【题目描述】
菊菊是一个码农,他很喜欢码一些高(e)级(xin)数据结构。
有一天,菊菊在打网赛时遇到了 wfj。wfj 觉得他很有前途,可以做下一代码农大神。
于是乎,wfj 给菊菊出了一道题,来检验一下菊菊的代码能力:
这是一个简单的数据结构题,你只需在树上维护如下几个简单操作:
type=1:树上单点修改,给定 x,v,把 x 的值改为 v。
type=2:树上子树修改,给定 x,v,把 x 子树上的所有数加上 v。
type=3:树上路径修改,给定 x,y,v,把 x 到 y 路径上的所有数加上 v。
type=4:树上单点查询,给定 x,查询 x 的值。
type=5:树上子树查询,给定 x,查询子树 x 的和。
type=6:树上路径查询,给定 x,y,查询 x 到 y 路径上数的和。
wfj 想了很久,觉得这题太容易了,没有任何意义。所以,在上面这些操作完成以后,
他还要求菊菊完成另外一些操作:
type=7:树上子树查询区间第 k 小,给定 x,k,求 x 子树上第 k 小值。
type=8:树上子树查询比给定数小的数的个数,给定 x,k,求 x 子树上比 k 小的
数的个数。
type=9:树上路径查询区间第 k 小,给定 x,y,k(huaji.jpg),求 x 到 y 路径
上的区间第 k 小。
type=10:树上路径查询比给定数小的数的个数,给定 x,y,k,求 x 到 y 路径上
比 k 小的数的个数。
wfj 又想了很久,觉得这题可以了。然而这时,菊菊对他说:“这也太容易了吧!我半
小时就能 AC!”于是 wfj 怒了。他想:这个 sb,我再加一问,不信他写 得出。于是,wfj
加了最后一问:
对于这棵树,请求出这棵树中<=k 的路径条数,其中,k 为给定值。
菊菊是一个智商特别高的编程天才,他身上带了电脑,但他这回做不出来了,所以他委
托你——一位植树工人来完成这个游戏。你能帮帮他吗?
【输入数据】
第一行包括两个整数 N,表示这颗树的结点数。
接下来一行包括 N 个整数 Ai,表示 N 个结点初始权值。
接下来有 N-1 行,每行两个数 x,y,表示 x 和 y 之间有边相连。
接下来一行包括一个整数 M1,表示第一问的询问数。
接下来 M1 行每行包括一个数 type,后接几个数:
type=1:输入 x,v。
type=2:输入 x,v。
type=3:输入 x,y,v。
type=4:输入 x。
type=5:输入 x。
type=6:输入 x,y。
接下来一行一个数 M2,表示第二问的询问数。
接下来 M2 行:
type=7:输入 x,k。
type=8:输入 x,k。
type=9:输入 x,y,k。
type=10:输入 x,y,k。
最后一行一个整数 k。
以上输入意义见题中所述。
【输出数据】
对于每个查询操作,每行输出一个答案。
最后一行为最后一问的答案。
【输入样例 1】
5
00000
12
23
24
35
6
134
43
213
3342
54
634
4
722
835
9342
10 4 5 2
3
【输出样例 1】
4
5
19
5
1
5
0
10
【输入样例 2、3】
见下发样例文件。
【输出样例 2、3】
见下发样例文件。
【数据约定】
对于 30%的数据,满足 N<=3000。M1,M2<=3000。
对于 100%的数据,满足 N<=100000。M1,M2<=100000。
(ps:简单送肉板子题,应该有人 AC 吧。。)
正解：树链剖分+线段树+主席树+点分治。
全部是板子，出了这道题为了训练代码能力。考场上无人写出正解，1人写对30分暴力。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define N (100010) 14 #define inf (1<<30) 15 #define lson (x<<1) 16 #define rson (x<<1|1) 17 #define il inline 18 #define RG register 19 #define ll long long 20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 21 22 using namespace std; 23 24 struct edge 25 { 26 ll nt,to; 27 } g[2*N]; 28 29 ll head[N],top[N],fa[N],son[N],size[N],dep[N],dfn[N],pos[N],cur[N],vis[N],dis[N],a[N],W[N],num[N],hsh[N],root1[N],root2[N],lazy[4*N],sum[4*N],sum1[20*N],sum2[20*N],ls1[20*N],rs1[20*N],ls2[20*N],rs2[20*N],n,ssz,sz,sz1,sz2,cnt,tot,root,limit,ans; 30 31 il ll gi() 32 { 33 RG ll x=0,q=1; 34 RG char ch=getchar(); 35 while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); 36 if (ch=='-') q=-1,ch=getchar(); 37 while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); 38 return q*x; 39 } 40 41 il void insert(RG ll from,RG ll to) 42 { 43 g[++sz]=(edge) {head[from],to},head[from]=sz; 44 return; 45 } 46 47 il void dfs1(RG ll x,RG ll p) 48 { 49 dep[x]=dep[p]+1,fa[x]=p,size[x]=1; 50 RG ll v,mx=0; 51 for (RG ll i=head[x]; i; i=g[i].nt) 52 { 53 v=g[i].to; 54 if (v==p) continue; 55 dfs1(v,x); 56 size[x]+=size[v]; 57 if (size[mx]<=size[v]) mx=v; 58 } 59 son[x]=mx; 60 return; 61 } 62 63 il void dfs2(RG ll x,RG ll p,RG ll a) 64 { 65 top[x]=a,dfn[x]=++cnt,pos[cnt]=x; 66 if (son[x]) dfs2(son[x],x,a); 67 RG ll v; 68 for (RG ll i=head[x]; i; i=g[i].nt) 69 { 70 v=g[i].to; 71 if (v==p || v==son[x]) continue; 72 dfs2(v,x,v); 73 } 74 return; 75 } 76 77 il void down(RG ll x,RG ll l,RG ll r) 78 { 79 RG ll mid=(l+r)>>1; 80 sum[lson]+=lazy[x]*(mid-l+1),sum[rson]+=lazy[x]*(r-mid); 81 lazy[lson]+=lazy[x],lazy[rson]+=lazy[x],lazy[x]=0; 82 return; 83 } 84 85 il void build(RG ll x,RG ll l,RG ll r) 86 { 87 if (l==r) 88 { 89 sum[x]=a[pos[l]]; 90 return; 91 } 92 RG ll mid=(l+r)>>1; 93 build(lson,l,mid); 94 build(rson,mid+1,r); 95 sum[x]=sum[lson]+sum[rson]; 96 return; 97 } 98 99 il void update(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll v,RG ll flag) 100 { 101 if (xl<=l && r<=xr) 102 { 103 if (flag) sum[x]+=(r-l+1)*v,lazy[x]+=v; 104 else sum[x]=v; 105 return; 106 } 107 if (lazy[x]) down(x,l,r); 108 RG ll mid=(l+r)>>1; 109 if (xr<=mid) update(lson,l,mid,xl,xr,v,flag); 110 else if (xl>mid) update(rson,mid+1,r,xl,xr,v,flag); 111 else 112 { 113 update(lson,l,mid,xl,mid,v,flag); 114 update(rson,mid+1,r,mid+1,xr,v,flag); 115 } 116 sum[x]=sum[lson]+sum[rson]; 117 return; 118 } 119 120 il ll query(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr) 121 { 122 if (xl<=l && r<=xr) return sum[x]; 123 if (lazy[x]) down(x,l,r); 124 RG ll mid=(l+r)>>1; 125 if (xr<=mid) return query(lson,l,mid,xl,xr); 126 else if (xl>mid) return query(rson,mid+1,r,xl,xr); 127 else return query(lson,l,mid,xl,mid)+query(rson,mid+1,r,mid+1,xr); 128 } 129 130 il void change(RG ll u,RG ll v,RG ll w) 131 { 132 while (top[u]!=top[v]) 133 { 134 if (dep[top[u]]<dep[top[v]]) swap(u,v); 135 update(1,1,n,dfn[top[u]],dfn[u],w,1); 136 u=fa[top[u]]; 137 } 138 if (dep[u]>dep[v]) swap(u,v); 139 update(1,1,n,dfn[u],dfn[v],w,1); 140 return; 141 } 142 143 il ll Query(RG ll u,RG ll v) 144 { 145 RG ll res=0; 146 while (top[u]!=top[v]) 147 { 148 if (dep[top[u]]<dep[top[v]]) swap(u,v); 149 res+=query(1,1,n,dfn[top[u]],dfn[u]); 150 u=fa[top[u]]; 151 } 152 if (dep[u]>dep[v]) swap(u,v); 153 res+=query(1,1,n,dfn[u],dfn[v]); 154 return res; 155 } 156 157 il ll lca(RG ll u,RG ll v) 158 { 159 while (top[u]!=top[v]) 160 { 161 if (dep[top[u]]<dep[top[v]]) swap(u,v); 162 u=fa[top[u]]; 163 } 164 return dep[u]>dep[v] ? v : u; 165 } 166 167 il void kth1build(RG ll x,RG ll &y,RG ll l,RG ll r,RG ll v) 168 { 169 sum1[y=++sz1]=sum1[x]+1,ls1[y]=ls1[x],rs1[y]=rs1[x]; 170 if (l==r) return; 171 RG ll mid=(l+r)>>1; 172 if (v<=mid) kth1build(ls1[x],ls1[y],l,mid,v); 173 else kth1build(rs1[x],rs1[y],mid+1,r,v); 174 return; 175 } 176 177 il ll kth1query1(RG ll x,RG ll y,RG ll k) 178 { 179 RG ll l=1,r=tot,mid,tmp; 180 while (l<r) 181 { 182 mid=(l+r)>>1,tmp=sum1[ls1[y]]-sum1[ls1[x]]; 183 if (k<=tmp) r=mid,x=ls1[x],y=ls1[y]; 184 else l=mid+1,k-=tmp,x=rs1[x],y=rs1[y]; 185 } 186 return hsh[l]; 187 } 188 189 il ll kth1query2(RG ll x,RG ll y,RG ll k) 190 { 191 if (!k) return 0; 192 RG ll l=1,r=tot,mid,ans=0; 193 while (l<r) 194 { 195 mid=(l+r)>>1; 196 if (k<=mid) r=mid,x=ls1[x],y=ls1[y]; 197 else 198 { 199 ans+=sum1[ls1[y]]-sum1[ls1[x]]; 200 l=mid+1,x=rs1[x],y=rs1[y]; 201 } 202 } 203 return ans+sum1[y]-sum1[x]; 204 } 205 206 il void kth2build(RG ll x,RG ll &y,RG ll l,RG ll r,RG ll v) 207 { 208 sum2[y=++sz2]=sum2[x]+1,ls2[y]=ls2[x],rs2[y]=rs2[x]; 209 if (l==r) return; 210 RG ll mid=(l+r)>>1; 211 if (v<=mid) kth2build(ls2[x],ls2[y],l,mid,v); 212 else kth2build(rs2[x],rs2[y],mid+1,r,v); 213 return; 214 } 215 216 il ll kth2query1(RG ll u,RG ll v,RG ll k) 217 { 218 RG ll Lca=lca(u,v),l=1,r=tot,mid,tmp; 219 RG ll a=root2[dfn[u]],b=root2[dfn[v]]; 220 RG ll c=root2[dfn[Lca]],d=root2[dfn[fa[Lca]]]; 221 while (l<r) 222 { 223 mid=(l+r)>>1,tmp=sum2[ls2[a]]+sum2[ls2[b]]-sum2[ls2[c]]-sum2[ls2[d]]; 224 if (k<=tmp) r=mid,a=ls2[a],b=ls2[b],c=ls2[c],d=ls2[d]; 225 else k-=tmp,l=mid+1,a=rs2[a],b=rs2[b],c=rs2[c],d=rs2[d]; 226 } 227 return hsh[l]; 228 } 229 230 il ll kth2query2(RG ll u,RG ll v,RG ll k) 231 { 232 if (!k) return 0; 233 RG ll Lca=lca(u,v),l=1,r=tot,mid,ans=0; 234 RG ll a=root2[dfn[u]],b=root2[dfn[v]],c=root2[dfn[Lca]],d=root2[dfn[fa[Lca]]]; 235 while (l<r) 236 { 237 mid=(l+r)>>1; 238 if (k<=mid) r=mid,a=ls2[a],b=ls2[b],c=ls2[c],d=ls2[d]; 239 else 240 { 241 ans+=sum2[ls2[a]]+sum2[ls2[b]]-sum2[ls2[c]]-sum2[ls2[d]],l=mid+1; 242 a=rs2[a],b=rs2[b],c=rs2[c],d=rs2[d]; 243 } 244 } 245 return ans+sum2[a]+sum2[b]-sum2[c]-sum2[d]; 246 } 247 248 il void dfs3(RG ll x) 249 { 250 kth2build(root2[dfn[fa[x]]],root2[dfn[x]],1,tot,num[dfn[x]]); 251 for (RG ll i=head[x]; i; i=g[i].nt) 252 { 253 RG ll v=g[i].to; 254 if (v==fa[x]) continue; 255 dfs3(v); 256 } 257 return; 258 } 259 260 il void getroot(RG ll x,RG ll p) 261 { 262 size[x]=1,son[x]=0; 263 for (RG ll i=head[x]; i; i=g[i].nt) 264 { 265 RG ll v=g[i].to; 266 if (vis[v] || v==p) continue; 267 getroot(v,x); 268 size[x]+=size[v]; 269 son[x]=max(son[x],size[v]); 270 } 271 son[x]=max(son[x],son[0]-size[x]); 272 if (son[x]<son[root]) root=x; 273 return; 274 } 275 276 il void getdis(RG ll x,RG ll p) 277 { 278 cur[++ssz]=dis[x]; 279 for (RG ll i=head[x]; i; i=g[i].nt) 280 { 281 RG ll v=g[i].to; 282 if (vis[v] || v==p) continue; 283 dis[v]=dis[x]+1; 284 getdis(v,x); 285 } 286 return; 287 } 288 289 il ll cont(RG ll x,RG ll mit) 290 { 291 RG ll res=0; 292 dis[x]=mit,ssz=0; 293 getdis(x,0); 294 sort(cur+1,cur+ssz+1); 295 for (RG ll l=1,r=ssz; l<r;) 296 if (cur[l]+cur[r]<=limit) res+=(r-l++); 297 else r--; 298 return res; 299 } 300 301 il void solve(RG ll x) 302 { 303 vis[x]=1; 304 ans+=cont(x,0); 305 for (RG ll i=head[x]; i; i=g[i].nt) 306 { 307 RG ll v=g[i].to; 308 if (vis[v]) continue; 309 ans-=cont(v,1),root=0,son[0]=size[v]; 310 getroot(v,0),solve(root); 311 } 312 return; 313 } 314 315 il void work() 316 { 317 n=gi(); 318 RG ll m1,m2,u,v,w,x,k,type; 319 for (RG ll i=1; i<=n; ++i) a[i]=gi(); 320 for (RG ll i=1; i<n; ++i) 321 { 322 u=gi(),v=gi(); 323 insert(u,v),insert(v,u); 324 } 325 dfs1(1,0),dfs2(1,0,1); 326 build(1,1,n); 327 m1=gi(); 328 for (RG ll i=1; i<=m1; ++i) 329 { 330 type=gi(); 331 if (type==1) 332 { 333 x=gi(),w=gi(); 334 update(1,1,n,dfn[x],dfn[x],w,0); 335 } 336 if (type==2) 337 { 338 x=gi(),w=gi(); 339 update(1,1,n,dfn[x],dfn[x]+size[x]-1,w,1); 340 } 341 if (type==3) 342 { 343 u=gi(),v=gi(),w=gi(); 344 change(u,v,w); 345 } 346 if (type==4) 347 { 348 x=gi(); 349 printf("%lld ",query(1,1,n,dfn[x],dfn[x])); 350 } 351 if (type==5) 352 { 353 x=gi(); 354 printf("%lld ",query(1,1,n,dfn[x],dfn[x]+size[x]-1)); 355 } 356 if (type==6) 357 { 358 u=gi(),v=gi(); 359 printf("%lld ",Query(u,v)); 360 } 361 } 362 for (RG ll i=1; i<=n; ++i) num[i]=W[i]=query(1,1,n,i,i); 363 sort(num+1,num+n+1); 364 hsh[tot=1]=num[1]; 365 for (RG ll i=2; i<=n; ++i) if (num[i]>num[i-1]) hsh[++tot]=num[i]; 366 for (RG ll i=1; i<=n; ++i) num[i]=lower_bound(hsh+1,hsh+tot+1,W[i])-hsh; 367 for (RG ll i=1; i<=n; ++i) kth1build(root1[i-1],root1[i],1,tot,num[i]); 368 dfs3(1); 369 m2=gi(); 370 for (RG ll i=1; i<=m2; ++i) 371 { 372 type=gi(); 373 if (type==7) 374 { 375 x=gi(),k=gi(); 376 printf("%lld ",kth1query1(root1[dfn[x]-1],root1[dfn[x]+size[x]-1],k)); 377 } 378 if (type==8) 379 { 380 x=gi(),k=gi(); 381 if (k>hsh[tot]) k=tot; 382 else if (k<hsh[1]) k=0; 383 else k=upper_bound(hsh+1,hsh+tot+1,k)-hsh-1; 384 printf("%lld ",kth1query2(root1[dfn[x]-1],root1[dfn[x]+size[x]-1],k)); 385 } 386 if (type==9) 387 { 388 u=gi(),v=gi(),k=gi(); 389 printf("%lld ",kth2query1(u,v,k)); 390 } 391 if (type==10) 392 { 393 u=gi(),v=gi(),k=gi(); 394 if (k>hsh[tot]) k=tot; 395 else if (k<hsh[1]) k=0; 396 else k=upper_bound(hsh+1,hsh+tot+1,k)-hsh-1; 397 printf("%lld ",kth2query2(u,v,k)); 398 } 399 } 400 limit=gi(); 401 ans=0,root=0,son[0]=n; 402 getroot(1,0); 403 solve(root); 404 printf("%lld ",ans); 405 return; 406 } 407 408 int main() 409 { 410 File("structure"); 411 work(); 412 return 0; 413 }