「NOI2015」软件包管理器

题目描述

题面比较啰唆，我先把大体意思讲一下:

首先，有编号从\(0\)到\(N-1\)的\(N\)个节点，根节点一定是\(0\)号节点(无前驱)

(我把下标都加上了一，转化为以\(1\)为起始下标的点集，那么根节点编号为\(1\)，注意一下)

输入会给定根节点以外的节点的前驱，即父节点编号。

还有\(M\)次操作：

\(install:\) 根据题意也就是将给定的节点\(x\)到根的路径上的每一个节点的权值赋值为\(1\)
\(uninstall:\) 根据题意也就是将以给定的节点\(x\)为根的子树的每一个节点的权值赋值为\(0\)

看到这里就很显然，这是一道树链剖分的模板题。

基本思路 (树链剖分+线段树)

既然是模板题，思路就很简单了，树剖之后加线段树维护即可。(不过还是有点坑点的...)

细节注意事项

接下来就是关于这道题的几个坑点。

坑点一：点下标出锅

这里我之前也有提到，尤其是在输入时，下面我把两种输入方式的正确写法都说一下：

以\(0\)为下标，这意味着你的输入是从下标\(1\)到\(N-1\)的，所以要这样写：

    for(rg int x,i=1;i<=n-1;i++) x=read();//这里主要只说下标处理，连边什么的见详细代码

以\(1\)为下标则是：

    for(rg int x,i=2;i<=n;i++) x=read();

这里我有一点检验方法，还是比较实用的，毕竟下标的处理是很基本而又重要的：

试着通过你的for循环算一下你的循环次数
确保你的循环变量\(i\)(或其他变量名)的循环起点

这样的话有可以适当避免下标出锅问题(我就是因为下标问题卡了十多分钟，泪的教训啊\(qwq\))

坑点二：线段树修改子节点信息(标记下传)出锅

在此篇题解的开始我便用粗体强调了，这里再说一次：

每次操作是在赋值，也就是覆盖之前的信息(这也正是选择线段树来维护而不是分块等数据结构的理由)

具体代码实现可以看一下我写的：

    inline void f(int rt,int l,int r,int v){

    //rt为当前接受信息的线段树节点编号

    //l为该节点包含区间的左端点，r为右端点

    //v为父节点的lazy tag值

        tag[rt]=v,sum[rt]=v*(r-l+1);//该题正确写法

        /*tag[rt]+=v,sum[rt]+=v*(r-l+1)*/

        //一般写法，区别就在于+=和=，小小的=就帮我们实现了覆盖操作

    }

    inline void pushdown(int rt,int l,int r,int mid){

    	//由于涉及到赋为0的操作，所以我用了-1表示lazy tag为空的状态

    	if(tag[rt]!=-1){

            f(lc(rt),l,mid,tag[rt);

            f(rc(rt),mid+1,r,tag[rt]);

            tag[rt]=-1;

        }

    }

坑点三：输出出锅

其实这一点还是比较好处理的，不过我第一次还是没有直接写对(还是涉及到读题的问题)

题目是这样说的：

输出文件的第\(i\)行输出\(1\)个整数，为第\(i\)步操作中改变安装状态的软件包数。

也就是说我们每次输出的是变化量而并非操作后的总数，具体实现的话只需要在每次操作前事先记录一下总量\(t_1\)，再记录一下每次操作完后的新的总量\(t_2\)，输出\(\vert t_1-t_2 \vert\)即可(注意换行...)

参考代码

下面贴上蒟蒻的代码。。。

#include<cstdio>

#include<algorithm>

#define rg register

const int MAXN=100010;

using namespace std;

inline int read(){

    int s=0;bool f=false;char c=getchar();

    while(c<'0'||c>'9')f|=(c=='-'),c=getchar();

    while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();

    return (f)?(-s):(s);

}

int n,m;

int tot,head[MAXN],nxt[MAXN],ver[MAXN];

inline void Add_edge(int u,int v){

    nxt[++tot]=head[u],head[u]=tot,ver[tot]=v;

}

int sum[MAXN<<2],tag[MAXN<<2];

inline int lc(int rt){return rt<<1;}

inline int rc(int rt){return rt<<1|1;}

inline void pushup(int rt){

    sum[rt]=sum[lc(rt)]+sum[rc(rt)];

}

inline void f(int rt,int l,int r,int v){

    tag[rt]=v,sum[rt]=v*(r-l+1);

}

inline void pushdown(int rt,int l,int r,int mid){

    if(tag[rt]!=-1){

        f(lc(rt),l,mid,tag[rt]);

        f(rc(rt),mid+1,r,tag[rt]);

        tag[rt]=-1;

    }

}

inline void update(int rt,int l,int r,int x,int y,int v){

    if(l>y||r<x) return;

    if(x<=l&&r<=y) return f(rt,l,r,v);

    int mid=(l+r)>>1;

    pushdown(rt,l,r,mid);

    update(lc(rt),l,mid,x,y,v);

    update(rc(rt),mid+1,r,x,y,v);

    pushup(rt);

}

inline int query(int rt,int l,int r,int x,int y){

    if(l>y||r<x) return 0;

    if(x<=l&&r<=y) return sum[rt];

    int mid=(l+r)>>1;

    pushdown(rt,l,r,mid);

    return query(lc(rt),l,mid,x,y)+query(rc(rt),mid+1,r,x,y);

}

int top[MAXN],seg[MAXN];

int dep[MAXN],siz[MAXN],son[MAXN],father[MAXN];

inline void dfs1(int u,int fa){

    siz[u]=1;

    father[u]=fa;

    dep[u]=dep[fa]+1;

    for(rg int v,i=head[u];i;i=nxt[i])

        if(!dep[v=ver[i]]){

            dfs1(v,u),siz[u]+=siz[v];

            if(siz[v]>siz[son[u]]) son[u]=v;

        }

}

inline void dfs2(int u,int topf){

    top[u]=topf;

    seg[u]=++seg[0];

    if(!son[u]) return;

    dfs2(son[u],topf);

    for(rg int v,i=head[u];i;i=nxt[i])

        if(!top[v=ver[i]]) dfs2(v,v);

}

inline void uptRange(int x,int y,int v){

    int fx=top[x],fy=top[y];

    while(fx!=fy){

        if(dep[fx]>dep[fy]){

            update(1,1,n,seg[fx],seg[x],v);

            x=father[fx],fx=top[x];

        }

        else{

            update(1,1,n,seg[fy],seg[y],v);

            y=father[fy],fy=top[y];

        }

    }

    if(dep[x]<dep[y])

        update(1,1,n,seg[x],seg[y],v);

    else

        update(1,1,n,seg[y],seg[x],v);

}

inline void uptSon(int x,int v){

    update(1,1,n,seg[x],seg[x]+siz[x]-1,v);

}

int main(){

    n=read();

    for(rg int fa,i=2;i<=n;i++)

        fa=read()+1,Add_edge(fa,i);

    fill(sum+1,sum+n+1,0);

    fill(tag+1,tag+n+1,-1);

    //fill 这个函数是algorithm库里的一个函数，用法与sort类似，用于实现数组的初始化

    //之所以没写memset是因为一开始以为不能用memset初始化负数，不过好像可以？

    dfs1(1,0);

    dfs2(1,1);

    m=read();

    char s[20];

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

        scanf("%s",s);

        int x=read()+1;

        int t1=sum[1];

        if(s[0]=='i'){

            uptRange(x,1,1);

            printf("%d\n",abs(t1-sum[1]));

        }

        else{

            uptSon(x,0);

            printf("%d\n",abs(t1-sum[1]));

        }

    }

    return 0;

}

完结撒花\(qwq\)

巴特西