[NOI2015]软件包管理器 题解
题目地址:洛谷:【P2146】[NOI2015]软件包管理器 – 洛谷、BZOJ:Problem 4196. — [Noi2015]软件包管理器
题目描述
Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软件包管理器。
你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除0号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而0号软件包不依赖任何一个软件包。依赖关系不存在环(若有m(m≥2)个软件包A1,A2,A3,⋯,Am,其中A1依赖A2,A2依赖A3,A3依赖A4,……,A[m-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
输出样例#1:
3 1 3 2 3
输入样例#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
输出样例#2:
1 3 2 1 3 1 1 1 0 1
说明
n,q<=10000
题解
考虑安装软件包即安装从根0到该点的路径上的所有软件包,则先求和算出改变数再链改值。卸载软件包即卸载其子树中所有软件包,则先求和算出改变值再子树改值。
由于0号点不好处理,我们给点的编号加1。
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF
: *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
inline int readop() {
char c;
int res = 1;
while(!isalpha(c = fgc()));
while(isalpha(c)) {
if(c == 'u') res = 2;
c = fgc();
}
return res;
}
const int MAXN = 1000005;
int n, dfn[MAXN], ptn[MAXN];
std::vector<int> gra[MAXN];
// Segment Tree
#define lch o << 1
#define rch (o << 1) | 1
#define mid ((l + r) >> 1)
int val[MAXN << 2], tag[MAXN << 2];
inline void pushdown(int o, int l, int r) {
if(tag[o] != -1) {
tag[lch] = tag[rch] = tag[o];
val[lch] = tag[o] * (mid - l + 1);
val[rch] = tag[o] * (r - mid);
tag[o] = -1;
}
}
inline void merge(int o) {
val[o] = val[lch] + val[rch];
}
inline void modify(int o, int l, int r, int ll, int rr, int v) {
if(l >= ll && r <= rr) {
val[o] = v * (r - l + 1);
tag[o] = v;
return;
}
pushdown(o, l, r);
if(ll <= mid) modify(lch, l, mid, ll, rr, v);
if(rr > mid) modify(rch, mid + 1, r, ll, rr, v);
merge(o);
}
inline int query(int o, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) {
return val[o];
}
pushdown(o, l, r);
int res = 0;
if(ll <= mid) res += query(lch, l, mid, ll, rr);
if(rr > mid) res += query(rch, mid + 1, r, ll, rr);
return res;
}
int fa[MAXN], siz[MAXN], dep[MAXN], top[MAXN], son[MAXN], clk;
inline void dfs1(int u) {
siz[u] = 1;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
dfn[u] = ++clk;
ptn[dfn[u]] = u;
top[u] = tp;
if(son[u]) {
dfs2(son[u], tp);
}
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline void modify(int x, int y, int z) {
int tx = top[x], ty = top[y];
while(tx != ty) {
if(dep[tx] > dep[ty]) {
std::swap(x, y);
std::swap(tx, ty);
}
modify(1, 1, n, dfn[ty], dfn[y], z);
y = fa[ty];
ty = top[y];
}
if(dep[x] > dep[y]) {
std::swap(x, y);
}
modify(1, 1, n, dfn[x], dfn[y], z);
}
inline int query(int x, int y) {
int tx = top[x], ty = top[y];
int res = 0;
while(tx != ty) {
if(dep[tx] > dep[ty]) {
std::swap(x, y);
std::swap(tx, ty);
}
res += query(1, 1, n, dfn[ty], dfn[y]);
y = fa[ty];
ty = top[y];
}
if(dep[x] > dep[y]) {
std::swap(x, y);
}
res += query(1, 1, n, dfn[x], dfn[y]);
return res;
}
inline void modify(int x, int z) {
modify(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z);
}
inline int query(int x) {
return query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);
}
int q, op, x;
int main() {
memset(tag, -1, sizeof(tag));
n = readint();
for(int i = 2; i <= n; i++) {
x = readint() + 1;
gra[x].push_back(i);
gra[i].push_back(x);
}
dfs1(1);
dfs2(1, 1);
q = readint();
while(q--) {
op = readop(); x = readint() + 1;
if(op == 1) {
printf("%d\n", dep[x] + 1 - query(1, x));
modify(1, x, 1);
} else {
printf("%d\n", query(x));
modify(x, 0);
}
}
return 0;
}