题解 P2146 【[NOI2015]软件包管理器】

P2146 题解

关于树链剖分的教程

思路

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

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


Tips:

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

代码

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
162
163
164
165
166
167
168
169
170
171
172
#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;
}
文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/题解-P2146-【-NOI2015-软件包管理器】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏