(luogu2146) 软件包管理器 (NOI2015)

发表于 分类于 ， ，

树链剖分笔记索引

思路:

一样的是树链剖分 + 线段树

不同的是这个线段树和之前那道有所不同

每个区间记录区间内已安装的安装包数量，这样操作就简单了

代码:

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
const int Mn(100005);
int qrd()    //快读
{
    int x(0); char c(getchar());
    while(!isdigit(c))   c=getchar();
    while(isdigit(c))
    { x=x*10+c-'0'; c=getchar(); }
    return x;
}
int n;
char opr[20];    //读入用字符串
struct edge    //一样的边表
{
    int e,nt;
}ed[Mn<<1];
int vs[Mn],ec(0);
void adde(int s,int e)
{
    ed[++ec].e=e; ed[ec].nt=vs[s];
    vs[s]=ec;
}
int dp[Mn],pa[Mn],sz[Mn],hs[Mn];    //还是一样的操作
void dfs1(int x)
{
    sz[x]=1;
    for(int e(vs[x]);e;e=ed[e].nt)
    {
        int& ntn(ed[e].e);
        if(!dp[ntn])
        {
            dp[ntn]=dp[x]+1;
            dfs1(ntn);
            sz[x] += sz[ntn];
            if(sz[hs[x]]<sz[ntn])   hs[x]=ntn;
        }
    }
}
int tp[Mn],vp[Mn],dc(0);
void dfs2(int x)
{
    vp[x] = ++dc;
    if(hs[x])
    { tp[hs[x]]=tp[x]; dfs2(hs[x]); }
    for(int e(vs[x]);e;e=ed[e].nt)
    {
        int& ntn(ed[e].e);
        if(dp[ntn]>dp[x] && ntn!=hs[x])
        {
            tp[ntn] = ntn;
            dfs2(ntn);
        }
    }
}
struct sn    // 线段树结点
{
    int l,r,n1,t;    // 左端点, 右端点, 已安装数量, 懒标记
}t[Mn<<2];
void bud(int l,int r,int rt=1)    //建树
{
    sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    nd.t=-1;
    if(l==r)
    {
        nd.l=nd.r=l;
        nd.n1=0;
    }
    else
    {
        int mid((l+r)>>1);
        bud(l,mid,rt<<1);
        bud(mid+1,r,rt<<1|1);
        nd.l=l, nd.r=r;
        nd.n1=0;
    }
}
void pd(int rt)    // 下放标记
{
    sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    if(nd.t!=-1)
    {
        ls.t=rs.t=nd.t;
        ls.n1 = (nd.t ? (ls.r-ls.l+1) : 0);    //将左右儿子全部置1
        rs.n1 = (nd.t ? (rs.r-rs.l+1) : 0);
        nd.t = -1;
    }
}
int ist(int ml,int mr,int rt=1)    //安装
{
    sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    int ret(0);
    if(nd.l>=ml && nd.r<=mr)    //全部置1并打上标记
    {
        ret = (nd.r-nd.l+1)-nd.n1;    //记录该区间状态修改数
        nd.n1 = nd.r-nd.l+1;
        nd.t = 1;
    }
    else
    {
        pd(rt);
        if(ml<=ls.r) ret+=ist(ml,mr,rt<<1);
        if(mr>=rs.l) ret+=ist(ml,mr,rt<<1|1);
        nd.n1 = ls.n1+rs.n1;
    }
    return ret;
}
int dlt(int ml,int mr,int rt=1)    //删除
{
    sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]);
    int ret(0);
    if(nd.l>=ml && nd.r<=mr)    //全部置0
    {
        ret = nd.n1;    //记录该区间状态修改数
        nd.n1 = 0;
        nd.t = 0;
    }
    else
    {
        pd(rt);
        if(ml<=ls.r) ret+=dlt(ml,mr,rt<<1);
        if(mr>=rs.l) ret+=dlt(ml,mr,rt<<1|1);
        nd.n1 = ls.n1+rs.n1;
    }
    return ret;
}
int main()
{
    cin >> n;
    for(int i(2);i<=n;++i)
    {
        int p(qrd());
        pa[i] = p+1;
        adde(p+1,i), adde(i,p+1);
    }
    dp[1]=1; dfs1(1);
    tp[1]=1; dfs2(1);
    bud(1,n);
    int q(qrd());
    while(q--)
    {
        scanf("%s",opr);
        int x(qrd());
        ++x;
        if(opr[0]=='i')    //安装, 从需安装安装包到根结点的所有安装包全部安装
        {
            int ans(0);
            while(x)
            {
                ans += ist(vp[tp[x]],vp[x]);
                x = pa[tp[x]];
            }
            printf("%d\n",ans);
        }
        else if(opr[0]=='u')    //删除, 把子树中的安装包全部删除
            printf("%d\n",dlt(vp[x],vp[x]+sz[x]-1));
    }
    return 0;
}