歡迎訪問~原文出處——博客園-zhouzhendong

去博客園看該題解

---

題目傳送門 - BZOJ1146

---

題意概括

　　在一棵樹上，每一個點一個權值。

　　有兩種操作：

　　1、單點修改

　　2、詢問兩點之間的樹鏈上的第k大值

---

?

題解

　　水題。

　　就是煩了一點。

　　居然只調了3個小時？

　　樹鏈剖分+帶修主席樹。

　　帶修主席樹：

　　BZOJ1901 Zju2112 Dynamic Rankings 主席樹

---

?

代碼

#include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> #include <vector> using namespace std; const int N=80005; struct Gragh{int cnt,y[N*2],nxt[N*2],fst[N];void clear(){cnt=0;memset(fst,0,sizeof fst);}void add(int a,int b){y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;} }g; struct cz{int k,a,b; }q[N]; int n,Q,v[N],Ha[N*2],hs; int fa[N],son[N],depth[N],size[N],top[N],p[N],ap[N],cnp=0; const int S=N*2*2*20; vector <int> val[N]; int ls[S],rs[S],root[N],Next[S],sum[S],pp[S],app[S],tot=0,tpp=0; void LSH(){sort(Ha+1,Ha+hs+1);int hs_=1;for (int i=2;i<=hs;i++)if (Ha[i]!=Ha[i-1])Ha[++hs_]=Ha[i];hs=hs_; } void Get_Gen_Info(int rt,int pre,int d){fa[rt]=pre,depth[rt]=d,size[rt]=1,son[rt]=-1;for (int i=g.fst[rt];i;i=g.nxt[i])if (g.y[i]!=pre){int s=g.y[i];Get_Gen_Info(s,rt,d+1);size[rt]+=size[s];if (son[rt]==-1||size[s]>size[son[rt]])son[rt]=s;} } void Get_Top(int rt,int tp){top[rt]=tp;ap[p[rt]=++cnp]=rt;if (son[rt]==-1)return;Get_Top(son[rt],tp);for (int i=g.fst[rt];i;i=g.nxt[i]){int s=g.y[i];if (s!=fa[rt]&&s!=son[rt])Get_Top(s,s);} } int find(int x){return lower_bound(Ha+1,Ha+hs+1,x)-Ha; } void build(int &rt,int L,int R){rt=++tot;if (L==R){ls[rt]=rs[rt]=0;return;}int mid=(L+R)>>1;build(ls[rt],L,mid);build(rs[rt],mid+1,R); } void access(int prt,int &rt,int L,int R,int pos){if (!rt||rt==prt)rt=++tot;Next[prt]=rt;if (L==R)return;int mid=(L+R)>>1;if (pos<=mid){access(ls[prt],ls[rt],L,mid,pos);if (!rs[rt])rs[rt]=rs[prt];}else {access(rs[prt],rs[rt],mid+1,R,pos);if (!ls[rt])ls[rt]=ls[prt];} } void build_pp(int rt){if (!rt)return;for (int i=rt;i;i=Next[i])app[pp[i]=++tpp]=i;build_pp(ls[rt]);build_pp(rs[rt]); } int lowbit(int x){return x&-x; } void add(int x,int d){for (;x<=tpp;x+=lowbit(x))sum[x]+=d; } int Sum(int x){int ans=0;for (;x>0;x-=lowbit(x))ans+=sum[x];return ans; } void update(int rt,int L,int R,int pos,int v){add(pp[rt],v);if (L==R)return;int mid=(L+R)>>1;if (pos<=mid)update(ls[rt],L,mid,pos,v);elseupdate(rs[rt],mid+1,R,pos,v); } int query(int prt,int rt,int L,int R,int pos){if (R<pos)return 0;if (L>=pos)return Sum(pp[rt])-Sum(pp[prt]);int mid=(L+R)>>1;return query(ls[prt],ls[rt],L,mid,pos)+query(rs[prt],rs[rt],mid+1,R,pos); } int Tquery(int a,int b,int pos){int f1=top[a],f2=top[b];int total=0;while (f1!=f2){if (depth[f1]<depth[f2])swap(f1,f2),swap(a,b);total+=query(root[p[f1]-1],root[p[a]],1,hs,pos);a=fa[f1],f1=top[a];}if (depth[a]>depth[b])swap(a,b);total+=query(root[p[a]-1],root[p[b]],1,hs,pos);return total; } int main(){scanf("%d%d",&n,&Q);for (int i=1;i<=n;i++)scanf("%d",&v[i]),Ha[i]=v[i];hs=n;g.clear();for (int i=1,a,b;i<n;i++){scanf("%d%d",&a,&b);g.add(a,b);g.add(b,a);}for (int i=1;i<=Q;i++){scanf("%d%d%d",&q[i].k,&q[i].a,&q[i].b);if (q[i].k==0)Ha[++hs]=q[i].b;}LSH();Get_Gen_Info(1,0,0);Get_Top(1,1);for (int i=1;i<=n;i++)val[i].clear();for (int i=1;i<=n;i++)val[p[i]].push_back(find(v[i]));for (int i=1;i<=Q;i++)if (q[i].k==0)val[p[q[i].a]].push_back(find(q[i].b));build(root[0],1,hs);memset(Next,0,sizeof Next);for (int i=1;i<=n;i++)for (int j=0;j<val[i].size();j++)access(root[i-1],root[i],1,hs,val[i][j]);build_pp(root[0]);memset(sum,0,sizeof sum);for (int i=1;i<=n;i++)update(root[p[i]],1,hs,find(v[i]),1);for (int i=1;i<=Q;i++){if (q[i].k==0){update(root[p[q[i].a]],1,hs,find(v[q[i].a]),-1);update(root[p[q[i].a]],1,hs,find(v[q[i].a]=q[i].b),1);}else {int L=1,R=hs,mid,ans=-1;while (L<=R){mid=(L+R)>>1;if (Tquery(q[i].a,q[i].b,mid)>=q[i].k)L=mid+1,ans=mid;elseR=mid-1;}if (!~ans)puts("invalid request!");elseprintf("%d\n",Ha[ans]);}}return 0; }

　　

轉載于:https://www.cnblogs.com/zhouzhendong/p/BZOJ1146.html

總結

以上是生活随笔為你收集整理的BZOJ1146 [CTSC2008]网络管理Network 树链剖分 主席树 树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

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