BZOJ1146: [CTSC2008]网络管理Network

 ?1 #include<bits/stdc++.h> ?2 using namespace std; ?3 const int N=100005; ?4 struct que ?5 { ?6 ????int l,r,k; ?7 }q[N]; ?8 int n,m,cnt,sec,idx,ra,mx; ?9 int id[N],bel[N],head[N],son[N],size[N],d[N],f[N],rt[N*4],a[N]; 10 vector<int>v; 11 inline int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;} 12 struct node 13 { 14 ????int to,nex; 15 }e[N*2]; 16 void adde(int x,int y) 17 { 18 ????e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt; 19 } 20 struct treap 21 { 22 ????int l,r,s,v,rnd,w; 23 }t[N*50]; 24 void dfs1(int x) 25 { 26 ????size[x]=1; 27 ????for(int i=head[x];i;i=e[i].nex) 28 ????{ 29 ????????int y=e[i].to; 30 ????????if(y==f[x])continue; 31 ????????d[y]=d[x]+1;f[y]=x;dfs1(y); 32 ????????size[x]+=size[y]; 33 ????????if(size[y]>size[son[x]])son[x]=y; 34 ????} 35 } 36 void dfs2(int x,int chain) 37 { 38 ????id[x]=++idx;bel[x]=chain; 39 ????if(son[x])dfs2(son[x],chain); 40 ????for(int i=head[x];i;i=e[i].nex) 41 ????{ 42 ????????int y=e[i].to; 43 ????????if(y==f[x]||y==son[x])continue; 44 ????????dfs2(y,y); 45 ????} 46 } 47 int lca(int x,int y) 48 { 49 ????while(bel[x]!=bel[y]) 50 ????{ 51 ????????if(d[bel[x]]<d[bel[y]])swap(x,y); 52 ????????x=f[bel[x]]; 53 ????} 54 ????return d[x]<d[y]?x:y; 55 }//树链剖分 56 ?57 void update(int k){t[k].s=t[t[k].l].s+t[t[k].r].s+t[k].w;} 58 void lturn(int &k){int rs=t[k].r;t[k].r=t[rs].l;t[rs].l=k;t[rs].s=t[k].s;update(k);k=rs;} ?59 void rturn(int &k){int ls=t[k].l;t[k].l=t[ls].r;t[ls].r=k;t[ls].s=t[k].s;update(k);k=ls;} 60 void insert(int &k,int num) 61 { 62 ????if(!k) 63 ????{ 64 ????????k=++sec; 65 ????????t[k].w=t[k].s=1; 66 ????????t[k].v=num; 67 ????????t[k].rnd=rand(); 68 ????????return; 69 ????} 70 ????t[k].s++; 71 ????if(t[k].v==num)t[k].w++; 72 ????else 73 ????{ 74 ????????if(t[k].v>num){ 75 ????????????insert(t[k].l,num); 76 ????????????if(t[t[k].l].rnd>t[k].rnd)rturn(k); 77 ????????} 78 ????????else{ 79 ????????????insert(t[k].r,num); 80 ????????????if(t[t[k].r].rnd>t[k].rnd)lturn(k); 81 ????????} 82 ????} 83 } 84 void del(int &k,int num) 85 { 86 ????if(!k)return; 87 ????if(t[k].v==num) 88 ????{ 89 ????????if(t[k].w>1)t[k].s--,t[k].w--; 90 ????????else if(t[k].l*t[k].r==0)k=t[k].l+t[k].r; 91 ????????else 92 ????????{ 93 ????????????if(t[t[k].l].rnd>t[t[k].r].rnd){rturn(k);del(k,num);} 94 ????????????else {lturn(k);del(k,num);} 95 ????????} 96 ????????return; 97 ????} 98 ????t[k].s--; 99 ????if(t[k].v>=num)del(t[k].l,num);100 ????else del(t[k].r,num);101 }102 void getrank(int k,int num)103 {104 ????if(!k)return;105 ????if(t[k].v==num){ra+=t[t[k].r].s;return;}106 ????if(t[k].v>num){107 ????????ra+=t[t[k].r].s+t[k].w;getrank(t[k].l,num);108 ????}109 ????else getrank(t[k].r,num);110 }//平衡树111 112 void add(int p,int l,int r,int L,int R,int num)113 {114 ????if(l==L&&r==R){getrank(rt[p],num);return;}115 ????int mid=l+r>>1;116 ????if(R<=mid)add(p<<1,l,mid,L,R,num);117 ????else if(L>mid)add(p<<1|1,mid+1,r,L,R,num);118 ????else add(p<<1,l,mid,L,mid,num),add(p<<1|1,mid+1,r,mid+1,R,num);119 }120 void change(int p,int l,int r,int pos,int x,int y)121 {122 ????del(rt[p],x);insert(rt[p],y);123 ????if(l==r)return;124 ????int mid=(l+r)>>1;125 ????if(mid>=pos)change(p<<1,l,mid,pos,x,y);126 ????else change(p<<1|1,mid+1,r,pos,x,y);127 }128 void query(int x,int y,int num)129 {130 ????while(bel[x]!=bel[y])131 ????{132 ????????add(1,1,n,id[bel[x]],id[x],num);133 ????????x=f[bel[x]];134 ????}135 ????add(1,1,n,id[y],id[x],num);136 }137 void solve(int x,int y,int k)138 {139 ????int lc=lca(x,y);140 ????ra=0;141 ????query(x,lc,0);142 ????query(y,lc,0);ra--;143 ????if(ra<k){puts("invalid request!");return;}144 ????int l=1,r=mx,ans;145 ????while(l<=r)146 ????{147 ????????int mid=l+r>>1;148 ????????ra=0;query(x,lc,mid);query(y,lc,mid);149 ????????if(a[lc]>mid)ra--;150 ????????if(ra<k)ans=mid,r=mid-1;151 ????????else l=mid+1;152 ????}153 ????printf("%d\n",v[ans-1]); 154 }155 int main()156 {157 ????scanf("%d%d",&n,&m);158 ????for(int i=1;i<=n;++i)159 ????{160 ????????scanf("%d",&a[i]);v.push_back(a[i]);161 ????}int x,y;162 ????for(int i=1;i<n;++i)163 ????{164 ????????scanf("%d%d",&x,&y);165 ????????adde(x,y);adde(y,x);166 ????}167 ????for(int i=1;i<=m;++i)168 ????{169 ????????scanf("%d%d%d",&q[i].k,&q[i].l,&q[i].r);170 ????????if(!q[i].k)171 ????????{172 ????????????v.push_back(q[i].r);173 ????????}174 ????}175 ????dfs1(1);dfs2(1,1);176 ????sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());mx=v.size();177 ????for(int i=1;i<=n;++i)a[i]=get(a[i]);178 ????for(int i=1;i<=m;++i)if(!q[i].k)q[i].r=get(q[i].r);179 ????for(int i=1;i<=n;++i)change(1,1,n,id[i],0,a[i]);180 ????for(int i=1;i<=m;++i)181 ????{182 ????????if(!q[i].k)183 ????????{184 ????????????change(1,1,n,id[q[i].l],a[q[i].l],q[i].r);a[q[i].l]=q[i].r;185 ????????}186 ????????else187 ????????{188 ????????????solve(q[i].l,q[i].r,q[i].k);189 ????????}190 ????}191 ????return 0;192 }