BZOJ1146 [CTSC2008]网络管理Network 树链剖分 主席树 树状数组

​​题目传送门 - 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);
  else
    update(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;
        else
          R=mid-1;
      }
      if (!~ans)
        puts("invalid request!");
      else
        printf("%d\n",Ha[ans]);
    }
  }
  return 0;
}