太玄学了为什么会RE???
查看原帖
太玄学了为什么会RE???
538683
Enoch006楼主2024/5/12 22:04

重新表达一下

rt,求解,会用小号关注的

这份代码会RE

#include <bits/stdc++.h>
#define maxm 100005
#define maxn 500
#define int long long
#define inf 0x3f3f3f3f3f3f
using namespace std;
namespace fastIO{
#ifdef ONLINE_JUDGE
	const int SIZE = 1 << 20;
	char in[SIZE], out[SIZE], *p1 = in, *p2 = in, *p3 = out;
#define getchar() (p1 == p2 && (p2 = (p1 = in) + fread(in, 1, SIZE, stdin), p1 == p2) ? EOF : *p1 ++ )
#define flush() (fwrite(out, 1, p3 - out, stdout))
#define putchar(x) (p3 == out + SIZE && (flush(), p3 = out), *p3 ++ = (x))
	class Flush {public: ~Flush() {flush();}} _;
#endif
	template<typename Type>
	inline Type read(Type &x){
		x = 0; bool flag(0); char c = getchar();
		while (!isdigit(c)) flag ^= (c == '-'), c = getchar();
		while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
		return flag ? x = -x : x;
	}
	template<typename Type>
	inline void write(Type x){
		x < 0 ? x = -x, putchar('-') : 0;
		static short Stack[35], top(0);
		do Stack[ ++ top] = x % 10, x /= 10; while (x);
		while (top) putchar(Stack[top -- ] | 48);
	}
	inline char read(char &x) {do x = getchar(); while (isspace(x)); return x;}
	inline int read(char *x) {static char *c = x; while (!isspace(*c = getchar()) && *c != EOF) c ++ ; *c = '\0'; return c - x;}
	inline char write(const char &x) {return putchar(x);}
	template<typename Type> inline void write(Type *x) {while (*x) putchar(*x ++ );}
	template<typename Type, typename ...Args> inline void read(Type &x, Args &...y) {read(x), read(y...);}
	template<typename Type, typename ...Args> inline void write(const Type &x, const Args &...y) {write(x), putchar(' '), write(y...), sizeof...(y) ^ 1 ? 0 : putchar('\n');}
	template<typename Type>	inline void write(const Type &x, char c) {write(x), putchar(c);}
#ifdef ONLINE_JUDGE
	#undef getchar
	#undef flush
	#undef putchar
#endif
}
using namespace fastIO;
int n,l,q,lastans;
int a[maxm],d[maxm];
int B,m;
struct node{
	int id,x;
}t[maxn][maxn];
bool cmp(node x,node y){
	return x.x<y.x;
}
int belong[maxm],st[maxn],ed[maxn],len[maxn];
int pre[maxm],suf[maxm];
int big[maxn][maxm],small[maxn][maxm];
int ans[maxn][maxn];
int tmp1[maxn],tmp2[maxn];
int lowbit(int x){return x&(-x);}
void add(int D[],int x){
	while(x<=n){
		D[x]++;
		x+=lowbit(x);
	}
}
int ask(int D[],int x){
	int sum=0;
	while(x){
		sum+=D[x];
		x-=lowbit(x);
	}return sum;
}
void Clear(){for(register int i=1;i<=n;i++)d[i]=0;}
void Split(){
	for(register int i=1;i<=m;i++){
		st[i]=(i-1)*B+1;
		ed[i]=min(n,i*B);
		len[i]=ed[i]-st[i]+1;
		//为了散块加散块归并优化 
		for(register int j=st[i];j<=ed[i];j++){
			belong[j]=i;
			t[i][j-st[i]+1]=(node){j,a[j]};
		}
		sort(t[i]+1,t[i]+len[i]+1,cmp);
		//散块/整块内部预处理pre,suf数组 
		Clear();
		for(register int j=st[i];j<=ed[i];j++){
			pre[j]=ask(d,n)-ask(d,a[j]);
			if(j!=st[i])pre[j]+=pre[j-1];
			//cout<<j<<" "<<c[j]<<"\n";
			add(d,a[j]);
		}
		Clear();
		for(register int j=ed[i];j>=st[i];j--){
			suf[j]=ask(d,a[j]-1);
			if(j!=ed[i])suf[j]+=suf[j+1];
			add(d,a[j]);
		}		
		//散块+整块
		for(register int j=st[i];j<=ed[i];j++)big[i][a[j]]++;
		for(register int j=1;j<=n;j++)small[i][j]=big[i][j]+small[i][j-1];
		for(register int j=n;j>=1;j--)big[i][j]+=big[i][j+1];
	}
	for(register int i=1;i<=m;i++){
		for(register int j=1;j<=n;j++){
			small[i][j]+=small[i-1][j];
			big[i][j]+=big[i-1][j];
		}
	} 
	for(register int i=1;i<=m;i++){
		for(register int j=i;j<=m;j++){
			ans[i][j]=ans[i][j-1];
			for(register int o=st[j];o<=ed[j];o++)ans[i][j]+=big[j-1][a[o]+1]-big[i-1][a[o]+1];
			//cout<<i<<" "<<j<<" "<<ans[i][j]<<"\n";
		}//cout<<"\n";
	}	
}
int Merge(int cnt1,int cnt2){
	int l=1,r=1,sum=0,cnt=0;
	while(l<=cnt1){
		if(l>cnt1)return sum;
		if(r>cnt2){
			sum+=cnt;
			l++;			
		}
		else if(tmp1[l]>tmp2[r]){
			cnt++;
			r++;
		}else{
			sum+=cnt;
			l++;
		}
	//	cout<<l<<" "<<r<<"\n";
		//system("pause");
	}return sum;
}
int Ask(int x,int y){
	int L=belong[x],R=belong[y],sum=0;
	if(L==R){
//		if(1){
//			sum=pre[y];
//			int cnt1=0,cnt2=0;
//			for(int i=1;i<=len[L];i++){
//				if(t[L][i].id<x)tmp1[++cnt1]=t[L][i].x;
//				if(t[L][i].id<=y&&t[L][i].id>=x)tmp2[++cnt2]=t[L][i].x;
//			}
//			sum-=Merge(cnt1,cnt2);			
//		}else{
			//加上这几行后 
			//Clear();//-------------------------------------------------------------------------------------
			//for(int i=x;i<=y;i++){
			//	sum+=ask(d,n)-ask(d,a[i]);
			//	add(d,a[i]);
			//}	//-------------------------------------------------------------------------------------------------
//		}
		return sum;
	}
	sum=suf[x]+pre[y];//散块内部
//	cout<<"散块内部:"<<sum<<"\n"; 
	int cnt1=0,cnt2=0;
	for(int i=1;i<=len[L];i++)if(t[L][i].id>=x)tmp1[++cnt1]=t[L][i].x;
	for(int i=1;i<=len[R];i++)if(t[R][i].id<=y)tmp2[++cnt2]=t[R][i].x;
	sum+=Merge(cnt1,cnt2);//散块+散块 
//	cout<<"散块+散块:"<<sum<<"\n";
	//整块+散块 
	for(register int i=x;i<=ed[L];i++)sum+=small[R-1][a[i]-1]-small[L][a[i]-1];
	for(register int i=st[R];i<=y;i++)sum+=big[R-1][a[i]+1]-big[L][a[i]+1];
	L++;R--;
//	cout<<"整块+散块:"<<sum<<"\n";
	for(register int i=L;i<=R;i++)sum+=pre[ed[i]];//整块内部
//	cout<<"整块内部:"<<sum<<"\n";
	sum+=ans[L][R]; //整块+整块 
//	cout<<"整块+整块:"<<sum<<"\n";
	return sum;
}
signed main(){
	read(n);read(q);
    for(register int i=1;i<=n;i++)read(a[i]);	
	B=sqrt(n);
	m=ceil(n*1.0/B);
	Split();
	for(register int i=1;i<=q;i++){
		int x,y;read(x);read(y);
		x^=lastans;y^=lastans; 
		if(x>y)swap(x,y); 
		lastans=Ask(x,y);
		write(lastans,'\n');
	}
    return 0;
}

然而加上了149-152行他就不RE了???

这是为什么啊

2024/5/12 22:04
加载中...