问题描述

你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除0号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而0号软件包不依赖任何一个软件包。依赖关系不存在环(若有m(m≥2)个软件包A1,A2,A3,…,Am,其中A1依赖A2,A2依赖A3,A3依赖A4,……,Am−1依赖Am,而Am依赖A1,则称这m个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为0。

输入

第1行包含1个整数n,表示软件包的总数。软件包从0开始编号。随后一行包含n−1个整数,相邻整数之间用单个空格隔开,分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个整数q,表示询问的总数。之后q行,每行1个询问。询问分为两种:
install x:表示安装软件包x
uninstall x:表示卸载软件包x
你需要维护每个软件包的安装状态,一开始所有的软件包都处于未安装状态。

对于每个操作,你需要输出这步操作会改变多少个软件包的安装状态,随后应用这个操作(即改变你维护的安装状态)

输出

输出文件包括q行。

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

数据范围

对于全部数据:n<=100000, q<=100000。

思路

我们可以看出这些软件的依赖关系是一棵树。设未安装的节点权值为0,安装的权值为1。

然后install操作就是让x节点到根节点路径上权值为0的节点变为1,并输出权值为0节点个数。uninstall操作就是让x子树权值为1的节点变为0,并输出权值为1节点个数。

然后这就是一个很裸的树剖啦QVQ 线段树上的操作就是将整个区间变为0或1。

但是要注意常数问题!以install操作为例,如果先计算x到根节点权值之和,然后进行修改,再求一遍到根节点之和。这样的常数巨大,在BZOJ上会TLE。QWQ

所以我们可以优化一下,先保存一下整棵树权值之和(就是sum[1]),然后修改,输出整棵树前后权值之差。这样常数就小了不少。

细节

  1. 所有点的编号都要+1,不然树剖时会产生与0号节点有关的bug。
  2. lazytag要注意,初始赋为-1,下传标记时新tag要覆盖掉原tag。
  3. 要注意常数,TLE了一次QWQ

代码

#include <bits/stdc++.h>
#define MAXN 100005
#define INF 1e9
#define ls (l+r<<1)
#define rs (l+r<<1|1)
#define mid (l+r>>1)
using namespace std;

int n, x, q, cnt, head[MAXN], tag[MAXN*4], sum[MAXN*4];
int Index, son[MAXN], f[MAXN], dep[MAXN], size[MAXN], id[MAXN], top[MAXN];
char opt[100];
struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs1(int x, int fa, int deep)
{
    dep[x]=deep; f[x]=fa; size[x]=1;
    int maxson=-1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to, x, deep+1);
        size[x]+=size[to];
        if(size[to]>maxson) maxson=size[to], son[x]=to;
    }
}

void dfs2(int x, int topf)
{
    id[x]= ++Index; top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x], topf);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==son[x] || to==f[x]) continue;
        dfs2(to, to);
    }
}

void down(int root, int l, int r)
{
    if(tag[root]==-1) return;
    sum[ls]=(mid-l+1)*tag[root];
    sum[rs]=(r-mid)*tag[root];
    tag[ls]=tag[root];
    tag[rs]=tag[root];
    tag[root]=-1;
}

void update(int root, int l, int r, int x, int y, int z)
{
    if(x>r || y<l) return ;
    if(x<=l && y>=r)
    {
        sum[root]=(r-l+1)*z;
        tag[root]=z;
        return;
    }
    down(root, l, r);
    update(ls, l, mid, x, y, z);
    update(rs, mid+1, r, x, y, z);
    sum[root]=sum[ls]+sum[rs];
}

void act(int x, int y)
{
    while(top[x]!=1)
    {
        update(1, 1, n, id[top[x]], id[x], y);
        x=f[top[x]];
    }
    update(1, 1, n, id[1], id[x], y);
}

int main()
{
    memset(tag, -1, sizeof(-1));
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &x);
        addedge(i, x+1); 
        addedge(x+1, i);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    scanf("%d", &q);
    for(int i=1; i<=q; i++)
    {
        scanf("%s%d", opt, &x); x++;
        int temp=sum[1];
        if(opt[0]=='i')
        {
            act(x, 1);
            printf("%dn", sum[1]-temp);
        }
        if(opt[0]=='u')
        {
            update(1, 1, n, id[x], id[x]+size[x]-1, 0);
            printf("%dn", temp-sum[1]);
        }
    }
}

1 对 “BZOJ4196 软件包管理器 [树链剖分]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注