?

3730: 震波

Time Limit: 15 Sec??Memory Limit: 256 MB
Submit: 2260??Solved: 470
[Submit][Status][Discuss]

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

很久沒有寫過代碼題了，被這道沒什么難度的題目弄的心力交瘁。

很容易想到是動態點分治的題型，有可以看出需要數據結構維護，因為有影響半徑的限制，又是求和，很容易想到線段樹。這樣由于樹高的限制，每個點最多出現在log n棵線段樹中，動態開點就好了。

實際上動態點分治不需要一上來就建點分樹，遍歷一遍求出每個點在點分樹上的父節點就可以了，只有需要知道點分樹的子節點在父節點在原樹上的哪個子樹內的時候才需要建圖（將這個作為邊權即可，參考BZOJ3924捉迷藏）。

這道題雖然只是幾個模板拼在一起，但是我調了很久，說明對代碼的熟練程度還有很大的欠缺。有很多錯誤，而且因為這道題既卡空間又卡時間，所以還需要各種卡常技巧，下面是一些我遇到的問題。

• 不要建點分樹，只需記錄父節點。找中心的過程和普通點分治一樣，rt和S作為全局變量而不是參數傳入。
• 注意看清題目，強制在線要記得異或。
• 思路仍然是不斷沿點分樹向上爬，加上父節點的貢獻減去自己的重復貢獻。
• 注意點分樹上兒子到父親的距離可能比兒子到自己的距離短。

還有一些卡常技巧（讓常數優化成為一種習慣）：

• 快讀和register最常用，但是寄存器容量有限要酌情選擇。比較底層的函數的參數類型也可以設置為register int，也會有很大提升。
• 線段樹能避免update的盡量避免，可以標記永久化的就不要pushdown，比如單點修改區間求和就不需要update。
• 增加一些循環終止條件。
• 多維數組將少的維數提到前面，數組開2的次冪數加一并沒有明顯優化效果。
• rmq求lca

想清楚之后就可以直接上代碼了。

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #define rg register int 6 #define rep(i,l,r) for (rg i=l; i<=r; i++) 7 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 8 typedef long long ll; 9 using namespace std; 10 11 const int N=100100,M=6000100,inf=1000000000; 12 int n,m,rt,S,op,x,y,lst,tot,nd,cnt,to[N<<1],nxt[N<<1],h[N]; 13 int sz[N],fa[N],vis[N],st[20][N<<1],dep[N]; 14 int pos[N],root[N],root1[N],lg[N<<1],f[N],a[N],sum[M],ls[M],rs[M]; 15 16 template<typename T>inline void rd(T &x){ 17 rg t; char ch; 18 for (t=0; !isdigit(ch=getchar()); t=(ch=='-')); 19 for (x=ch-'0'; isdigit(ch=getchar()); x=x*10+ch-'0'); 20 if (t) x=-x; 21 } 22 23 void add(rg u,rg v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 24 25 void find(rg x,rg fa){ 26 sz[x]=1; f[x]=0; 27 For(i,x) if ((k=to[i])!=fa && !vis[k]) 28 find(k,x),sz[x]+=sz[k],f[x]=max(f[x],sz[k]); 29 f[x]=max(f[x],S-sz[x]); 30 if (f[x]<f[rt]) rt=x; 31 } 32 33 void dfs(rg x,rg fa){ 34 st[0][++tot]=dep[x]; pos[x]=tot; 35 For(i,x) if ((k=to[i])!=fa) 36 dep[k]=dep[x]+1,dfs(k,x),st[0][++tot]=dep[x]; 37 } 38 39 void rmq(){ 40 rep(j,1,18) rep(i,1,tot-(1<<j)+1) 41 st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]); 42 } 43 44 int get(rg l,rg r){ 45 if (l>r) swap(l,r); rg t=lg[r-l+1]; 46 return min(st[t][l],st[t][r-(1<<t)+1]); 47 } 48 49 int dis(rg u,rg v){ rg x=pos[u],y=pos[v]; return dep[u]+dep[v]-2*get(x,y); } 50 51 void mdf(rg &x,rg L,rg R,rg pos,rg k){ 52 if (!x) x=++nd; 53 sum[x]+=k; if (L==R) return; 54 rg mid=(L+R)>>1; 55 if (pos<=mid) mdf(ls[x],L,mid,pos,k); else mdf(rs[x],mid+1,R,pos,k); 56 } 57 58 int que(rg x,rg L,rg R,rg pos){ 59 if (!x) return 0; 60 if (L==R) return sum[x]; 61 rg mid=(L+R)>>1; 62 if (pos<=mid) return que(ls[x],L,mid,pos); 63 else return sum[ls[x]]+que(rs[x],mid+1,R,pos); 64 } 65 66 void work(rg x,rg F,rg p){ 67 mdf(root[p],0,n,dis(x,p),a[x]); 68 if (fa[p]) mdf(root1[p],0,n,dis(x,fa[p]),a[x]); 69 For(i,x) if (!vis[k=to[i]] && k!=F) work(k,x,p); 70 } 71 72 void build(rg x){ 73 vis[x]=1; work(x,fa[x],x); 74 for (rg i=h[x],k; i; i=nxt[i]) if (!vis[k=to[i]]) 75 f[rt=0]=inf,S=sz[k],find(k,x),fa[rt]=x,build(rt); 76 } 77 78 int getans(rg x,rg y){ 79 rg res=que(root[x],0,n,y); rg D=0; 80 for (rg i=x; fa[i]; i=fa[i]){ 81 D=dis(x,fa[i]); 82 if (D>y) continue; 83 if (D-y>20) return x; 84 res+=que(root[fa[i]],0,n,y-D)-que(root1[i],0,n,y-D); 85 } 86 return res; 87 } 88 89 void modify(rg x,rg y){ 90 int t=y-a[x]; mdf(root[x],0,n,0,t); a[x]=y; 91 for (int i=x; fa[i]; i=fa[i]){ 92 mdf(root[fa[i]],0,n,dis(x,fa[i]),t); 93 mdf(root1[i],0,n,dis(x,fa[i]),t); 94 } 95 } 96 97 int main(){ 98 freopen("bzoj3730.in","r",stdin); 99 freopen("bzoj3730.out","w",stdout); 100 rd(n); rd(m); 101 rep(i,1,n) rd(a[i]); 102 rep(i,1,n-1) rd(x),rd(y),add(x,y),add(y,x); 103 dfs(1,0); rmq(); 104 lg[1]=0; rep(i,2,tot) lg[i]=lg[i>>1]+1; 105 f[rt=0]=inf; S=n; find(1,0); build(rt); 106 rep(i,1,m){ 107 rd(op); rd(x); rd(y); x^=lst; y^=lst; 108 if (op==0) printf("%d\n",lst=getans(x,y)); else modify(x,y); 109 } 110 return 0; 111 }

?

轉載于:https://www.cnblogs.com/HocRiser/p/8527354.html

總結

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

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