BZOJ3730 震波

---

Description

在一片土地上有N個城市，通過N-1條無向邊互相連接，形成一棵樹的結構，相鄰兩個城市的距離為1，其中第i個城市的價值為value[i]。
不幸的是，這片土地常常發生地震，并且隨著時代的發展，城市的價值也往往會發生變動。
接下來你需要在線處理M次操作：
0 x k 表示發生了一次地震，震中城市為x，影響范圍為k，所有與x距離不超過k的城市都將受到影響，該次地震造成的經濟損失為所有受影響城市的價值和。
1 x y 表示第x個城市的價值變成了y。
為了體現程序的在線性，操作中的x、y、k都需要異或你程序上一次的輸出來解密，如果之前沒有輸出，則默認上一次的輸出為0。

Input

第一行包含兩個正整數N和M。
第二行包含N個正整數，第i個數表示value[i]
接下來N-1行，每行包含兩個正整數u、v，表示u和v之間有一條無向邊。
接下來M行，每行包含三個數，表示M次操作。

Output

包含若干行，對于每個詢問輸出一行一個正整數表示答案。

Sample Input

8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

Sample Output

11100101

HINT

1<=N,M<=100000
1<=u,v,x<=N
1<=value[i],y<=10000
0<=k<=N-1

---

動態點分治

噗噗噗惡習死了

首先我們是肯定需要求出兩點間的路徑的，然后就可以上倍增LCA的板子
然后開始考慮怎么維護答案

如果不考慮修改
每次詢問的答案可以用怎樣的形式來統計呢？
因為我們維護一個點的字樹信息很方便，所以就可以先用樹狀數組維護一下一個子樹里的信息，以距離為下標，點權直接單點加上就行了

現在考慮怎么統計子樹外邊的貢獻，首先我們可以跳到點分樹上的prt節點上，然后求出prt到當前節點u的距離len，用查詢距離k減去len，查詢在prt的子樹里邊有多少距離小于等于k-len的點就可以了，但是我們發現在u的子樹內的一部分節點會被重復計算，所以我們需要另開一個樹狀數組來維護重復的貢獻，在這個樹狀數組里邊只記錄在u的子樹中的額外貢獻

現在考慮吧修改加上，我們從修改節點x這個點開始，不停向prt跳，然后我們這里可以把每一個原來是val[x]的貢獻換成y的貢獻，簡而言之就是加上y-val[x]，然后跟查詢差不多，只不過反向維護一下就好了

然后細節一大堆，主要就是跳prt維護的細節

---

#include<bits/stdc++.h> using namespace std; #define N 500010 inline int read(){int ans=0,w=1;char c=getchar();while(!isdigit(c)&&c!='-')c=getchar();if(c=='-')w=-1,c=getchar();while(isdigit(c))ans=(ans<<1)+(ans<<3)+c-'0',c=getchar();return ans*w; } int n,m,lastans=0,val[N],Log[N]; struct Edge{int v,next;Edge(){}Edge(int v,int next):v(v),next(next){} }E[N<<1]; int head[N],tot=0; void add(int u,int v){E[++tot]=Edge(v,head[u]);head[u]=tot; } int dep[N]={0},Fa[N][21]; void getFa(int u,int fa){Fa[u][0]=fa;dep[u]=dep[fa]+1;for(int i=1;i<=20;i++)Fa[u][i]=Fa[Fa[u][i-1]][i-1];for(int i=head[u];i;i=E[i].next){int v=E[i].v;if(v==fa)continue;getFa(v,u);} } int Lca(int x,int y){if(dep[x]<dep[y])swap(x,y);int t=dep[x]-dep[y],k=Log[n]+1;for(int i=0;i<=k;i++)if(t&(1<<i))x=Fa[x][i];if(x==y)return x;while(Fa[x][0]!=Fa[y][0]){if(Fa[x][k]!=Fa[y][k]){x=Fa[x][k];y=Fa[y][k];}k--;}return Fa[x][0]; } int getdis(int x,int y){return dep[x]+dep[y]-dep[Lca(x,y)]*2;} vector<int> t[2][N]; void modify(int typ,int pos,int x,int vl){if(!x)return;int up=t[typ][pos].size();while(x<up){t[typ][pos][x]+=vl;x+=x&(-x);} } int query(int typ,int pos,int x){int res=0;x=min(x,(int)(t[typ][pos].size()-1));while(x){res+=t[typ][pos][x];x-=x&(-x);}return res; } int siz[N],F[N],rt,siz_tree; int prt[N];bool vis[N]; void getroot(int u,int fa){siz[u]=1;F[u]=0;for(int i=head[u];i;i=E[i].next){int v=E[i].v;if(v==fa||vis[v])continue;getroot(v,u);siz[u]+=siz[v];F[u]=max(F[u],siz[v]);}F[u]=max(F[u],siz_tree-siz[u]);if(F[u]<F[rt])rt=u; } void divide(int u,int fa){prt[u]=fa;vis[u]=1;t[0][u].resize(siz_tree+1);t[1][u].resize(siz_tree+1);for(int i=head[u];i;i=E[i].next){int v=E[i].v;if(vis[v])continue;F[rt=0]=siz_tree=siz[v];getroot(v,u);divide(rt,u);} } void modify(int u,int vl){for(int i=u;i;i=prt[i]){modify(0,i,getdis(u,i),vl);if(!prt[i])break;modify(1,i,getdis(u,prt[i]),vl);} } int query(int u,int vl){int res=query(0,u,vl)+val[u];for(int i=prt[u],last=u;i;last=i,i=prt[i]){int d=vl-getdis(u,i);if(d<0)continue;res+=query(0,i,d)-query(1,last,d)+val[i];}return res; } void work(){F[rt=0]=siz_tree=n;getroot(1,0);divide(rt,0); } int main(){freopen("bzoj3730.in","r",stdin);Log[0]=-1;for(int i=1;i<N;i++)Log[i]=Log[i>>1]+1;n=read();m=read();for(int i=1;i<=n;i++)val[i]=read();for(int i=1;i<n;i++){int u=read(),v=read();add(u,v);add(v,u);}getFa(1,0);work();for(int i=1;i<=n;i++)modify(i,val[i]);for(int i=1;i<=m;i++){int op=read(),x=read(),y=read();x^=lastans,y^=lastans;if(op)modify(x,y-val[x]),val[x]=y;else printf("%d\n",lastans=query(x,y));}return 0; }

總結

以上是生活随笔為你收集整理的BZOJ3730 震波 【动态点分治】*的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。