NOI2015 D1T2 软件包管理器

　　题目传送门;

　　这个貌似是我这个蒟蒻做的第一道NOI系列的题了吧。。。这题的算法是树链剖分，其实基本上就是很常见的树剖+线段树，题目既然是要求每次安装或卸载改变的软件包的数目，那么就在每次操作前记录下线段树中根节点的权值，再进行修改，修改后的根节点的值与先前记录的值的差的绝对值就是改变的软件包的数目。思想并不复杂，但是这一类代码量比较大的题有很多细节要注意，这里我就不一一地说了。

　　另外，这个题目中的软件包是从0开始标号的，为了方便操作，可以把所有软件包的标号都+1。

　　下面是AC代码：

　　（蒟蒻手写的代码效率也还行，最慢的点236ms）　　

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<iostream>

using namespace std;

const int N=;

int n,m,anum,depth[N],head[N];

int xu[N],id,num[N],fa[N];

int size[N],top[N],hson[N];

int segtree[N<<],sign[N<<];

struct Node{

  int to,next;

}edge[N<<];

inline int read()

{

  char ch=getchar();int num=;bool flag=false;

  while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

  while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

  return flag?-num:num;

}

inline int Abs(int x)

{return x>?x:-x;}

inline void add(int x,int y)

{

  edge[++anum].to=y;

  edge[anum].next=head[x];

  head[x]=anum;

}

inline void dfs1(int u)

{

  size[u]=;

  for(int i=head[u];i!=-;i=edge[i].next){

    int v=edge[i].to;

    if(v==fa[u])continue;

    depth[v]=depth[u]+;fa[v]=u;

    dfs1(v);size[u]+=size[v];

    if(!hson[u]||size[v]>size[hson[u]])

      hson[u]=v;

  }

}

inline void dfs2(int u,int nowtop)

{

  xu[++id]=u;num[u]=id;top[u]=nowtop;

  if(!hson[u])return;dfs2(hson[u],nowtop);

  for(int i=head[u];i!=-;i=edge[i].next){

    int v=edge[i].to;

    if(v==fa[u]||v==hson[u])continue;

    dfs2(v,v);

  }

}

inline void pushup(int root)

{segtree[root]=segtree[root<<]+segtree[root<<|];}

inline void pushdown(int root,int l,int r)

{

  if(sign[root]!=-){

    int mid=(l+r)>>;

    segtree[root<<]=(mid-l+)*sign[root];

    segtree[root<<|]=(r-mid)*sign[root];

    sign[root<<]=sign[root];

    sign[root<<|]=sign[root];

    sign[root]=-;

  }

}

inline void build(int l,int r,int root)

{

  segtree[root]=;

  if(l==r)return;

  int mid=(l+r)>>;

  build(l,mid,root<<);

  build(mid+,r,root<<|);

  pushup(root);

}

inline void update(int l,int r,int root,int L,int R,int C)

{

  if(r<L||l>R)return;

  if(L<=l&&r<=R){

    segtree[root]=(r-l+)*C;

    sign[root]=C;return;}

  int mid=(l+r)>>;

  pushdown(root,l,r);

  if(L<=mid)update(l,mid,root<<,L,R,C);

  if(R>mid)update(mid+,r,root<<|,L,R,C);

  pushup(root);

}

inline void change(int x,int y,int val)

{

  int fax=top[x],fay=top[y];

  while(fax!=fay){

    if(depth[fax]<depth[fay])

      {swap(fax,fay);swap(x,y);}

    update(,n,,num[fax],num[x],val);

    x=fa[fax];fax=top[x];

  }

  if(depth[x]>depth[y])swap(x,y);

  update(,n,,num[x],num[y],val);

}

void ready()

{

  memset(head,-,sizeof(head));

  memset(sign,-,sizeof(sign));

  n=read();

  for(int i=;i<n;i++){

    int x=read();

    add(i+,x+);

    add(x+,i+);

  }

  fa[]=;depth[]=;

  dfs1();dfs2(,);

  build(,n,);

}

void work()

{

  m=read();char ka[];

  for(int i=;i<=m;i++){

    scanf("%s",ka);

    int t1=segtree[];

    int x=read();x++;

    if(ka[]=='i'){

      change(,x,);

      int t2=segtree[];

      printf("%d\n",Abs(t2-t1));

    }

    if(ka[]=='u'){

      update(,n,,num[x],num[x]+size[x]-,);

      int t2=segtree[];

      printf("%d\n",Abs(t1-t2));

    }

  }

}

int main()

{

  ready();

  work();

  return ;

}