部分点的评测状况随时间,O2的开关在RE与TLE中反复横跳,但都是只A最后一个点.

第一个点的数据下到本地大概只要1s左右就能跑出来,没有RE过.

似乎有不少其他人都出现了大面积RE的情况,然而他们的诉求却清一色地被忽视???

code:

#include<iostream>
#include<cstdio>
#define N 2000500
using namespace std;
int read(){
	char c=getchar();int in=0;
	while(c<48 || c>57)
		c=getchar();
	while(c>47 && c<58)
		in=in*10+c-48,c=getchar();
	return in;
}
struct SPLAY{								//splay保证以每个节点在lct中的dpt为key,是一棵bst
	struct node{
		int son[2];
		int fa,val,sum;						//val:该节点val;sum:该节点及其子树val的xor 
		bool tag;
	}tr[N];
	#define is_not_root(x) (tr[tr[x].fa].son[0]==x || tr[tr[x].fa].son[1]==x)
	inline void pushup(const int &x){
		tr[x].sum=tr[x].val^tr[tr[x].son[0]].sum^tr[tr[x].son[1]].sum;
	}
	inline void link(const int &x,const int &y,const bool &d){
		tr[tr[x].fa=y].son[d]=x;
	}
	inline void pushdown(const int &x){
		if(tr[x].tag){
			swap(tr[x].son[0],tr[x].son[1]);
			tr[tr[x].son[0]].tag^=1;
			tr[tr[x].son[1]].tag^=1;
			tr[x].tag=0;
		}
	}
	void print(int k) {
		if(!k)return;
		cout<<"now node No."<<k<<endl;
		cout<<"ls: "<<tr[k].son[0]<<" rs: "<<tr[k].son[1]<<endl;
		cout<<"val= "<<tr[k].val<<" sum= "<<tr[k].sum<<" fa="<<tr[k].fa<<endl;
		pushdown(k);
		print(tr[k].son[0]);
		print(tr[k].son[1]);
	}
	inline void rotate(const int &x){
		int y=tr[x].fa,z=tr[y].fa,d=tr[y].son[1]==x;
		if(is_not_root(y))
			link(x,z,tr[z].son[1]==y);
		else
			tr[x].fa=z;
		link(tr[x].son[!d],y,d);
		link(y,x,!d);
		pushup(y);
		pushup(x);
	}
	inline void reverse(const int &x){		//对于以x为根的一棵splay,reverse 
		splay(x);
		tr[x].tag^=1;
	}
	int sta[N],top;
	inline void splay(const int &x){
		sta[++top]=x;
		while(is_not_root(sta[top]))
			sta[++top]=tr[sta[top-1]].fa;
//		puts("fuck");
		int goal=tr[sta[top]].fa;
		while(top)
			pushdown(sta[top--]);
//		cout<<"rotate "<<x<<" to "<<goal<<endl;
		while(tr[x].fa!=goal){
			const int y=tr[x].fa,z=tr[y].fa;
//			cout<<x<<" "<<y<<" "<<z<<endl;
			if(z==goal);
			else if(tr[y].son[0]==x ^ tr[z].son[0]==y) rotate(x);
			else rotate(y);
			rotate(x);
		}
	}
}Splay;
struct Link_Cut_Tree{
	inline void access(int x){
		int son=0;
		while(x){
//			puts("fuck~");
			Splay.splay(x);
			Splay.link(son,x,1);
			Splay.pushup(x);
			son=x;
			x=Splay.tr[x].fa;
		}
	}
	inline void makeroot(const int &x){
		access(x);
		Splay.reverse(x);
		Splay.pushup(x);
	}
	inline int findroot(int x){
		access(x);
		Splay.splay(x);
		while(Splay.tr[x].son[0])
			Splay.pushdown(x=Splay.tr[x].son[0]);
		Splay.splay(x);
		return x;
	}
	inline void link(const int &x,const int &y){
		makeroot(x);
		if(x!=findroot(y))
			Splay.tr[x].fa=y;
	}
	inline void cut(const int &x,const int &y){
		split(x,y);
//		Splay.print(x);
//		Splay.print(y);
		if(!Splay.tr[x].son[0] && Splay.tr[y].son[1]==y){
//			cout<<"cut "<<x<<" "<<y<<endl;
			Splay.tr[y].fa=Splay.tr[x].son[1]=0;
			Splay.pushup(x);
		}
	}
	inline void split(const int &x,const int &y){
//		puts("fuck");
		makeroot(x);
//		puts("fuck");
		access(y);
//		puts("fuck");
		Splay.splay(x);
	}
}LCT;
int main(){
//	freopen("P3690_1.in.txt","r",stdin);
//	freopen("myP3690_1.out.txt","w",stdout);
	int n=read(),m=read();
	for(int i=1; i<=n; i++)
		Splay.tr[i].val=Splay.tr[i].sum=read();
	while(m--){
		int op=read(),x=read(),y=read();
//		cout << "fuck" << endl;
		switch(op){
			case 0:LCT.split(x,y);printf("%d\n",Splay.tr[x].sum);break;
			case 1:LCT.link(x,y);break;
			case 2:LCT.cut(x,y);break;
			default:Splay.splay(x);Splay.tr[x].val=y;Splay.pushup(x);
		}
	}
	return 0;
}

为防止玄学错误我已经试着把N开到2000k了,但还是RE

跪求大佬解答我等一众RE蒟蒻的疑惑!