令人抓狂的整體二分題。根本原因還是我太菜了。

在學校寫了一個下午寫得頭暈，回家里重寫了一遍，一個小時就寫完了……不過還是太慢。

題目傳送門：洛谷P4175。

題意簡述：

一棵 \(n\) 個結點的樹，每個點有點權。

有 \(m\) 次操作，每個操作要么是更改單點點權，要么是查詢樹鏈上第 \(k\) 大點權。

題解：

樹套樹固然可以，但是整體二分也很好。

整體二分就是對于所有的詢問一起二分答案，在二分區間范圍內的查詢和修改一并下傳。

這題把整體二分基礎題的操作搬到了鏈上，但是實現方法并沒有太大不同。

初始點權看成增加點權，插入在所有操作的最前面即可。
更改點權可以看成刪除點權再增加點權，變成兩次修改即可。

這題整體二分要求第 \(k\) 大，考慮二分出的答案 \(mid\)，將大于 \(mid\) 的修改轉成單點權值 \(\pm 1\)，
而對于樹鏈查詢第 \(k\) 大，則轉化成鏈上權值之和是否等于 \(k\)。

寫整體二分題永遠要注意二分的條件，我的條件是，鏈上大于 \(mid\) 的點數小于 \(k\) 個則答案小于等于 \(mid\)，否則答案大于 \(mid\)。

單點修改，樹鏈查詢要是還用樹剖就太naive了，套路轉化：

考慮每個節點維護到根的路徑上的信息，那么單點修改就變成子樹修改，鏈查就變成四個單點查了（需要求LCA）。

而子樹是一個區間，區間加法，單點查詢；再使用樹狀數組差分技巧轉化成單點差分，區間前綴和。

注意到還要求LCA，直接在DFS的時候用Tarjan處理就好了。

關于判斷無解：當然可以直接處理掉……不過這樣就必須求樹鏈長度了。
我的方法是，往權值里面加一個-1，如果答案是-1，則真實答案應該是無解。

我的代碼還離散化了權值，其實沒用……

其他惡心的地方就是整體二分基本功了，太弱了調了好久……注意循環變量是指向真實操作的下標的指針還是真實操作的下標，如果你寫結構體當我沒說。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int MN=80005; const int MM=110005; const int MQ=140005; int n,m,q,w[MN],d[MQ],c; int o[MQ],a[MQ],b[MQ],p[MQ],lc[MQ],ans[MQ]; int eh[MN],qh[MN],nxt[MM*2],to[MM*2],tot; inline void ins(int*h,int x,int y){nxt[++tot]=h[x],to[tot]=y,h[x]=tot;} int ld[MN],rd[MN],faz[MN],dfc; int fa[MN];int ff(int x){return fa[x]?fa[x]=ff(fa[x]):x;} void dfs(int u,int f){faz[u]=f,ld[u]=++dfc;for(int i=eh[u];i;i=nxt[i])if(to[i]!=f)dfs(to[i],u),fa[to[i]]=u;for(int i=qh[u];i;i=nxt[i])if(lc[to[i]])lc[to[i]]=ff(lc[to[i]]);else lc[to[i]]=u;rd[u]=dfc; } int B[MN]; inline void I(int i,int x){for(;i<=n;i+=i&-i)B[i]+=x;} inline int Q(int i){int a=0;for(;i;i-=i&-i)a+=B[i];return a;} int t[MQ]; void s(int l,int r,int L,int R){if(l>r)return;if(L==R){for(int i=l;i<=r;++i)ans[p[i]]=L;return;}int m=L+R>>1,p1=l-1,p2=r+1;for(int j=l,i;j<=r;++j){if(o[i=p[j]]>0){int x=Q(ld[a[i]])+Q(ld[b[i]])-Q(ld[lc[i]])-Q(ld[faz[lc[i]]]);if(x<o[i])o[i]-=x,t[++p1]=i;else t[--p2]=i;}else if(b[i]>m){I(ld[a[i]],o[i]?-1:1),I(rd[a[i]]+1,o[i]?1:-1);t[--p2]=i;}else t[++p1]=i;}for(int i=l;i<=r;++i)if(o[p[i]]<=0&&b[p[i]]>m)I(ld[a[p[i]]],o[p[i]]?1:-1),I(rd[a[p[i]]]+1,o[p[i]]?-1:1);reverse(t+p2,t+r+1),memcpy(p+l,t+l,r-l+1<<2);s(l,p1,L,m),s(p2,r,m+1,R); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",&w[i]),o[++q]=0,a[q]=i,b[q]=w[i],p[q]=q;for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),ins(eh,x,y),ins(eh,y,x);for(int i=1;i<=m;++i){++q,scanf("%d%d%d",&o[q],&a[q],&b[q]),p[q]=q;if(!o[q])o[++q]=-1,a[q]=a[q-1],b[q]=w[a[q-1]],p[q]=q,w[a[q-1]]=b[q-1];}for(int i=1;i<=q;++i)if(o[i]>0)ins(qh,a[i],i),ins(qh,b[i],i);else d[++c]=b[i];d[++c]=-1;sort(d+1,d+c+1);c=unique(d+1,d+c+1)-d-1;for(int i=1;i<=q;++i)if(o[i]<=0)b[i]=lower_bound(d+1,d+c+1,b[i])-d;dfs(1,0),s(1,q,1,c);for(int i=1;i<=q;++i)if(o[i]>0)ans[i]==1?puts("invalid request!"):printf("%d\n",d[ans[i]]);return 0; } // 20:08 - 21:03

轉載于:https://www.cnblogs.com/PinkRabbit/p/10182061.html

總結

以上是生活随笔為你收集整理的洛谷 P4175: bzoj 1146: [CTSC2008]网络管理的全部內容，希望文章能夠幫你解決所遇到的問題。

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