各类莫队讲解+ WC2013-糖果公园

题目链接

这是一篇讲解莫队以及这个题的文章。

1. 莫队

有一些区间询问问题,当得到了[l,r]的答案时,可以O(1)的得到[l,r-1],[l,r+1],[l-1,r],[l+1,r]的答案。

对于这种问题,我们有一种很显然的通过移动l,r指针的暴力。

但是这样面对[1,1],[n,n]循环的数据,会卡到O(qn) 的最坏复杂度。

怎么办呢?

这个莫队算法,就是莫涛队长想出来的优化。

首先把区间按照L/s分块,其中s是块大小。

就是把询问按照L/s从小到大排序,如果相等按R排序。

接下来用上面那个暴力。

时间复杂度为O(qs+n2s)O(qs+\frac{n^2}{s})(假设nq同阶)

s=ns=\sqrt{n}时取到最小值O(nn)O(n\sqrt{n})

常数很优秀。

2.带修改莫队

这里的修改是指单点修改。

记录t为当前是第几次修改后。

排序以后也可以t指针也可以O(1)O(1)移动。

还是分块,设块大小为s,按照左端点块编号-右端点块编号-t 三关键字排序,

然后移动3个指针。

时间复杂度O(ns+n3s2)O(ns+\frac{n^3}{s^2})

s=n23s=n^\frac{2}{3}时取到最小值O(n53)O(n^\frac{5}{3})

常数同样优秀。

3.树上莫队

也就是询问树上一条链的答案。

首先对树进行DFS,每个点入一个时间戳,出一个时间戳。得到每个点入和出的时间戳(in[i],out[i]),以及第i个时间戳是哪个点。

例如:

树上莫队

从1开始DFS,得到的时间戳是:in=[1,2,8,3,5],out=[10,7,9,4,6],标记顺序是[1,2,4,4,5,5,2,3,3,1]

我们定义,一个询问[l,r]表示询问所有 l到r这一段标记里,恰好出现了一次的节点的答案。

比如[1,5]就是询问1251-2-5这条路径的答案。

当u和v是同节点,则询问[in[u],in[u]]就可以了。

当v在u的子树里面,我们就可以询问[in[u],in[v]]区间,可以发现不在这条路径上的一定出现了0/2次,在这条路径上的一定出现了1次。

u在v子树中就相反。

否则,显然[in[u],out[u]],[in[v],out[v]]不相交。

假设out[u]<in[v],那么我们可以询问[out[u],in[v]]。此时除了LCA以外,这条路径上的节点恰好出现了一次。

再加上LCA的贡献就可以了。

否则就询问[out[v],in[u]]即可。

4. 树上带修改莫队

就是2+3.

WC 2013 糖果公园(代码)

这题是个树上带修改莫队。

代码:

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
/*
Author: CNYALI_LK
LANG: C++
PROG: luogu4074.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
ll in[102424],out[102424],is[204848],t,dep[102424];
ll to[233333],lst[204847],beg[102423],e;
ll fa[102424][20];
void dfs(ll x,ll f){
fa[x][0]=f;
dep[x]=dep[f]+1;
for(ll i=1;i<20;++i)fa[x][i]=fa[fa[x][i-1]][i-1];
is[in[x]=++t]=x;
for(ll i=beg[x];i;i=lst[i])if(to[i]!=f){
dfs(to[i],x);
}
is[out[x]=++t]=x;
}
void add(ll u,ll v){
to[++e]=v;
lst[e]=beg[u];
beg[u]=e;
/*------------------------*/
to[++e]=u;
lst[e]=beg[v];
beg[v]=e;
}
ll block;
struct _ask{
ll l,r,id,lb,_add,T,rb;
};
_ask ask[102424];
ll lca(ll u,ll v){
if(dep[u]<dep[v])swap(u,v);
for(ll i=19;~i;--i)if(dep[u]-(1<<i)>=dep[v]){
u=fa[u][i];
}
for(ll i=19;~i;--i)if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}
if(u!=v){
u=fa[u][0];v=fa[v][0];
}
return u;
}
ll cmp(_ask a,_ask b){return a.lb<b.lb||a.lb==b.lb&&a.rb<b.rb||a.lb==b.lb&&a.rb==b.rb&&a.T<b.T;}
ll _is[102424],cnt[102424],tot,ans[102424];
ll V[102424],w[102424],c[102424];
void ds(ll x){
if(_is[x]){
tot-=w[cnt[c[x]]]*V[c[x]];
--cnt[c[x]];
}
else{
tot+=w[++cnt[c[x]]]*V[c[x]];
}
_is[x]^=1;
}
ll cTo[102424],cFr[102424],pt[102424];
void rem(ll x){
if(_is[pt[x]]){
ds(pt[x]);
c[pt[x]]=cFr[x];
ds(pt[x]);
}
else
c[pt[x]]=cFr[x];
}
void add(ll x){
if(_is[pt[x]]){
ds(pt[x]);
c[pt[x]]=cTo[x];
ds(pt[x]);
}
else
c[pt[x]]=cTo[x];
}
int main(){
#ifdef cnyali_lk
freopen("luogu4074.in","r",stdin);
freopen("luogu4074.out","w",stdout);
#endif
ll n=read(),m=read(),q=0,u,v,_q=read();
for(ll i=1;i<=m;++i)V[i]=read();
for(ll i=1;i<=n;++i)w[i]=read();
for(ll i=1;i<n;++i){
add(read(),read());
}
dfs(1,0);
// for(ll i=1;i<=t;++i)printf("%lld%c",is[i],i==t?'\n':',');
block=(ll)ceil(pow(t,2./3));
for(ll i=1;i<=n;++i)c[i]=read();
ll T=0;
for(ll i=1;i<=_q;++i){
if(!read()){
pt[++T]=read();
cFr[T]=c[pt[T]];
cTo[T]=read();
c[pt[T]]=cTo[T];
}
else{
ask[++q].id=q;
ask[q].T=T;
u=read();v=read();
if(u==v){
ask[q].lb=ask[q].rb=(ask[q].l=ask[q].r=in[u])/block;
ask[q]._add=0;
}
else
if(in[u]<in[v]&&out[v]<out[u]){
ask[q].lb=(ask[q].l=in[u])/block;
ask[q].rb=(ask[q].r=in[v])/block;
ask[q]._add=0;
}
else if(in[u]>in[v]&&out[v]>out[u]){
ask[q].lb=(ask[q].l=in[v])/block;
ask[q].rb=(ask[q].r=in[u])/block;
ask[q]._add=0;
}
else{
if(out[u]>in[v]){
swap(u,v);
}
ask[q].lb=(ask[q].l=out[u])/block;
ask[q].rb=(ask[q].r=in[v])/block;
ask[q]._add=lca(u,v);
}
}
}
// for(ll i=1;i<=q;++i)printf("%lld %lld %lld %lld\n",ask[i].l,ask[i].r,ask[i].T,ask[i]._add);
sort(ask+1,ask+q+1,cmp);
ll l=1,r=t;
for(ll i=1;i<=q;++i){
while(T>ask[i].T){ rem(T);--T; }
while(T<ask[i].T){ add(++T); }
while(l<ask[i].l){
ds(is[l]);
++l;
}
while(l>ask[i].l){
ds(is[--l]);
}
while(r>ask[i].r){
ds(is[r]);
--r;
}
while(r<ask[i].r){
ds(is[++r]);
}
if(ask[i]._add)ds(ask[i]._add);
ans[ask[i].id]=tot;
if(ask[i]._add)ds(ask[i]._add);
}
for(ll i=1;i<=q;++i)printf("%lld\n",ans[i]);
return 0;
}
文章目录
  1. 1. 1. 莫队
  2. 2. 2.带修改莫队
  3. 3. 3.树上莫队
  4. 4. 4. 树上带修改莫队
  5. 5. WC 2013 糖果公园(代码)
|