平衡树板子

题目要求维护很多条链，不难想到用平衡树，个人用的是 fhq treap 。

将边化成点，每一棵 treap 都以点边点的顺序存了一条链，代表边的点权值为边权，代表点的点权值为 $0$ 。

操作一

加边操作，合法的条件是：

  • 不在同一棵子树。

  • 两个点都在链头或链尾，即中序遍历最大或最小。

如果 $x,y$ 同时在链头或同时在链尾还要翻转一下 treap 。

然后把 $x$ 放最后， $y$ 放最前，两棵树之间插入边权为 $z$ 的一个代表边的点，合起来就行。

操作二

删边操作，合法的条件是：

  • 在同一棵子树

  • 两个点之间只隔了一个代表边的点。

满足条件就直接把那个代表边的点拆掉就行。

操作三

本质上与上面两个一样，读者自行理解。

操作四

判断一下根是否相等就好。

操作五

首先还是判断 $x,y$ 是否同根，不同根直接返回。

然后比较一下 $x,y$ 在 treap 中排名的大小，不妨设为 $rx,ry$ 。

  • 如果 $rx<ry$ ，要往右边走，于是终点就是最右端的点，时间为 $x$ 节点后的边权和。

  • 如果 $rx>ry$ ，要往左边走，于是终点就是最左端的点，时间为 $x$ 节点前的边权和。

实现细节

有几个坑点提一下：

  • 查询根和排名需要维护节点父亲，然后从当前节点往上跳统计答案。

  • 查询排名时一定要释放从根到它的所有翻转标记。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<cstdlib>
#define rep(a,b,c) for(int c=(a);c<=(b);++c)
#define drep(a,b,c) for(int c=(a);c>=(b);--c)
inline int read()
{
	int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
inline int Get()
{
	char ch;do ch=getchar();while(ch<'a'||ch>'z');switch(ch)
	{
		case 'a': return 1;case 'c': return 3;case 'r': return 4;
		case 'd': getchar();return getchar()=='l'?2:5;
	}return 0;
}
inline void print(const int &p){if(p>9)print(p/10);putchar(p%10+'0');}
inline void pt(const int &p,const char &ch='\n'){print(p<0?putchar('-'),-p:p);putchar(ch);}
template<typename T> inline void Swap(T&x,T&y){T tmp=x;x=y;y=tmp;}
const int N=1e5+10;int T1,T2,T3,n,cgt;
struct FHQ{int l,r,siz,vl,sm,fa;bool tg;short key;inline FHQ(){key=rand();siz=1;}}t[N<<2];
inline void Rev(int x){Swap(t[x].l,t[x].r);t[x].tg^=1;}
inline void pushdown(int x){if(t[x].tg)Rev(t[x].l),Rev(t[x].r),t[x].tg=false;}
inline void update(int x)
{
	t[x].siz=t[t[x].l].siz+t[t[x].r].siz+1;
	t[x].sm=t[t[x].l].sm+t[t[x].r].sm+t[x].vl;
	t[t[x].l].fa=t[t[x].r].fa=x;t[x].fa=0;
}
inline void split(int cur,int k,int &x,int &y)
{
	if(!cur){x=y=0;return;}pushdown(cur);
	if(t[t[cur].l].siz>=k){y=cur;split(t[cur].l,k,x,t[cur].l);update(y);return;}
	x=cur;split(t[cur].r,k-t[t[cur].l].siz-1,t[cur].r,y),update(x);
}
inline int merge(int x,int y)
{
	if(!x||!y)return x|y;pushdown(x);pushdown(y);
	if(t[x].key<t[y].key){t[x].r=merge(t[x].r,y);update(x);return x;}
	t[y].l=merge(x,t[y].l);update(y);return y;
}
inline int fnd(int x){while(t[x].fa)x=t[x].fa;return x;}
inline void pushall(int x){if(t[x].fa)pushall(t[x].fa);pushdown(x);}
inline int rnk(int k){pushall(k);int r=t[t[k].l].siz;while(t[k].fa){r+=(k==t[t[k].fa].r)?t[t[t[k].fa].l].siz+1:0;k=t[k].fa;}return r+1;}
inline void add(int x,int y,int z)
{
	int fx=fnd(x),fy=fnd(y);
	if(fx==fy)return puts("ERROR"),void();
	int rx=rnk(x),ry=rnk(y);
	if((rx==1||rx==t[fx].siz)&&(ry==1||ry==t[fy].siz))
	{
		if(rx==1)Swap(x,y),Swap(fx,fy),Swap(rx,ry);
		if(rx==1)Rev(fx);if(ry==t[fy].siz)Rev(fy);
		t[++cgt].siz=1;t[cgt].vl=t[cgt].sm=z;merge(merge(fx,cgt),fy);puts("OK");
	}
	else puts("ERROR");
}
inline void del(int x,int y)
{
	int fx=fnd(x),fy=fnd(y);if(fx!=fy)return puts("ERROR"),void();
	int rx=rnk(x),ry=rnk(y);if(rx>ry)Swap(rx,ry),Swap(fx,fy),Swap(x,y);
	if(ry!=rx+2)puts("ERROR");else{split(fx,rx,T1,T2);split(T2,1,T1,T3);puts("OK");}
}
inline void chg(int x,int y,int z)
{
	int fx=fnd(x),fy=fnd(y);if(fx!=fy)return puts("ERROR"),void();
	int rx=rnk(x),ry=rnk(y);if(rx>ry)Swap(rx,ry),Swap(fx,fy),Swap(x,y);
	if(ry!=rx+2)return puts("ERROR"),void();
	split(fx,rx,T1,T2);split(T2,1,T2,T3);t[T2].sm=t[T2].vl=z;
	merge(merge(T1,T2),T3);puts("OK");
}
inline void qry(int x,int y)
{
	int fx=fnd(x),fy=fnd(y);if(fx!=fy)return puts("ERROR"),void();
	int rx=rnk(x),ry=rnk(y);if(rx<ry)
	{
		int c=fx;while(t[c].r)pushdown(c),c=t[c].r,pushdown(c);pt(c,' ');
		split(fx,rx,T1,T2);pt(t[T2].sm);merge(T1,T2);
	}
	else
	{
		int c=fx;while(t[c].l)pushdown(c),c=t[c].l,pushdown(c);pt(c,' ');
		split(fx,rx,T1,T2);pt(t[T1].sm);merge(T1,T2);
	}
}
int main()
{
	t[0].siz=0;cgt=n=read();int Q=read();rep(1,Q,i)
	{
		int opt=Get(),x=read(),y=read();
		switch(opt)
		{
			case 4: puts(fnd(x)==fnd(y)?"YES":"NO");break;
			case 1: add(x,y,read());break;case 2: del(x,y);break;
			case 3: chg(x,y,read());break;case 5: qry(x,y);break; 
		}
	}
}