NKOJ 3423 (NOI 2015) 软件包管理器 （树链剖分+线段树）

发表于 |
字数统计: 1,714字 | 阅读时长 ≈ 8min

P3423【NOI2015 Day1】软件包管理器

问题描述

Linux用户和OS X用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其他软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的是yum，以及OS X下可用的homebrew都是优秀的软件包管理器。
你决定设计你自己的软件包管理器。不可避免的，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包B以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m>=2)个软件包A1,A2,A2依赖A3,…,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，Am-1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入格式

/从manager.in中读入数据。/
输入文件的第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。
随后一行包含n-1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,…,n-2,n-1号软件包依赖的软件包编号。
接下来一行包含1个整数q，表示询问的总数。
之后的q行，每行1个询问。询问分为两种：
●install x：表示安装软件包x
●uninstall x：表示卸载软件包x
你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态，对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式

/输出到文件manager.out中。/
输出文件包括q行。
输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。

样例输入1：

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

样例输入2：

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9
样例输出

样例输出1：

3
1
3
2
3

样例输出2：

1
3
2
1
3
1
1
1
0
1

这里写图片描述

此题显然树链剖分，安装操作容易处理，卸载操作其实也很简单，因为剖分出来的ID在一棵子树上肯定是连续的一段，那么直接记下这棵子树的左右界就行了，然后就是线段树区间修改。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
int n,dep[N],fa[N],son[N],top[N],id[N],Mid[N],VT;
int TOT,LA[N],NE[N],EN[N];
int ls[N*5],rs[N*5],v[N*5],w[N*5],lazy[N*5],tot;
void ADD(int x,int y)
{
    TOT++;
    EN[TOT]=y;
    NE[TOT]=LA[x];
    LA[x]=TOT;
}
int FHE(int x,int f)
{
    int i,y,t=0,s=1,tmp;
    fa[x]=f;
    dep[x]=dep[f]+1;
    for(i=LA[x];i;i=NE[i])
    {
        y=EN[i];
        if(y!=f)
        {
            tmp=FHE(y,x);s+=tmp;
            if(tmp>t)t=tmp,son[x]=y;
        }
    }
    return s;
}
void CHE(int x,int f)
{
    int i,y;
    id[x]=++VT;
    top[x]=f;
    if(son[x])CHE(son[x],f);
    for(i=LA[x];i;i=NE[i])
    {
        y=EN[i];
        if(y!=fa[x]&&y!=son[x])CHE(y,y);
    }
    Mid[x]=VT;
}
int BT(int x,int y)
{
    int p=++tot;
    w[p]=y-x+1;
    if(x<y)
    {
        int mid=x+y>>1;
        ls[p]=BT(x,mid);
        rs[p]=BT(mid+1,y);
    }
    return p;
}
void PD(int p)
{
    if(lazy[p]==1)
    {
        v[ls[p]]=w[ls[p]];
        v[rs[p]]=w[rs[p]];
        lazy[ls[p]]=1;
        lazy[rs[p]]=1;
    }
    else
    {
        v[ls[p]]=0;
        v[rs[p]]=0;
        lazy[ls[p]]=-1;
        lazy[rs[p]]=-1;
    }
    lazy[p]=0;
}
void MD(int p,int l,int r,int x,int y,int d)
{
    if(lazy[p])PD(p);
    if(x<=l&&y>=r){v[p]=w[p]*d;lazy[p]=d==1?1:-1;return;}
    int mid=l+r>>1;
    if(x<=mid&&y>=l)MD(ls[p],l,mid,x,y,d);
    if(x<=r&&y>mid)MD(rs[p],mid+1,r,x,y,d);
    v[p]=v[ls[p]]+v[rs[p]];
}
int GS(int p,int l,int r,int x,int y)
{
    if(lazy[p])PD(p);
    if(x<=l&&y>=r)return v[p];
    int mid=l+r>>1,s=0;
    if(x<=mid&&y>=l)s+=GS(ls[p],l,mid,x,y);
    if(x<=r&&y>mid)s+=GS(rs[p],mid+1,r,x,y);
    return s;
}
void Ins(int x)
{
    int ans=dep[x],k=x;
    while(top[k]!=top[0])
    {
        ans-=GS(1,1,n,id[top[k]],id[k]);
        MD(1,1,n,id[top[k]],id[k],1);
        k=fa[top[k]];
    }
    ans-=GS(1,1,n,id[top[k]],id[k]);
    MD(1,1,n,id[top[k]],id[k],1);
    printf("%d\n",ans);
}
int Uns(int x)
{
    int ans=GS(1,1,n,id[x],Mid[x]);
    printf("%d\n",ans);
    MD(1,1,n,id[x],Mid[x],0);
}
int main_main()
{
    int i,x;char s[20];
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d",&x);
        ADD(x,i);
    }
    FHE(0,0);CHE(0,0);BT(1,n);
    scanf("%d",&i);
    while(i--)
    {
        scanf("%s%d",s,&x);
        if(s[0]=='i')Ins(x);
        else Uns(x);
    }
}
const int main_stack=16;   
char my_stack[128<<20];   
int main() {   
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");   
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");   
  main_main();   
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");   
  return 0;   
}