如果你被卡 TLE 了

我教你一招。

我们充分发扬人类智慧，每次操作前随机选择一个点给它 splay 一下。

只要你保证算法的正确性，用这套方法没人能卡掉你。

亲自测试：本人原本被 11 点卡 TLE ，然后加入上述奇妙优化后直接通过，AC链接。

代码展示：

CPP

splay((1ll*rand()*rand())%n+1);

注意需要乘法运算两次，因为单个 rand 的范围是

0\sim 32767

。

还有一定要注意要在乘法前加 1ll* 否则会 RE 。

完整代码（顺便帮我找一下导致被卡的问题呗~）：

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ans=0,j=1;
	char c=getchar();
	while(c>'9' or c<'0'){
		if(c=='-')j=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		ans=(ans<<1)+(ans<<3)+(c^48);
		c=getchar();
	}
	return ans*j;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(48+x%10);
}
#define I inline void
#define lc(x) s[x][0]
#define rc(x) s[x][1]
#define nrt(x) (s[f[x]][0]==x or s[f[x]][1]==x)
const int N=3e5+5;
int n,m;
bool tag[N];
int s[N][2],f[N],v[N],sum[N];
I tg(int x){tag[x]^=1,swap(lc(x),rc(x));}
I up(int x){sum[x]=sum[lc(x)]^sum[rc(x)]^v[x];}
I down(int x){
	if(!tag[x])return;tag[x]=0;
	if(lc(x))tg(lc(x));if(rc(x))tg(rc(x));
}
I rotate(int x){
	int y=f[x],z=f[y],k=x==rc(y),w=s[x][!k];
	if(nrt(y))s[z][y==rc(z)]=x;s[x][!k]=y,s[y][k]=w;
	if(w)f[w]=y;f[y]=x,f[x]=z,up(y);
}
int st[N];
I splay(int x){
	int y=x,z=0;st[++z]=y;
	while(nrt(y))st[++z]=y=f[y];
	while(z)down(st[z--]);
	while(nrt(x)){
		y=f[x],z=f[y];
		if(nrt(y))rotate((rc(y)==x)^(rc(z)==y)?y:x);
		rotate(x);
	}up(x);
}
I access(int x){
	for(int y=0;x;x=f[y=x])
		splay(x),s[x][1]=y,up(x);
}
I mkrt(int x){access(x),splay(x),tg(x);}
inline int getrt(int x){
	access(x),splay(x);
	while(s[x][0])down(x),x=s[x][0];
	splay(x);return x;
}
I split(int x,int y){mkrt(x),access(y),splay(y);}
I link(int x,int y){
	mkrt(x);
	if(getrt(y)!=x)f[x]=y;
}
I cut(int x,int y){
	mkrt(x);
	if(getrt(y)==x and f[y]==x and !s[y][0])
		f[y]=s[x][1]=0,up(x);
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		v[i]=read();
	for(int i=1;i<=m;++i){
		int op=read(),x=read(),y=read();
		splay((1ll*rand()*rand())%n+1);
		switch(op){
		case 0:split(x,y),write(sum[y]),putchar(10);break;
		case 1:link(x,y);break;
		case 2:cut(x,y);break;
		case 3:splay(x),v[x]=y;
		}
	}
	return 0;
}

如果你被卡 TLE 了

讨论操作

回复

相关推荐

如果你被卡 TLE 了