震波

Description

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

Input

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

Output

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

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

---

寫和調(diào)錯共用時2h。
這就算了。
然后咱卡常卡了2h!!!!!

(╯‵□′)╯︵┻━┻

---

思路:
動態(tài)點分治。
首先顯然要建點分樹。
對于每個節(jié)點開兩個樹狀數(shù)組，第一個記錄到當(dāng)前分治中心的距離為指定值的點的權(quán)值和，第二個記錄到點分樹上當(dāng)前分治中心的父親的距離為指定值的點的權(quán)值和。

那么對于節(jié)點 u 詢問，沿詢問節(jié)點向點分樹根節(jié)點跳。
對點分樹上每個節(jié)點v，在其第一個樹狀數(shù)組上詢問距離小于 k?dist(u,v) 的結(jié)果。
若當(dāng)前節(jié)點不是 u 本身，可以發(fā)現(xiàn)這個點到上一個詢問過程中訪問的點的答案有一部分重合了。
那么這時用第二個樹狀數(shù)組減去重復(fù)的情況即可。
即用用兒子的樹狀數(shù)組詢問距離小于k?dist(u,v)的結(jié)果。

對于修改，找出當(dāng)前節(jié)點所有出現(xiàn)的位置逐一修改即可。
具體做法是，從修改節(jié)點開始，沿著點分樹父親向上跳，沿路節(jié)點的兩個樹狀數(shù)組均需修改。

最后一步，卡常。
然后就完成了~

#include<bits/stdc++.h> using namespace std;inline char getchars(void) {static char buf[1000000],*p1=buf,*p2=buf;if(p1==p2) {p2=(p1=buf)+fread(buf,1,1000000,stdin);if(p1==p2)return EOF;}return *p1++; }inline int read() {int x=0;char ch=getchars();while(ch<'0' || '9'<ch)ch=getchars();while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchars();return x; }inline void write(int x) {if(x>=10)write(x/10);putchar('0'+x%10); }inline void chkmax(int &a,int b){if(a<b)a=b;} inline void chkmin(int &a,int b){if(a>b)a=b;} inline int minn(int a,int b){if(a<b)return a;return b;} inline int maxx(int a,int b){if(a>b)return a;return b;}typedef long long ll; const int N=100009; const int K=20;int n,m; int to[N<<1],nxt[N<<1],beg[N],tot=1; int fa[K][N],dep[N],fat[N],siz[N<<1]; int depth[N],id[N],ed[N],seg[N],dfn; int val[N],fadis[N],stk[N],top; bool ban[N<<1];namespace bits {ll *rt[N],*rt2[N];int mv[N],mv2[N];inline void init(ll* &rts,int siz){rts=new ll[sizeof(ll)*(siz+9)];memset(rts,0,sizeof(ll)*(siz+8));}inline void modify(ll *bit,int mp,int p,ll v){for(int i=p+1;i<=mp+1;i+=i&-i)bit[i]+=v;}inline ll query(ll *bit,int p){ll ret=0;for(int i=p+1;i;i-=i&-i)ret+=bit[i];return ret;} }using namespace bits;inline void add(int u,int v) {to[++tot]=v;nxt[tot]=beg[u];beg[u]=tot; }inline void dfspre(int u) {for(int i=beg[u],v;i;i=nxt[i])if((v=to[i])!=fa[0][u]){fa[0][v]=u;dep[v]=dep[u]+1;dfspre(v);} }inline int lca(int a,int b) {if(dep[b]<dep[a])swap(a,b);int dlt=dep[b]-dep[a];for(int i=K-1,j=(1<<i);~i;--i,j>>=1)if(dlt&j)b=fa[i][b];if(a==b)return a;for(int i=K-1;~i;--i)if(fa[i][a]!=fa[i][b])a=fa[i][a],b=fa[i][b];return fa[0][a]; }inline int dist(int u,int v) {return dep[u]+dep[v]-(dep[lca(u,v)]<<1); }inline int dfsrt(int u,int faa,int totsz,int &rt) {int sz=1,mx=0;for(int i=beg[u];i;i=nxt[i])if(to[i]!=faa && !ban[i]){chkmax(mx,(siz[i]=dfsrt(to[i],u,totsz,rt)));sz+=siz[i];siz[i^1]=n-siz[i];}chkmax(mx,totsz-sz);if((mx<<1)<=totsz)rt=u;return sz; }inline int dfsdep(int u,int faa) {seg[id[u]=++dfn]=u;int ret=depth[u];for(int i=beg[u];i;i=nxt[i])if(to[i]!=faa && !ban[i]){depth[to[i]]=depth[u]+1;chkmax(ret,dfsdep(to[i],u));}ed[u]=dfn;return ret; }inline int dfsbuild(int u,int faa) {stk[++top]=u;int ret=depth[u];for(int i=beg[u];i;i=nxt[i])if(to[i]!=faa && !ban[i]){depth[to[i]]=depth[u]+1;chkmax(ret,dfsbuild(to[i],u));}return ret; }inline void dfs(int u,int faa,int sz) {int root=u;dfsrt(u,0,sz,root);if(faa){top=0;depth[u]=1;mv2[root]=dfsbuild(u,0);init(rt2[root],mv2[root]);for(int i=1;i<=top;i++)modify(rt2[root],mv2[root],depth[stk[i]],val[stk[i]]);}fat[root]=faa;mv[root]=dfsdep(root,depth[root]=dfn=0);init(rt[root],mv[root]);for(int i=id[root];i<=ed[root];i++)modify(rt[root],mv[root],depth[seg[i]],val[seg[i]]);for(int i=beg[root];i;i=nxt[i])if(!ban[i]){ban[i]=ban[i^1]=1;dfs(to[i],root,siz[i]);} }inline void edit(int pos,int v) {int curdis=0;for(int i=pos,las=0;i;las=i,i=fat[i]){curdis=dist(i,pos);modify(rt[i],mv[i],curdis,v-val[pos]);if(las)modify(rt2[las],mv2[las],curdis,v-val[pos]);}val[pos]=v; }inline int ask(int pos,int k) {int ret=0,curdis=0;for(int i=pos,las=0;i;las=i,i=fat[i]){curdis=dist(i,pos);if(k-curdis>=0)ret+=query(rt[i],minn(mv[i],k-curdis));if(las && k-curdis>0)ret-=query(rt2[las],minn(mv2[las],k-curdis));}return ret; }int main() {n=read();m=read();for(int i=1;i<=n;i++)val[i]=read();for(int i=1,u,v;i<n;i++){u=read();v=read();add(u,v);add(v,u);}dfspre(dep[1]=1);for(int i=1;i<K;i++)for(int j=1;j<=n;j++)fa[i][j]=fa[i-1][fa[i-1][j]];dfs(1,0,n);int lans=0;for(int i=1,ty,x,k;i<=m;i++){ty=read();x=read()^lans;k=read()^lans;if(ty==0)write(lans=ask(x,k)),putchar('\n');elseedit(x,k);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[BZOJ3730]震波-动态点分治的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。