P2146 题解

思路

这题就是一道树链剖分的模板题，用0和1分别代表每个软件的存在与否，那么“安装$k$”操作就是把从$1$到$k$的路径上的节点都置为$1$，而“卸载$k$”则是将$k$的子树都置为$0$，用树链剖分就可以十分方便地维护这两种操作。

然后对根节点求区间和就可以求出一共有多少个状态值为$1$（即安装了）的软件，用这个数减去上一次操作时的安装软件数即为改变的数目。

Tips：

“赋值”运算不能进行叠加，打延迟标记时要注意先将原有的延迟标记下传
数据范围这么大一定要写快读

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=100005;
int n,m,last;
vector<int> e[maxn];
int father[maxn],dep[maxn],size[maxn],hson[maxn],top[maxn],seg[maxn],rev[maxn<<2],num[maxn],tot;
struct segmenttree{ //线段树
    int l,r,sum,add=-1;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define add(x) tree[x].add
};
segmenttree tree[maxn<<2];
inline int readint() { //快读
   int x=0;char ch=getchar();
    while(ch<48||ch>57) ch=getchar();
    while(ch>=48&&ch<=57) x=x*10+ch-48,ch=getchar();
    return x;
}
inline void readchar(char * input) { //快读
  int len=0;
  char ch=getchar();
  while(ch!=' ' && ch!='\r' && ch !='\n')
  {
    input[len++]=ch;
    ch=getchar();
  }
}
void addedge(int x,int y) //vector存图
{
    e[x].push_back(y);
    e[y].push_back(x);
}
void dfs1(int u,int f) //树剖预处理
{
    size[u]=1;
    father[u]=f;
    dep[u]=dep[f]+1;
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i];
        if(v!=f)
        {
            dfs1(v,u);
            size[u]+=size[v];
            if(size[v]>size[hson[u]]) hson[u]=v;
        }
    }
}
void dfs2(int u,int f) //树剖预处理
{
    if(hson[u])
    {
        seg[hson[u]]=++tot;
        top[hson[u]]=top[u];
        rev[tot]=hson[u];
        dfs2(hson[u],u);
    }
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i];
        if(!top[v])
        {
            seg[v]=++tot;
            rev[tot]=v;
            top[v]=v;
            dfs2(v,u);
        }
    }
}
void build(int p,int l,int r) //线段树建树
{
    int mid=(l+r)>>1;
    l(p)=l;r(p)=r;
    if(l==r){
        sum(p)=num[rev[l]];
        return;
    }
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    sum(p)=(sum(p<<1)+sum(p<<1|1));
    return;
}
void spread(int p) //下传延迟标记
{
	if(add(p)>=0)
	{
		sum(p<<1)=add(p)*(r(p<<1)-l(p<<1)+1);
		sum(p<<1|1)=add(p)*(r(p<<1|1)-l(p<<1|1)+1);
		add(p<<1)=add(p);
		add(p<<1|1)=add(p);
		add(p)=-1;
	}
}
int query(int p,int l,int r) //区间查询
{
  if(l>r) swap(l,r);
  if(l<=l(p) && r>=r(p)) return sum(p);
  spread(p);
  int mid=((l(p)+r(p))>>1);
  int ans=0;
  if(l<=mid) ans=(ans+query(p<<1,l,r));
  if(r>mid) ans=(ans+query(p<<1|1,l,r));
  return ans;
}
void update(int p,int l,int r,int c) { //区间更新
  if(l>r) swap(l,r);
  spread(p); //先将原有的延迟标记下传
  if(l<=l(p) && r>=r(p)) {
		sum(p)=c*(r(p)-l(p)+1);
		add(p)=c;
		return;
	}
	int mid=((l(p)+r(p))>>1);
	if(l<=mid) update(p<<1,l,r,c);
	if(r>mid) update(p<<1|1,l,r,c);
	sum(p)=(sum(p<<1)+sum(p<<1|1));
}
void crange(int x,int y,int k) //路径修改
{
  while(top[x]!=top[y]) {
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    update(1,seg[top[x]],seg[x],k);
    x=father[top[x]];
  }
  if(dep[x]>dep[y]) swap(x,y);
  update(1,seg[x],seg[y],k);
}
void cson(int x,int k) //子树修改
{
  update(1,seg[x],seg[x]+size[x]-1,k);
}
int main()
{
  n=readint();
  for(int i=2,a;i<=n;i++){
    a=readint();
    addedge(i,a+1);
  }
  m=readint();
  dfs1(1,0);
  tot=seg[1]=1; //树剖初始化
  top[1]=rev[1]=1;
  dfs2(1,0);
  build(1,1,n+1);
  int last=query(1,1,n); //存好上一次的软件数
  for(int i=1,x;i<=m;i++)
  {
    char op[20];
    scanf("%s\n",op);
    if (op[0]=='i') { //安装
      x=readint();
      crange(x+1,1,1);
      int cur=query(1,1,n);
      printf("%d\n",abs(last-cur)); //更新答案
      last=query(1,1,n); //存好上一次的软件数
    }
    else if (op[0]=='u') { //安装
      x=readint();
      cson(x+1,0);
      int cur=query(1,1,n);
      printf("%d\n",abs(last-cur)); //更新答案
      last=cur; //存好上一次的软件数
    }
  }
  return 0;
}