BZOJ 3123 森林

发表于 | 更新于

Link

Solution

良心出题人。。写一个LCT再写一个裸主席树再写一个暴力就给85pts。。 正解启发式。启发式真是好，好写又不慢。。 如果没有Link操作，直接树上主席树（见CLJ论文）。 对于Link操作，采用把小树合到大树里面去的方法。小树所有节点的主席树都暴力重建。 查询的时候要求LCA。因为是动态地连接，只能用倍增（可以不用吗？？）。因此在之前的DFS中搜到每个点都预处理一下fa[][]fa[][]数组。 对于一个点，重建一次的代价是O(logn)O(\log n)(主席树+倍增)。一个点至多被重构O(logn)O(\log n)次：因为每次重构，这个点所在的子树的大小都至少扩大了一倍，所以最多logn\log n次操作就能这个点与其它所有的点连成一棵树了。类似并查集的按秩合并。 一开始WA了，然后RE了。因为fa[][]fa[][]数组没有彻底清零，写成了 

1
if(!(fa[pos][i]=fa[fa[pos][i-1]][i-1])) break;

Tips

倍增LCA数组重建之后一定要彻底清零。。

Code

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
//重构一个点是log n 一个点最多被重构log n次
using std::sort;
using std::lower_bound;
using std::swap;
const int MAXN=8e4+10,LOG=20;
namespace iSeg
{
	const int TL=1;int TR;
	const int SIZE=MAXN*LOG*LOG;
	struct Node
	{
		Node *son[2];int cnt;
		Node(Node *lc=0,Node *rc=0){son[0]=lc,son[1]=rc;cnt=0;}
		void up(){cnt=son[0]->cnt+son[1]->cnt;}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root[MAXN];
	Node *newNode()	{return new(ME++) Node;}
	Node *newNode(Node *old)
	{
		static Node *cur;
		cur=newNode();*cur=*old;return cur;
	}
	void Edit(Node *&pos,int L,int R,int goal,int v)
	{
		pos=newNode(pos);
		if(L==R) pos->cnt+=v;
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Edit(pos->son[0],L,MID,goal,v);
			else Edit(pos->son[1],MID+1,R,goal,v);
			pos->up();
		}
	}
	int GetK(Node *p1,Node *p2,Node *lca,Node *lcaf,int L,int R,int K)//可以改成非递归
	{
		if(L==R) return L;
		else
		{
			int sum=p1->son[0]->cnt+p2->son[0]->cnt-lca->son[0]->cnt-lcaf->son[0]->cnt,MID=(L+R)>>1;
			if(K<=sum) return GetK(p1->son[0],p2->son[0],lca->son[0],lcaf->son[0],L,MID,K);//写成了sum<=K
			else return GetK(p1->son[1],p2->son[1],lca->son[1],lcaf->son[1],MID+1,R,K-sum);//写成了K
		}
	}
}using namespace iSeg;
struct Edge{int to,pre;}e[MAXN<<1];int ec,id[MAXN],w[MAXN];
void Adde(int f,int t)
{
	e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;
	e[++ec].to=f;e[ec].pre=id[t];id[t]=ec;
}
int fa[MAXN][LOG],dep[MAXN];
int LCA(int p1,int p2)
{
	if(dep[p1]<dep[p2]) swap(p1,p2);
	for(int j=LOG-1;~j;j--)
		if(dep[fa[p1][j]]>=dep[p2]) p1=fa[p1][j];//写成了<=
	//0,1的dep不能相等。。否则会跳过头。。
	if(p1==p2) return p1;
	for(int j=LOG-1;~j;j--)
		if(fa[p1][j]!=fa[p2][j]) p1=fa[p1][j],p2=fa[p2][j];
	return fa[p1][0];
}
int ud[MAXN],ut,sz[MAXN],rt[MAXN];
void DFS(int pos,int r)
{
	for(int j=1;j<LOG;j++)
		fa[pos][j]=fa[fa[pos][j-1]][j-1];
	ud[pos]=ut;
	rt[pos]=r;sz[r]++;
	dep[pos]=dep[fa[pos][0]]+1;
	root[pos]=root[fa[pos][0]];
	Edit(root[pos],TL,TR,w[pos],1);
	for(int i=id[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(ud[u]==ut) continue;
		fa[u][0]=pos;
		DFS(u,r);
	}
}
int main()
{
	null->son[0]=null->son[1]=null;root[0]=null;

	static int t[MAXN];
	scanf("%*d");
	int n,m,q;get(n),get(m),get(q);TR=n;
	for(int i=1;i<=n;i++) get(w[i]),t[i]=w[i];
	sort(t+1,t+1+n);
	for(int i=1;i<=n;i++) w[i]=lower_bound(t+1,t+1+n,w[i])-t;//写成了-w.....上天了...
	for(int i=1;i<=m;i++)
	{
		int x,y;get(x),get(y);
		Adde(x,y);
	}
	ut++;
	for(int i=1;i<=n;i++)
		if(ud[i]!=ut)
			DFS(i,i);
	int last=0;
	#define decode(x) (x^=last)
	for(int i=1;i<=q;i++)
	{
		char opt;int x,y,K;
		while(!isalpha(opt=getchar()));
		get(x),decode(x),get(y),decode(y);
		if(opt=='L')//Link写的有问题??
		{
			if(sz[rt[x]]>sz[rt[y]]) swap(x,y);
			sz[rt[x]]=0;fa[x][0]=y;
			++ut;DFS(x,rt[y]);
			Adde(x,y);
		}
		else
		{
			get(K),decode(K);
			int lca=LCA(x,y);
			last=t[GetK(root[x],root[y],root[lca],root[fa[lca][0]],TL,TR,K)];
			printf("%d\n",last);
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE  WA once. 
 * * * * * * * * * */