1
8
2016
7

【天坑三】 LCT初探

      这么迟才学LCT。。人弱怎么办。。_(:з」∠)_。。。

   看着这篇论文学的 --> http://wenku.baidu.com/link?url=zkj-PcHffl3yWD8eSTpc7RcHPndKxR6E072sDE0w6MZ1CxYnbQDMHxLEGWJZ7gvkYHT2P9EAErh_wSf7839mSZBKxlHl6c9SEJ1kSCqW8ri


 

        LCT是可以解决动态树一类问题的数据结构,可以再均摊Nlog(N)的时间内进行Link,Cut,换根操作和维护链上信息。


        先讲解一下LCT中的几个概念

        称一个点被访问过,则刚对这个点进行了Access操作;

        Preferred Child:对于一个节点u,如果最后访问的节点在其子树w中,则称w为u的Preferred Child,如果最后访问的节点为u本身,则u没有Preferred Child;

        Preferred Edge:连接节点u与其Preferred Child的边;

        Preferred Path:由Preferred Edge连成的路径;

   

        我们可以显然的发现所有的Preferred Path会不重复地覆盖树上所有的点。。

        根据这个性质我们可以对于每一条Preferred Path用一颗平衡树维护,称为Auxiliary Tree。用平衡树按照深度为关键字维护每一条Preferred Path,所有深度比当前点大的都在右子树中,所有深度比当前点小的都在左子树中。然后我们对于每一棵平衡树记录一下这颗平衡树中最高点的父亲,记为Path Parent,这样我们就可以用若干棵Auxiliary Tree表示原树了。


         然后是LCT的几个操作:

        Access(u) :Access操作是LCT的基础,对一个点u进行Access操作后,它到根节点的边都变成Preferred Path;

        操作的结果如图所示:

           

        然后是实现问题:首先如果我们访问一个节点u则这个点的Preferred Child应该改为空。那么我们将它旋转到它所在的平衡树的根,将它的右子树与它分离。因为这个平衡树是以深度为关键字的,所以右子树中的点都是u的子孙节点。

        接下来将根到它的路径都改为Preferred Path。如果当前点的平衡树并不包含根节点,设v为当前u所在平衡树的Path Parent,将v旋转到它所在的平衡树的根,然后将其右子树替换为u所在的平衡树,再更改一下原右子树的Path Parent。

        关于复杂度,虽然看起来不正常。。但是均摊确实是Nlog(N)的。。。虽然我并不会证明。

 

        Change_Root(u):将这颗树的根换为x。这个那篇论文中并没有写到,然后不会。就被RXD大爷喷了。。_(:з」∠)_。。人生真艰难。其实自己YY一下就知道。先Access(u),将u旋转到根,然后调换左右子树。这样就相当于改变了深度关系。

 

        Link(x,y):将两颗不相连的树通过在x,y之间连边的方式相连。先Change_Root(x),然后将x所在的平衡树的Path Parent设为y就好了。

 

         Cut(x,y):将x,y之间的连边断开。将x换为根后,Access(y),然后旋转到根,y的左儿子就是x,然后将两者的关系断开。

 

node *Access(node *x){
	node *y;
	for (y=null;x!=null;y=x,x=x->Fa) {Splay(x);x->R = y;x->Update();}
	return y;
}
void Change_Root(node *x) {Access(x);Splay(x);x->Setrev();}
void Link(node *x,node *y) {Change_Root(x);x->Fa = y;}
void Cut(node *x,node *y) {Change_Root(x);Access(y);Splay(y);y->L = x->Fa = null;y->Update();}

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 6165  Solved: 3261
[Submit][Status][Discuss]

Description

某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

Input

第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况,你都要输出一个需要的步数,占一行。

Sample Input

4
1 2 1 1
3
1 1
2 1 1
1 1

Sample Output

2
3

 

        LCT模板,Link,Cut操作,Splay中只要维护子树大小即可   

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 200010;
using namespace std;
int n,num[N],Q,opt,x,k;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
struct node *null;
struct node {
	node *L,*R,*Fa;int S;
	int Top(){return Fa==null || (Fa->L!=this && Fa->R!=this);}
	void Update(){
		if (this==null) return;
		S = L->S+R->S+1;
	}
	void Zig(){
		if (this==null) return;
		node *y = Fa,*z = y->Fa;
		if (z->L==y) z->L = this;else if (z->R==y) z->R = this;Fa = z;
		y->L = R;if (R!=null) R->Fa = y;
		R = y;y->Fa = this;y->Update();
	}
	void Zag(){
		if (this==null) return;
		node *y = Fa,*z = y->Fa;
		if (z->L==y) z->L = this;else if (z->R==y) z->R = this;Fa = z;
		y->R = L;if (L!=null) L->Fa = y;
		L = y;y->Fa = this;y->Update();
	}
} Nd[N];
void Splay(node *x){
	while (!x->Top()){
		node *y = x->Fa,*z = y->Fa;
		if (!y->Top())
			if (y->L==x) if (z->L==y) y->Zig(),x->Zig();else x->Zig(),x->Zag();
			else if (z->R==y) y->Zag(),x->Zag();else x->Zag(),x->Zig();
		else if (y->L==x) x->Zig();else x->Zag();
	}
	x->Update();
}
node *Access(node *x){
	node *y;
	for (y=null;x!=null;y=x,x=x->Fa){Splay(x);x->R = y;x->Update();}
	return y;
}
void Link(node *x,node *y){
	Access(x);Splay(x);x->L = x->L->Fa = null;
	x->Fa = y;x->Update();
}
int main(){
	null = Nd; n = read();
	for (int i=0;i<=n+1;i++) Nd[i] = (node) {null,null,null,1};
	null->S = 0;
	for (int i=1;i<=n;i++) {
		x = read();
		if (i+x<=n) Nd[i].Fa = Nd+x+i;
	}
	Q = read();
	for (int i=1;i<=Q;i++) {
		opt = read();
		if (opt==1) {
			x = read()+1;
			printf("%d\n",Access(Nd+x)->S);
		}
		else {
			x = read()+1;k = read();
			if (x+k>n) Link(Nd+x,null);
			else Link(Nd+x,Nd+x+k);
		}
	}
}

3282: Tree

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 1033  Solved: 435
[Submit][Status][Discuss]

Description

给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。

0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。

2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。

3:后接两个整数(x,y),代表将点X上的权值变成Y。

Input

第1行两个整数,分别为N和M,代表点数和操作数。

第2行到第N+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。

第N+2行到第N+M+1行,每行三个整数,分别代表操作类型和操作所需的量。

Output

对于每一个0号操作,你须输出X到Y的路径上点权的Xor和。

Sample Input

3 3
1
2
3
1 1 2
0 1 2
0 1 1

Sample Output

3
1

HINT

1<=N,M<=300000

 
         LCT上维护xor和,单点修改,链询问,动态删加边。
        对于单点修改,我们直接将那个节点提取出来修改。。然后维护信息。
        对于链的询问:我们可以将那条链提取出来,先将x旋转到根,然后Access(y),这是y所在的Splay即为x到y的链,然后直接在Splay上打标记就好了。
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 300010;
using namespace std;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
int n,x,m,opt,y;
map <int,int> M[N];
struct node *null;
struct node {
	node *L,*R,*Fa;int S,val,Xor,rev;
	int Top() {return Fa==null || (Fa->L!=this && Fa->R!=this);}
	void Down() {if (this==null) return;if (rev) {L->Setrev();R->Setrev();rev = 0;}}
	void Setrev() {if (this==null) return;rev^=1;swap(L,R);}
	void Update() {if (this==null) return;S = L->S+R->S+1;Xor = L->Xor^R->Xor^val;}
	void Zig() {
		if (this==null) return;
		node *y = Fa,*z = y->Fa;
		if (z->L==y) z->L = this;else if (z->R==y) z->R = this;Fa = z;
		y->L = R;if (R!=null) R->Fa = y;
		R = y;y->Fa = this;y->Update();
	}
	void Zag() {
		if (this==null) return;
		node *y = Fa,*z = y->Fa;
		if (z->L==y) z->L = this;else if (z->R==y) z->R = this;Fa = z;
		y->R = L;if (L!=null) L->Fa = y;
		L = y;y->Fa = this;y->Update();
	}
} Nd[N];
void Splay(node *x){
	static node *S[N];node *tmp = x;int k = 0;
	while (!tmp->Top()) {S[++k] = tmp;tmp = tmp->Fa;} S[++k] = tmp;
	while (k) S[k--]->Down();
	while (!x->Top()) {
		node *y = x->Fa,*z = y->Fa;
		if (!y->Top()) 
			if (y->L==x) if (z->L==y) y->Zig(),x->Zig();else x->Zig(),x->Zag();
			else if (z->R==y) y->Zag(),x->Zag();else x->Zag(),x->Zig();
		else if (y->L==x) x->Zig();else x->Zag();
	}
	x->Update();
}
node *Access(node *x){
	node *y;
	for (y=null;x!=null;y=x,x=x->Fa) {Splay(x);x->R = y;x->Update();}
	return y;
}
void Change_Root(node *x) {Access(x);Splay(x);x->Setrev();}
void Link(node *x,node *y) {Change_Root(x);x->Fa = y;}
void Cut(node *x,node *y) {Change_Root(x);Access(y);Splay(y);y->L = x->Fa = null;y->Update();}
void Extract(node *x,node *y) {Change_Root(x);Access(y);Splay(y);}
int Judge(node *x,node *y) {while (x->Fa!=null) x = x->Fa;while (y->Fa!=null) y = y->Fa;return x==y;}
int main(){
	n = read();m = read();null = Nd;
	for (int i=0;i<=n;i++) Nd[i] = (node) {null,null,null,1,0,0,0};
	null->S = 0;
	for (int i=1;i<=n;i++) Nd[i].val = read();
	for (int i=1;i<=m;i++) {
		opt = read();
		if (opt==0){x = read();y = read();Extract(Nd+x,Nd+y);printf("%d\n",Nd[y].Xor);}
		if (opt==1) {x = read();y = read();if (!Judge(Nd+x,Nd+y)) {Link(Nd+x,Nd+y);M[x][y] = M[y][x] = 1;}}
		if (opt==2) {x = read();y = read();if (M[x][y]) {Cut(Nd+x,Nd+y);M[x][y] = M[y][x] = 0;}}
		if (opt==3) {x = read();Nd[x].val = read();Splay(Nd+x);}
	}
}

QTREE - Query on a tree

 

You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.

We will ask you to perfrom some instructions of the following form:

  • CHANGE i ti : change the cost of the i-th edge to ti
    or
  • QUERY a b : ask for the maximum edge cost on the path from node a to node b

Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

  • In the first line there is an integer N (N <= 10000),
  • In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between ab of cost c (c <= 1000000),
  • The next lines contain instructions "CHANGE i ti" or "QUERY a b",
  • The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.

Output

For each "QUERY" operation, write one integer representing its result.

Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3

        修改边权,询问链Max。

        放这道题的原因是这道题没有树形态的改变,对于链的询问论文中有写到一种比较简单(十分复杂)的方法,可以不用换根,所以Splay上就可以不用维护标记。

        然而也是因为这个坑了我一天,学完以后发现并没有什么卵用,而且标记下传还十分蛋碎。

        具体方法:先 Access(x),然后在Access(y)的过程中,如果遇到的一颗Splay包含根节点,则当前这个点即为x和y的LCA,然后答案即为y所在Splay的答案和当前节点右儿子的答案。

        这个方法唯一的好处就是,不用维护标记。

        但是如果树的形态不变。。。为什么要用LCT呢。。。

        所以总结。。这种方法好像并没有什么卵用。

        但是代码还是这样写的。。。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 10010;
using namespace std;
int n,belong[N],x,y,s,I,val,head[N],cnt;
char opt[20];
struct data{int x,y,s,next,id;} e[N<<1];
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
struct node *null;
struct node {
	node *L,*R,*Fa;int S,val,Max;
	int Top(){return Fa==null || (Fa->L!=this && Fa->R!=this);}
	void Update(){
		if (this==null) return;
		S = L->S+R->S+1;Max = max(max(L->Max,R->Max),val);
	}
	void Zig(){
		if (this==null) return;
		node *y = Fa,*z = y->Fa;
		if (z->L==y) z->L = this;else if (z->R==y) z->R = this;Fa = z;
		y->L = R;if (R!=null) R->Fa = y;
		R = y;y->Fa = this;y->Update();
	}
	void Zag(){
		if (this==null) return;
		node *y = Fa,*z = y->Fa;
		if (z->L==y) z->L = this;else if (z->R==y) z->R = this;Fa = z;
		y->R = L;if (L!=null) L->Fa = y;
		L = y;y->Fa = this;y->Update();
	}
} Nd[N];
void Insert(int x,int y,int s,int id){
	e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
	e[cnt].id = id;e[cnt].next = head[x];head[x] = cnt;
}
void dfs(int x,int fa){
	for (int i=head[x];i;i=e[i].next)
		if  (e[i].y!=fa) {
			Nd[e[i].y].val = Nd[e[i].y].Max = e[i].s;
			Nd[e[i].y].Fa = Nd+x;
			belong[e[i].id] = e[i].y;
			dfs(e[i].y,x);
		}
}
void Splay(node *x){
	while (!x->Top()){
		node *y = x->Fa,*z = y->Fa;
		if (!y->Top())
			if (y->L==x) if (z->L==y) y->Zig(),x->Zig();else x->Zig(),x->Zag();
			else if (z->R==y) y->Zag(),x->Zag();else x->Zag(),x->Zig();
		else if (y->L==x) x->Zig();else x->Zag();
	}
	x->Update();
}
node *Access(node *x){
	node *y;
	for (y=null;x!=null;y=x,x=x->Fa) {Splay(x);x->R = y;x->Update();}
	return y;
}
void Work(node *x,node *y){
	Access(y);
	for (y=null;x!=null;y=x,x=x->Fa){
		Splay(x);if (x->Fa==null) break;
		x->R = y;x->Update();
	}
	printf("%d\n",max(x->R->Max,y->Max));
}
int main(){
	null = Nd;
	for (int T=read();T;T--){
		n = read();
		for (int i=0;i<=n;i++) Nd[i] = (node) {null,null,null,1,0,0};
		null->S = 0;cnt = 0;
		memset(head,0,sizeof(head));
		for (int i=1;i<n;i++) {
			x = read();y = read();s = read();
			Insert(x,y,s,i);Insert(y,x,s,i);
		}
		dfs(1,-1);
		while (~scanf("%s",opt+1)){
			if (opt[1]=='D') break;
			if (opt[1]=='Q') {
				x = read();y = read();
				Work(Nd+x,Nd+y);
			}
			if (opt[1]=='C') {
				I = read();val = read();
				node *t = Nd+belong[I];
				t->val = val;t->Update();
				Splay(t); 
			}
		}
	}
}
Category: 杂文 | Tags: 笔记 数据结构 LCT | Read Count: 590
Avatar_small
hzq84621 说:
2016年1月13日 13:15

噫,弹飞绵羊标算不是块状链表吗

Avatar_small
meepo 说:
2016年1月13日 16:02

@hzq84621: 难道不是一眼就知道是动态树吗。。

Avatar_small
orzsqc 说:
2016年1月16日 11:41

@Stalker: %小橙子干

Avatar_small
WasteRice 说:
2016年2月26日 19:49

我怎么觉得QTREE好像树剖就行了

Avatar_small
meepo 说:
2016年2月26日 19:57

@WasteRice: 我写这个主要是觉得不用换根可以提取区间很厉害。。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com