自动搬运

查看原文

来自洛谷，原作者为

	p_b_p_b *const int brain=NULL;

搬运于2025-08-24 22:04:33，当前版本为作者最后更新于2018-08-27 13:32:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话

这题各位dalao都说是裸的LCT，就我一个人想到splay。。。

然后出题人也只想到LCT，而且跑得巨快，于是比赛时时限是1s。。。

又因为我是蒟蒻，自带大常数，竟然比LCT还慢。。。哭死

结果出题人善良地在比赛时卡我常数在赛后把时限调到2s

正题

这题我一眼平衡树，又因为treap不熟，于是写了splay

一开始对于每个元素都建一棵splay。

若合并：

{

设x合并到y后面

朴素做法：

x=getfa(x);y=getfa(y);
if (x==y) return;
while (rs[B]) B=rs[B];
fa[A]=B;rs[B]=A;
splay(A,0);

卡常：加启发式即可

}

断开：

{

splay(x,0);
fa[ls[x]]=0;ls[x]=0;
pushup(x)

}

查询：

{

if (x==y) return a[x];
fx=getfa(x);fy=getfa(y);
if (fx!=fy) return -1;
splay(x,0);splay(y,x);
return rs[x]==y?a[x]+a[y]+sum[ls[y]]:a[x]+a[y]+sum[rs[y]];

}

完。

代码

#include<bits/stdc++.h>
#define sz 201010
using namespace std;
typedef long long ll;
struct FastIO
{
	inline FastIO& operator>>(int& x)
	{
		x=0;char f=0,ch=getchar();
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
		return x=(f?-x:x),*this;
	}
	inline FastIO& operator>>(ll& x)
	{
		x=0;char f=0,ch=getchar();
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
		return x=(f?-x:x),*this;
	}
	inline FastIO& operator>>(double& x)
	{
		x=0;char f=0,ch=getchar();
		double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
		if(ch=='.')
		{
			ch=getchar();
			while(ch<='9'&&ch>='0') x+=d*(ch^48),d*=0.1,ch=getchar();
		}
		return x=(f?-x:x),*this;
	}
}read;

void file()
{
	#ifndef ONLINE_JUDGE
	freopen("a.txt","r",stdin);
	#endif
}

ll a[sz];

struct hh{int fa,dep,ch[2];ll sum;}tr[sz];

int getfa(int x){while (tr[x].fa) x=tr[x].fa;return x;}
void pushup(int x)
{
	tr[x].sum=tr[tr[x].ch[0]].sum+tr[tr[x].ch[1]].sum+a[x];
	tr[x].dep=max(tr[tr[x].ch[0]].dep,tr[tr[x].ch[1]].dep)+1;
}
bool get(int x){return tr[tr[x].fa].ch[1]==x;}
void rotate(int x)
{
	int y=tr[x].fa,z=tr[y].fa;
	int k=get(x),w=tr[x].ch[!k];
	if (z) tr[z].ch[get(y)]=x;tr[x].ch[!k]=y;tr[y].ch[k]=w;
	if (w) tr[w].fa=y;tr[x].fa=z;tr[y].fa=x;
	pushup(y);pushup(x);
}
void splay(int x,int to)
{
	while (tr[x].fa!=to)
	{
		int y=tr[x].fa;
		if (tr[y].fa!=to) rotate(get(x)==get(y)?y:x);
		rotate(x);
	}
}
void connect(int x,int y) //head[x]->tail[y]
{
	x=getfa(x);y=getfa(y);
	if (x==y) return;
	if (tr[x].dep>tr[y].dep)
	{
		while (tr[x].ch[0]) x=tr[x].ch[0];
		tr[x].ch[0]=y;tr[y].fa=x;
		splay(y,0);
	}
	else
	{
		while (tr[y].ch[1]) y=tr[y].ch[1];
		tr[y].ch[1]=x;tr[x].fa=y;
		splay(x,0);
	}
}
void cut(int x)
{
	splay(x,0);
	tr[tr[x].ch[0]].fa=0;tr[x].ch[0]=0;
	pushup(x);
}
ll query(int x,int y)
{
	if (x==y) return a[x];
	int fx=getfa(x),fy=getfa(y);
	if (fx!=fy) return -1;
	splay(x,0);splay(y,x);
	int ls=tr[y].ch[0],rs=tr[y].ch[1];
	return get(y)?tr[ls].sum+a[x]+a[y]:tr[rs].sum+a[x]+a[y];
}
int main()
{
	file();
	int n,m,i,x,y;
	read>>n>>m;
	for (i=1;i<=n;i++) read>>a[i];
	for (i=1;i<=n;i++) pushup(i);
	while (m--)
	{
		char ch;cin>>ch;
		if (ch=='M') read>>x>>y,connect(x,y);
		else if (ch=='D') read>>x,cut(x);
		else read>>x>>y,printf("%lld\n",query(x,y));
	}
}

吐槽

出题人太恶心啦！！这份代码最慢的点跑了1200ms，比赛时时限1000ms！！！我的ＡＣ没啦！！！