CF414E Mashmokh's Designed Problem

发表于 | 更新于

Link

神题。。（哦应该是因为我太弱了。。）

Solution

一直不明白DFS序到底是怎么定义的 那种记录每个点第一次访问的位置的，总共nn个点，有人叫它DFS序 还有那种记录DFS的路径的，总共2n−12n-1个点，有人也叫它DFS序。。 于是各种题解随便一混用就能把我转很久(应该是我太弱了) 好吧，这个用的是第二种DFS序。。那我叫它multiDFS序好了。 首先求出树的multiDFS序=S=\mathcal{S} 那么求点对距离就是求出LCA然后计算，即为区间最小值 然后求最后一个深度为depdep的节点，只要在序列上二分然后判存在性就行了，判存在的条件是 区 间 最 小 值 区 间 最 大 值 。不要漏掉第二个条件！！ 要求把一棵子树移动到它的第kk个祖先上，首先这个第kk个祖先也可以在序列上二分得到，而移动在S\mathcal{S}中就对应区间的移动。转化为 的基本操作。 这样两个二分就转化为在 上走。 But。。

Tips

关于 的用法

says ydc

的区间操作一直让我感到云里雾里。 普通的 ，一般是自顶向下操作(如维修数列)，需要一个 来在 中定位。这样，就可以一路 下去，没有问题。 但是在一些直接定位到节点的应用中，比如 ，它祖先的 标记就访问不到了。 学习 的时候，看到Po姐的做法是一直递归到根节点，然后一路下放标记。因为也没学会势能分析，也不知道这样复杂度是否有保障，但也就一直这样写了。 在Summer Camp上问了下gty大神，他表示他一直只是在 的时候下放一下标记，从来没出现问题。问起关于祖先的标记，他表示没有考虑过。 向gty大神要来代码，最后也没有完全弄明白。 那天晚上跑到省队的实验室去问swh（之前他学的也是类似的写法，只是写hzwer的代码，用手工栈），他说因为 操作以后会把节点 到根。当时觉得挺有道理的样子，但也没再深究。 写这道题，又用到了直接定位节点需要处理祖先标记的问题。 思考了以下，发现只要按照ydc所讲的，在一个点停下就 上去就行了。 在 中，需要把父节点的标记下传，然后把当前节点的标记下传，遵循的原则就是：在出子树之前下传防止多传给其它子树，在进入子树之前下传让防止漏传给其它子树。 对于 ，读取之前本来是可以不需要 到根的。(修改也可以在之后 ) 但现在的话就对读写都一视同仁，都 到根，就解决了标记的问题，也让思维更清晰一些。 （特殊情况：提取区间之后对区间进行修改，不能 到跟节点，那就修改之后再 ） 切记对节点进行修改之后要更新区间信息！

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define getc() getchar()
#define putc(x) putchar(x)
#define puts(x) printf("%s",x)
#define iter(x) typeof((x).begin())
#define riter(x) typeof((x).rbegin())
#define foreach(it,x) for(iter(x) it=(x).begin();it!=(x).end();++it)
typedef long long ll;
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
using std::swap;
using std::pair;
using std::make_pair;
using std::vector;

const int INF=0x1f1f1f1f,MAXN=1e5+11;
namespace Splay
{
	const int SIZE=MAXN<<2;
	typedef pair<int,int> Data;
	struct Node
	{
		Node *son[2],*fa;
		int add,ssz,isz;
		Data self,imin,imax; 
		Node()
		{
			imin=make_pair(INF,0);
			imax=make_pair(-INF,0);
			son[0]=son[1]=fa=0;
			add=isz=ssz=0;
		}
		bool kind(){return fa->son[1]==this;}
		bool isRoot(){return fa->son[0]!=this && fa->son[1]!=this;}
		void Add(int);
		void up();
		void down()
		{
			if(add)
			{
				son[0]->Add(add);
				son[1]->Add(add);
				add=0;
			}
		}
		void uptoroot()
		{
			up();
			if(!isRoot()) fa->uptoroot();
		}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root=null,*lnull,*rnull;
	void Node::Add(int v)
	{
		if(this!=null)
		{
			add+=v;
			self.first+=v;
			imin.first+=v;
			imax.first+=v;
		}
	}
	void Node::up()
	{
		assert(this!=null);
		if(this==lnull || this==rnull)
			imin=make_pair(INF,0),imax=make_pair(-INF,0);
		else
			imin=imax=self;
		chkmn(imin,min(son[0]->imin,son[1]->imin));
		chkmx(imax,max(son[0]->imax,son[1]->imax));
		isz=ssz+son[0]->isz+son[1]->isz;
	}
	Node *newNode(Data v)
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=cur->fa=null;
		cur->imin=cur->imax=cur->self=v;
		cur->add=0;cur->isz=cur->ssz=1;
		return cur;
	}
	Node *Append(Node *&pos,Node *nw)
	{
		nw->son[0]=pos;
		if(pos!=null)
			pos->fa=nw;
		pos=nw;pos->up();
		return pos;
	}
	
	void Trans(Node *pos)
	{
		static Node *f,*grf;
		static int d;
		f=pos->fa,grf=f->fa;
		d=pos->kind();
		
		f->down();//here
		pos->down();

		if(!f->isRoot())
			grf->son[f->kind()]=pos;
		pos->fa=grf;
		f->son[d]=pos->son[!d];pos->son[!d]->fa=f;
		pos->son[!d]=f;f->fa=pos;
		f->up();
		pos->up();
		assert(pos->son[0] && pos->son[1] && f->son[0] && f->son[1]);
	}
	void SplayTo(Node *pos,Node *goal=0)
	{
		bool flag=0;
		if(goal==0)
			goal=null,flag=1;
		while(pos->fa!=goal)
		{
			Node *f=pos->fa;
			if(f->fa!=goal)
				Trans(pos->kind()==f->kind()?f:pos);
			Trans(pos);
		}
		if(goal==null && !flag)
			root=pos;
	}
	Node *Adjace(Node *pos,int dir=0)
	{
		SplayTo(pos,null);
		pos=pos->son[dir];
		while(pos->son[!dir]!=null)	
			pos=pos->son[!dir];
		SplayTo(pos,null);
		return pos;
	}
	Node *Split(Node *p1,Node *p2)
	{
		p1=Adjace(p1,0);
		p2=Adjace(p2,1);
		SplayTo(p1,null);
		SplayTo(p2,p1);
		return p2->son[0];
	}
	int Rank(Node *pos)
	{
		SplayTo(pos,null);
		return pos->son[0]->isz;
	}
}using namespace Splay;
vector<int> son[MAXN];
struct SubTree
{
	Splay::Node *lbound,*rbound,*trfa;
}sub[MAXN];
void DFS(int pos,int dep,Splay::Node* &s)
{
	sub[pos].lbound=Append(s,newNode(make_pair(dep,pos)));
	foreach(it,son[pos])
	{
		Append(s,newNode(make_pair(dep,pos)));
		sub[*it].trfa=s;
		DFS(*it,dep+1,s);
	}
	sub[pos].rbound=Append(s,newNode(make_pair(dep,pos)));
}
int FindPar(int p,int acn)
{
	SplayTo(sub[p].lbound,null);
	Splay::Node *pos=root->son[0];
	int dep=root->self.first-acn;
	for(;;)
	{
		pos->down();
		if(pos->son[1]->imin.first<=dep && dep<=pos->son[1]->imax.first)
			pos=pos->son[1];
		else if(pos->self.first==dep)
			return pos->self.second;
		else
			pos=pos->son[0];
	}
}
void Move(int pos,int acn)
{
	int par=FindPar(pos,acn);
	
	Splay::Node *rt=Split(sub[pos].trfa,sub[pos].rbound);
	rt->fa->son[0]=null,rt->fa->uptoroot();
	rt->fa=null;

	SplayTo(sub[pos].trfa);
	sub[pos].trfa->self.second=par;sub[pos].trfa->up();//..
	sub[pos].trfa->Add(1-acn);
	
	Splay::Node *last=Adjace(sub[par].rbound,0);
	SplayTo(last,null);
	SplayTo(sub[par].rbound,last);
	sub[par].rbound->son[0]=sub[pos].trfa;sub[par].rbound->uptoroot();
	sub[pos].trfa->fa=sub[par].rbound;
}
int Dist(int p1,int p2)
{
	if(Rank(sub[p1].lbound)>Rank(sub[p2].lbound))
		swap(p1,p2);//no judge swap
	Splay::Node* rt=Split(sub[p1].lbound,sub[p2].lbound);
	return sub[p1].lbound->self.first+sub[p2].lbound->self.first-2*rt->imin.first;
}
int DepLast(int dep)
{
	++dep;
	Splay::Node* pos=root;
	for(;;)
	{
		pos->down();
		if(pos->son[1]->imin.first<=dep && dep<=pos->son[1]->imax.first) 
			pos=pos->son[1];
		else if(pos->self.first==dep)
			return pos->self.second;
		else
			pos=pos->son[0];
	}
}
int main()
{
	freopen("input","r",stdin);
	int n,m;get(n),get(m);
	for(int i=1;i<=n;++i)
	{
		int sc;get(sc);
		for(int j=1;j<=sc;++j)
		{
			int s;get(s);
			son[i].push_back(s);
		}
	}
	root=lnull=newNode(make_pair(INF,INF));
	rnull=newNode(make_pair(INF,INF));;
	DFS(1,1,root);
	Append(root,rnull);
	for(int i=1;i<=m;++i)
	{
		int opt,v,u,h,k;
		get(opt);
		switch(opt)
		{
			case 1:get(v),get(u);put(Dist(v,u)),putc('\n');break;
			case 2:get(v),get(h);Move(v,h);break;
			case 3:get(k);put(DepLast(k)),putc('\n');break;
		}
	}
	return 0;
}