「ZJOI2016」大森林 - 扫描线+动态树LCT | Bill Yang's Blog
0%

「ZJOI2016」大森林 - 扫描线+动态树LCT

题目大意

    小Y家里有一个大森林,里面有$n$棵树,编号从$1$到$n$。一开始这些树都只是树苗,只有一个节点,标号为$1$。这些树都有一个特殊的节点,我们称之为生长节点,这些节点有生长出子节点的能力。
    小Y掌握了一种魔法,能让第$l$棵树到第$r$棵树的生长节点长出一个子节点。同时她还能修改第$l$棵树到第$r$棵树的生长节点。她告诉了你她使用魔法的记录,你能不能管理她家的森林,并且回答她的询问呢?


题目分析

很神的一道题,用神奇的虚点可以避免ETT。

将所有操作离线下来:
首先,$0$操作可以看做在全局加点,因为不会询问到不存在的点,所以加了也没关系。而对于$2$操作,将所有点加完了再询问也可以。
对于每个$1$操作建立一个虚点,每个$0$操作的点向距离其最近的$1$操作连边。
初始化的时候虚点向前一个虚点连边,使用$0/1$点权区分虚实点。
将所有$1,2$操作挂在序列对应位置表示一个事件($1$操作拆成两个事件)。

接下来开始按照序列顺序扫描,遇到一个$1$操作的事件,切换虚点连向的点,遇到一个$2$操作回答询问。

为了解释的更易懂,我们模拟一下算法过程。
这是初始情况:

将扫描线平行于时间轴移动,对应意义的点为顶部的红点:

若扫描线触碰到一个$1$询问区间,更改虚边所连接的点:(假设此处更改到$2$)

在扫描的过程中顺便求出询问,若离开询问区间,重新更改虚边的点:

如此重复即可。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>

using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=200005;

struct Tree {
int father,child[2];
bool rev;
int val,sum;
};

struct Link_Cut_Tree {
Tree tree[maxn];
stack<int>S;
#define fa(x) tree[x].father
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define rev(x) tree[x].rev
bool isroot(int index) {
return ls(fa(index))!=index&&rs(fa(index))!=index;
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_down(int index) {
if(!rev(index))return;
swap(ls(index),rs(index));
rev(ls(index))^=1;
rev(rs(index))^=1;
rev(index)=0;
}
void push_up(int index) {
tree[index].sum=tree[ls(index)].sum+tree[rs(index)].sum+tree[index].val;
}
void rotate(int index) {
int father=fa(index),grand=fa(father),side=checkson(index);
if(!isroot(father))tree[grand].child[checkson(father)]=index;
tree[father].child[side]=tree[index].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=index;
tree[index].child[side^1]=father;
fa(index)=grand;
push_up(father);
push_up(index);
}
void splay(int index) {
S.push(index);
for(int i=index; !isroot(i); i=fa(i))S.push(fa(i));
while(!S.empty())push_down(S.top()),S.pop();
for(int father; !isroot(index); rotate(index)) {
father=fa(index);
if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
}
}
int access(int index) {
int son=0;
for(; index; son=index,index=fa(index))splay(index),rs(index)=son,push_up(index);
return son;
}
void reverse(int index) {
access(index);
splay(index);
rev(index)^=1;
}
void link(int x,int y) {
reverse(x);
fa(x)=y;
}
void split(int x,int y) {
reverse(x);
access(y);
splay(y);
}
void cut(int x,int y) {
split(x,y);
ls(y)=fa(x)=0;
}
int query(int x,int y) {
reverse(1);
int sum=0;
access(x),splay(x);sum+=tree[x].sum;
int lca=access(y);splay(y);sum+=tree[y].sum;
access(lca),splay(lca),sum-=2*tree[lca].sum;
return sum;
}
} lct;

int n,m,q=0,cnt=0,size=0,ans[maxn],id[maxn],Left[maxn],Right[maxn];

int newnode(int v) {
lct.tree[++cnt].val=v;
return cnt;
}

struct Option {
int opt,x,from,to,id;
Option(int o=0,int x=0,int f=0,int t=0,int id=0):opt(o),x(x),from(f),to(t),id(id) {}
};

vector<Option> Opt[maxn];

int main() {
n=Get_Int();
m=Get_Int();
id[++size]=newnode(1),Left[size]=1,Right[size]=n;
int last=newnode(0);lct.link(last,id[1]);
for(int i=1; i<=m; i++) {
int opt=Get_Int();
if(opt==0) {
id[++size]=newnode(1),Left[size]=Get_Int(),Right[size]=Get_Int();
lct.link(last,id[size]);
} else if(opt==1) {
int l=Get_Int(),r=Get_Int(),x=Get_Int();
l=max(l,Left[x]),r=min(r,Right[x]);
if(l>r)continue;
int now=newnode(0);lct.link(now,last);
Opt[l].push_back(Option(1,now,last,id[x]));
Opt[r+1].push_back(Option(1,now,id[x],last));
last=now;
} else {
int x=Get_Int(),u=Get_Int(),v=Get_Int();
Opt[x].push_back(Option(2,x,id[u],id[v],++q));
}
}
for(int i=1; i<=n; i++)
for(auto now:Opt[i]) {
if(now.opt==1)lct.cut(now.x,now.from),lct.link(now.x,now.to);
else ans[now.id]=lct.query(now.from,now.to);
}
for(int i=1; i<=q; i++)printf("%d\n",ans[i]);
return 0;
}
姥爷们赏瓶冰阔落吧~