BZOJ 1146 网络管理

Link

小时候写过树状数组套主席树的版本,时空\(O(n\log^2n)\)。众所周知,这个空间复杂度是非常不友好的。 今天翻到jcvb巨神的博客,发现他给了一种非常interesting的做法:值域线段树套区间平衡树。研究一番,写完之后感觉很不错。 # 树状数组套主席树维护DFS序 ## Solution 众所周知,序列上的主席树可以利用可持久化实现时空\(O(n\log n)\)的前缀和,从而解决区间K值问题。 放到树上,如果不带修改,那就可以直接用序列的可持久化线段树方法,从根节点DFS下去,在节点\(u\)的值域线段树的\([l,r]\)区间,维护\(u\)\(root\)路径上值在\([l,r]\)的节点个数。这样,两点\(u,v\)的路径上,值在\([l,r]\)的节点个数\(c(u,v)\),就是\(c(u)+c(v)-c(lca)-c(fa[lca])\)。套用序列的方法查询即可。 现在有了修改,显然不可能暴力重建主席树,因为一次修改会影响子树的所有的点。 等等,一次修改影响子树所有的点?不禁让人思考能否进行区间操作?然后就联想到了DFS序。没错,DFS序就是一个满足子树的所有点是一个区间的序列。 区间操作的两种办法:用兹瓷区间修改的数据结构打标记;或者差分,把区间修改变成单点修改。待修改的树上主席树是通过套一个树状数组,绝对化相对的方法来实现的。这样,线段树就不需要可持久化了,因为本来可持久化是要维护前缀和,但现在树状数组就维护了前缀和。一次修改,会修改\(O(\log n)\)个线段树,每个线段树修改的时间是\(O(\log n)\)。一个点的值至多将在\(O(\log n)\)个线段树出现,粗略地估计总次数,绝对不会超过\(O(\log n)\)。所以得到了一个时空\(O(n\log ^2n)\)的优秀做法。 ## 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
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;
#define S(X,NUMO) seg[X].son[NUMO]
const int MAXN=80010;
const int MAXLOGN=18;
const int MAXRG=MAXN*2;
const int MAXLOGRG=20;
const int INF=522133279;
const int MAXP=12000000;
int nset[MAXN*2],nc=0;
inline int Get(int x)
{
return lower_bound(nset+1,nset+nc,x)-nset;
}
int T[MAXN];int N,Q;
int e[MAXN*2],pre[MAXN*2],id[MAXN],ec=0;
int l2(int x)//log x 取下整
{
int i=0;
while((1<<i)<=x)
++i;
return i-1;
}
void adde(int _f,int _t)
{
e[++ec]=_t;pre[ec]=id[_f];id[_f]=ec;
e[++ec]=_f;pre[ec]=id[_t];id[_t]=ec;
}
int dfs[MAXN],dep[MAXN],dc=0,lin[MAXN],rout[MAXN],fa[MAXN];//BIT用
int mdfs[MAXN*2],ml[MAXN],mr[MAXN],mdc=0;//ST用
//每条边访问一次,而每访问一条边加入2个点 所以总共是2n级别的
void DFS(int pos,int d)
{
dep[pos]=++d;
dfs[++dc]=pos;
mdfs[++mdc]=pos;
lin[pos]=rout[pos]=dc;
ml[pos]=mr[pos]=mdc;
for(int i=id[pos];i;i=pre[i])
if(fa[pos]!=e[i])
{
fa[e[i]]=pos;
DFS(e[i],d);
rout[pos]=max(rout[pos],rout[e[i]]);
mdfs[++mdc]=pos;
mr[pos]=max(mr[pos],mdc);
}
}
int f[MAXN*2][20];//i到i+(2^j)-1 [i开始长度为2^j]的最浅点
void outst()
{
for(int j=0;j<=l2(mdc);j++)
{
printf("2^%d:",j);
for(int i=1;i<=mdc;i++)
printf("%d-%d ",i,f[i][j]);
puts("");
}
}
void ST()
//dfs
{
for(int i=1;i<=mdc;i++)
f[i][0]=mdfs[i];
int endj=l2(mdc),endi,pl,pr,t;
for(int j=1;j<=endj;j++)
{
endi=mdc-(1<<j)+1;
for(int i=1;i<=endi;i++)
{
pl=f[i][j-1];
pr=f[i+(1<<j)-(1<<j>>1)][j-1];
f[i][j]=dep[pl]<dep[pr]?pl:pr;
}
}
}
int LCA(int p1,int p2)
{
p1=ml[p1],p2=ml[p2];
if(p1>p2) swap(p1,p2);
int j=l2(p2-p1+1),ans=-1;
p1=f[p1][j],p2=f[p2-(1<<j)+1][j];
return dep[p1]>dep[p2]?p2:p1;
}
int inp[MAXN][3];
struct SegNode
{
int son[2],cnt;
};
struct BIT
{
int root[MAXN],pc,n;
SegNode seg[MAXP];int TL,TR;//1,N
inline int lowbit(int x){return x&(-x);}
BIT(){pc=0;}
inline void valup(int pos)
{
seg[pos].cnt=0;
if(S(pos,0)) seg[pos].cnt+=seg[S(pos,0)].cnt;
if(S(pos,1)) seg[pos].cnt+=seg[S(pos,1)].cnt;
}
int Acs(int pos,int L,int R,int l,int r)
{
if(!pos)
return 0;
if(L==l && R==r)
return seg[pos].cnt;
else
{
int MID=(L+R)>>1;
if(r<=MID)
return Acs(S(pos,0),L,MID,l,r);
else if(MID+1<=l)
return Acs(S(pos,1),MID+1,R,l,r);
else
return Acs(S(pos,0),L,MID,l,MID)+Acs(S(pos,1),MID+1,R,MID+1,r);
}
}
int Edit(int pos,int L,int R,int goal,int v)
{
int pres=pos?pos:++pc;
seg[pres]=seg[pos];
if(L==R)
seg[pres].cnt+=v;
else
{
int MID=(L+R)>>1;
if(goal<=MID)
S(pres,0)=Edit(S(pos,0),L,MID,goal,v);
else
S(pres,1)=Edit(S(pos,1),MID+1,R,goal,v);
valup(pres);
}
return pres;
}
int Sum(int pos,int l,int r)
//得到树上pos位置的线段树[l,r]区间的cnt
{
if(!pos)
return 0;
int ans=0;
pos=lin[pos];
for(;pos;pos-=lowbit(pos))
ans+=Acs(root[pos],TL,TR,l,r);
return ans;
}
int add(int pos,int goal,int v)
//修改dfs序列中的pos对应的树
{
for(;pos<=n;pos+=lowbit(pos))
root[pos]=Edit(root[pos],TL,TR,goal,v);
}
int Add(int pos,int goal,int v)
//修改pos(树上编号)应的子树的区间
{
add(lin[pos],goal,v);
if(rout[pos]<n)
add(rout[pos]+1,goal,-v);
}
int Que(int p1,int p2,int K)
{
int lca=LCA(p1,p2);
K=dep[p1]+dep[p2]-dep[lca]*2+1-K+1;
if(K<=0)
return -INF;
int L=TL,R=TR,MID=(L+R)>>1,sum;
//int s1,s2,s3;
while(K)
{
if(L==R)
{
return nset[L];
}
MID=(L+R)>>1;
sum=Sum(p1,L,MID)+Sum(p2,L,MID)-Sum(lca,L,MID)-Sum(fa[lca],L,MID);
if(sum<K)
{
K-=sum;
L=MID+1;
}
else R=MID;
}
return INF;
}
void Out()
{
for(int i=1;i<=n;i++)
printf("%d ",Sum(i,TL,TR));
puts("");
}
void OutS()
{
for(int i=1;i<=n;i++)
printf("%d ",Acs(root[i],TL,TR,TL,TR));
puts("");
}
}B;
void InitSeg(int pos)
{
B.Add(pos,Get(T[pos]),1);
for(int i=id[pos];i;i=pre[i])
if(e[i]!=fa[pos])
InitSeg(e[i]);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
scanf("%d%d",&N,&Q);
B.n=N;
for(int i=1;i<=N;i++)
{
scanf("%d",&T[i]);
nset[++nc]=T[i];
}
int t1,t2,t3;
for(int i=1;i<=N-1;i++)
{
scanf("%d%d",&t1,&t2);
adde(t1,t2);
}
DFS(1,0);
dep[0]=INF;
ST();
int *p;
for(int i=1;i<=Q;i++)
{
p=inp[i];
scanf("%d%d%d",&p[0],&p[1],&p[2]);
if(!p[0])
nset[++nc]=p[2];
}
sort(nset+1,nset+1+nc);
nc=unique(nset+1,nset+1+nc)-nset-1;
B.TL=1,B.TR=nc;
InitSeg(1);
for(int i=1;i<=Q;i++)
{
p=inp[i];
if(!p[0])
{
B.Add(p[1],Get(T[p[1]]),-1);
B.Add(p[1],Get(p[2]),1);
T[p[1]]=p[2];
}
else
{
t1=B.Que(p[1],p[2],p[0]);
if(t1!=-INF)
printf("%d\n",t1);
else
puts("invalid request!");
}
}
return 0;
}

线段树套平衡树维护括号序列

Solution

现在考虑优化的话,主要就是要考虑压缩空间,否则太不友好。注意到,空间之所以那么大,是因为把主席树建在了内层,一个点的权值可能出现在\(O(\log n)\)棵线段树中,出现一次就至多带来\(O(\log n)\)个节点,比较浪费。 那么考虑把值域线段树建在外层,那么这一部分的空间就是\(O(n)\)。考虑如何在内层维护整个树。 用DFS序列应该就不好弄了。。涉及到路径,DFS序似乎就无力了。。。 于是祭出大杀器:括号序! 一个树的括号序,指的是每个点在进栈的时候放一个左括号,出栈的时候放一个右括号。 然后把一棵树的括号序写下来,会发现一个惊天大秘密:从第一个括号开始,到\(pos\)的左括号,把匹配的括号删掉,恰好可以得到从根节点到\(pos\)的路径! 于是就可做了: 在值域线段树的每个节点\([l,r]\)挂一个平衡树,平衡树维护所有值被\([l,r]\)覆盖的点的左括号位置和右括号位置。左括号的权值为\(1\),右括号为\(-1\),这样做一下前缀和,就可以得到根节点到一个点的路径上有多少点的值在\([l,r]\)之内了!然后就可以做了。 空间复杂度\(O(n \log n)\)。 ## 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
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#include "lucida"
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;
const int MAXN=80000+11,INF=0x1f1f1f1f,MAXLOG=20;
int n,w[MAXN],nums[MAXN<<1],nc=0,dep[MAXN];
#define alloc(T,c) (T*)malloc((c)*sizeof(T))
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
namespace treap {
struct Node *null,**rec,*Me;
const int P=99929,SIZE=(MAXN<<1)*MAXLOG;
struct Node {
Node *son[2];
int val,cnt,sz,py;
Node():sz(0),py(P) {
son[0]=son[1]=0;
val=-INF;
}
Node(int val,int cnt):val(val),cnt(cnt),sz(cnt),py(rand()%P) {
son[0]=son[1]=null;
}
void Up() {
sz=son[0]->sz+son[1]->sz+cnt;
}
void *operator new(size_t) {
return *rec?*rec--:Me++;
}
void operator delete(void *p) {
*++rec=(Node*)p;
}
}**cer=rec=alloc(Node*,SIZE),*eM=Me=alloc(Node,SIZE),*llun=null=new Node;
struct Treap {
Node *root;
void Trans(Node *&pos,int d) {
Node *s=pos->son[d];
pos->son[d]=s->son[!d];
s->son[!d]=pos;
pos->Up();
(pos=s)->Up();
}
int Adjust(Node *&pos) {
int d=pos->son[0]->py>pos->son[1]->py;
return pos->py>pos->son[d]->py?(Trans(pos,d),!d):-1;
}
void Fall(Node *&pos) {
int d=Adjust(pos);
if(d==-1) {
delete pos;
pos=null;
} else {
Fall(pos->son[d]);
pos->Up();
}
}
void Delete(Node *&pos,int val) {
if(pos->val==val) {
pos->py=P;
Fall(pos);
} else {
Delete(pos->son[pos->val<val],val);
pos->Up();
}
}
void Insert(Node *&pos,Node *goal) {
if(pos==null)
pos=goal;
else {
Insert(pos->son[pos->val<goal->val],goal);
pos->Up();//adjust不一定会adjust啊...
Adjust(pos);
}
}
typedef Node *Iter;
Treap():root(null){}
int Rank(int v) {
Node *pos=root;int res=0;
while(pos!=null) {
if(pos->val<=v) {
res+=pos->son[0]->sz+pos->cnt;
pos=pos->son[1];
} else
pos=pos->son[0];
}
return res;
}
void Delete(int val) {
Delete(root,val);
}
void Insert(int val,int cnt) {
Insert(root,new Node(val,cnt));
}
};
}using treap::Treap;
namespace segtree {
const int SIZE=MAXN<<2;
struct Node {
Node *son[2];
Treap idx;
Node() {
son[0]=son[1]=0;
}
void *operator new(size_t) {
static Node *Pool=alloc(Node,SIZE);
return Pool++;
}
};
struct SegTree {
typedef Node *Iter;
Node *root;
int L,R;
void Build(Node *&pos,int L,int R) {
pos=new Node;
if(L!=R) {
int Mid=(L+R)>>1;
Build(pos->son[0],L,Mid);
Build(pos->son[1],Mid+1,R);
}
}
void Point(Node *pos,int L,int R,int goal,int v,int cnt) {
if(v>0) pos->idx.Insert(v,cnt);
else pos->idx.Delete(-v);
if(L!=R) {
int Mid=(L+R)>>1;
if(goal<=Mid)
Point(pos->son[0],L,Mid,goal,v,cnt);
else
Point(pos->son[1],Mid+1,R,goal,v,cnt);
}
}
SegTree(){}
SegTree(int L,int R):L(L),R(R) {
Build(root,L,R);
}
void Insert(int pos,int idx,int cnt) {
Point(root,L,R,pos,idx,cnt);
}
void Delete(int pos,int idx) {
Point(root,L,R,pos,-idx,0);
}
};
}using segtree::SegTree;
struct Edge {
int to;Edge *pre;
Edge(int to,Edge *pre):to(to),pre(pre){}
void *operator new(size_t) {
static Edge *Me=alloc(Edge,MAXN<<1);
return Me++;
}
}*G[MAXN];
void Adde(int f,int t) {
G[f]=new Edge(t,G[f]);
G[t]=new Edge(f,G[t]);
}
namespace _ST_ {
int mdfs[MAXN<<1],lbd[MAXN],rbd[MAXN],mdc,log_2[MAXN<<1],f[MAXLOG][MAXN<<1];
void ST() {
log_2[0]=-1;
for(int i=1;i<=mdc;++i) {
f[0][i]=mdfs[i];
log_2[i]=log_2[i>>1]+1;
}
for(int lg=1,elg=log_2[mdc];lg<=elg;++lg)
for(int pl,pr,i=1,ei=mdc-(1<<lg)+1;i<=ei;++i)
f[lg][i]=dep[pl=f[lg-1][i]]<dep[pr=f[lg-1][i+(1<<lg>>1)]]?pl:pr;
}
int LCA(int p1,int p2) {
p1=lbd[p1],p2=lbd[p2];
if(p1>p2) swap(p1,p2);
int lg=log_2[p2-p1+1],pl,pr;
return dep[pl=f[lg][p1]]<dep[pr=f[lg][p2-(1<<lg)+1]]?pl:pr;
}
}
using _ST_::LCA;
int dfs[MAXN<<1],dc,lpt[MAXN],rpt[MAXN],fa[MAXN];
void DFS(int pos) {
using namespace _ST_;
dfs[++dc]=pos;lpt[pos]=dc;
mdfs[++mdc]=pos;lbd[pos]=mdc;
for(Edge *e=G[pos];e;e=e->pre)
if(e->to!=fa[pos]) {
fa[e->to]=pos;
dep[e->to]=dep[pos]+1;
DFS(e->to);
mdfs[++mdc]=pos;
}
dfs[++dc]=pos;rpt[pos]=dc;
rbd[pos]=mdc;
}
SegTree seg;
void Build() {
DFS(1);
new(&seg) SegTree(1,nc);
_ST_::ST();
for(int i=1;i<=n;++i) {
seg.Insert(w[i],lpt[i],1);
seg.Insert(w[i],rpt[i],-1);
}
}
int Query(int p1,int p2,int K) {
int lca=LCA(p1,p2);
K=dep[p1]+dep[p2]-dep[lca]*2+1-K+1;
if(K<=0)
return 0;
else {
int L=1,R=nc;
SegTree::Iter pos=seg.root;
while(L!=R) {
int Mid=(L+R)>>1;
Treap &idx=pos->son[0]->idx;
int d=idx.Rank(lpt[p1])+idx.Rank(lpt[p2])-idx.Rank(lpt[lca])-idx.Rank(lpt[fa[lca]]);
if(K<=d) {
R=Mid;
pos=pos->son[0];
} else {
K-=d;
L=Mid+1;
pos=pos->son[1];
}
}
return L;
}
return 23333;
}
void Change(int pos,int newv) {
seg.Delete(w[pos],lpt[pos]);
seg.Delete(w[pos],rpt[pos]);
w[pos]=newv;
seg.Insert(w[pos],lpt[pos],1);
seg.Insert(w[pos],rpt[pos],-1);
}
int main() {
freopen("input","r",stdin);
srand(0x1f1f1f1f);
int Q;is>>n>>Q;
for(int i=1;i<=n;++i) {
is>>w[i];
nums[++nc]=w[i];//=i?????????w[i]????
}
for(int i=1;i<=n-1;++i) {
int x,y;
is>>x>>y;
Adde(x,y);
}
static struct {int k,a,b;}opt[MAXN];
for(int i=1;i<=Q;++i) {
is>>opt[i].k>>opt[i].a>>opt[i].b;
if(!opt[i].k)
nums[++nc]=opt[i].b;
}
sort(nums+1,nums+1+nc);
nc=unique(nums+1,nums+1+nc)-nums-1;
for(int i=1;i<=n;++i)
w[i]=ref(w[i]);
Build();
for(int i=1;i<=Q;++i)
if(opt[i].k) {
int Ans=Query(opt[i].a,opt[i].b,opt[i].k);
if(Ans) os<<nums[Ans]<<'\n';
else os<<"invalid request!"<<'\n';
} else {
Change(opt[i].a,ref(opt[i].b));
}
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利