[UOJ 128][NOI 2015]パッケージマネージャ(ツリー分割+セグメントツリー)

#128.【NOI 2015】パッケージマネージャ
LinuxユーザーとOS Xユーザーは、パッケージマネージャに慣れていないに違いありません.パッケージマネージャを使用すると、1行のコマンドでパッケージをインストールできます.パッケージマネージャは、ソフトウェアソースからパッケージをダウンロードするのに役立ちます.同時に、すべての依存(つまり、このパッケージをインストールするインストールに依存する他のパッケージをダウンロードする)を自動的に解決し、すべての構成を完了します.Debian/Ubuntuで使用されているapt-get、Fedora/centOSで使用されているyum、およびOS Xで使用可能なhomebrewは、優れたパッケージマネージャです.
あなたは自分のパッケージマネージャを設計することにしました.ソフトウェアパッケージ間の依存問題を解決することは避けられません.パッケージA A AがパッケージBに依存している場合、パッケージA Aをインストールする前に、パッケージBをインストールする必要があります.また、パッケージB Bをアンインストールする場合は、パッケージA Aをアンインストールする必要があります.すべてのパッケージ間の依存関係を取得しました.また、あなたの前の仕事のため、0 0番のパッケージを除いて、あなたのマネージャの中のパッケージは1つのパッケージに依存し、1つのパッケージに依存しますが、0番のパッケージはいずれのパッケージにも依存しません.依存関係にループは存在しない(m m(m≧2)(m≧2)個のパッケージA 1,A 2,A 3,...,AmA 1,A 2,A 3,...,A 1 A 1がA 2 A 2 A 2,A 2 A 2がA 3 A 3,A 3 A 3がA 4 A 4,...,Am−1 A m−1がAm A 1 mに依存し,Am A mがA 1 A 1に依存するということは,このm個のパッケージの依存関係がループを構成しているという)はもちろん,一つのパッケージも自分に依存しない.
今、パッケージマネージャに依存ソリューションを書きます.フィードバックによると、ユーザーは、パッケージをインストールおよびアンインストールするときに、この操作が実際にどのくらいのパッケージのインストール状態を変更するか(すなわち、インストール操作がインストールされていないパッケージを何個インストールするか、またはインストール操作がインストールされているパッケージを何個アンインストールするか)を迅速に知りたいと考えています.あなたのタスクは、この部分を実現することです.インストール済みのパッケージをインストールしたり、インストールされていないパッケージをアンインストールしたりしても、パッケージのインストール状態は変わりません.つまり、この場合、インストール状態を変更するパッケージの数は0です.
入力フォーマット
入力ファイルの1行目には、パッケージの合計数を示す1つの正の整数nが含まれている.パッケージは0から番号付けされます.
その後、1行はn−1 n−1個の整数を含み、隣接する整数間は、1,2,3,…,n−2,n−1,2,3,…,n−2,n−1,n−1,n−1,n−1,n−1番のパッケージ依存パッケージの番号をそれぞれ表す単一のスペースで区切られる.
次の行は、1つの正の整数q qを含み、クエリの総数を表す.
その後q行、行ごとに1つの問い合わせがあります.質問は2つに分けられます.

install x:インストールパッケージx

を示す

uninstall x:アンインストールパッケージx

を示す
各パッケージのインストールステータスを維持する必要があります.最初はすべてのパッケージがインストールされていません.各操作について、この操作を出力すると、どのくらいのパッケージのインストールステータスが変更され、その後、この操作を適用する必要があります(つまり、メンテナンスのインストールステータスを変更します).
出力フォーマット
出力ファイルにはq q行が含まれます.
出力ファイルのi行目は1つの整数を出力し、iステップ目の操作でインストール状態を変更したパッケージ数です.
サンプル1
input

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

output

3
1
3
2
3

explanation
最初はすべてのパッケージがインストールされていませんでした.
5番のパッケージをインストールするには、0,1,5 0,1,5の3つのパッケージをインストールする必要があります.
その後、6番のパッケージをインストールし、6番のパッケージをインストールするだけです.このとき,0,1,5,6 0,1,5,6の4つのパッケージがインストールされた.
1番のパッケージをアンインストールするには、1,5,6 1,5,6の3つのパッケージをアンインストールする必要があります.この時点で、0番のパッケージだけがインストールされています.
その後、4番のパッケージをインストールするには、1,4 1,4の2つのパッケージをインストールする必要があります.このとき0,1,4 0,1,4は実装状態にある.
最後に、0 0番のパッケージをアンインストールすると、すべてのパッケージがアンインストールされます.
サンプル2
input

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

output

1
3
2
1
3
1
1
1
0
1

サンプル3
サンプルデータのダウンロードを参照してください.
制限と約束
テストポイント番号
n nの規模
q qの規模
コメント
1
n=5000 n = 5000
q=5000 q = 5000
2
3
n=100000 n = 100000
q=100000 q = 100000
データにアンインストール操作は含まれていません
4
5
n=100000 n = 100000
q=100000 q = 100000
iと番号付けされたパッケージに依存するパッケージ番号は、[0,i−1][0,i−1]内で均一にランダムである.各動作のパッケージ番号は[0,n−1][0,n−1]内で均一にランダムである.
6
7
8
9
n=100000 n = 100000
q=100000 q = 100000
10
11
12
13
14
15
16
17
18
19
20
時間制限:1 s 1 s
スペース制限:512 MB 512 MB
考え方&分析
    この問題は、1つのソフトウェアがダウンロードされていないことを0で表し、1はすでにダウンロードされていることを示しています.この問題には2つの操作があり、uninstall xを操作することはxをルートとするサブツリーのすべてのinstall済みのソフトウェアをアンインストールすることであり、xと他のサブツリーの値をすべて0に割り当てることである.一方,install xを操作すると,ルートからxへのパス上のすべてのパッケージ(xを含む)をすべてダウンロードし,1つのパス上のすべてのポイントに1を付与すると見なすことができる.簡単に分析すると、これはツリーの裸の問題であり、セグメントツリーですべての値を維持すればよいことがわかります.答えについては,修正するたびにルートのsumを記録し,sumと操作後のルートのsumの絶対値が答えである.
Code

#include
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=f;
}
#define rd(x) read(x)
#define r2(x,y) rd(x),rd(y)
#define r3(x,y,z) r2(x,y),rd(z)
#define r4(x,y,z,o) r2(x,y),r2(z,o)
#define ls o<<1
#define rs o<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
const int maxn=1000010;
int n,q,fa[maxn],dep[maxn],tp[maxn],son[maxn],id[maxn],dfs_clock,sz[maxn];
vector<int>G[maxn];
struct Seg {
    int sum,upd;
    inline void init() {
        sum=0;
        upd=-1;
    }
}t[maxn<<2];
inline void pushup(int o) {
    t[o].sum=t[ls].sum+t[rs].sum;
}
inline void pushdown(int o,int l,int r) {
    if(t[o].upd!=-1) {
        int mid=(l+r)>>1;
        t[ls].sum=t[o].upd*(mid-l+1);
        t[rs].sum=t[o].upd*(r-mid);
        t[ls].upd=t[rs].upd=t[o].upd;
        t[o].upd=-1;
    }
}
inline void dfs1(int u) {
    sz[u]=1;
    for(unsigned i=0;iint v=G[u][i];
        if(v==fa[u])
            continue;
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v);
        sz[u]+=sz[v];
        if(!son[u]||sz[son[u]]inline void dfs2(int u,int p) {
    id[u]=++dfs_clock;
    tp[u]=p;
    if(!son[u])
        return;
    dfs2(son[u],p);
    for(unsigned i=0;iint v=G[u][i];
        if(v==fa[u]||v==son[u])
            continue;
        dfs2(v,v);
    }
}
inline void build(int o,int l,int r) {
    t[o].init();
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(o);
}
inline void upset(int o,int l,int r,int ql,int qr,int s) {
    pushdown(o,l,r);
    if(l==ql&&r==qr) {
        //cout<
        t[o].sum=s*(r-l+1);
        t[o].upd=s;
        //cout<
        return;
    }
    int mid=(l+r)>>1;
    if(qr<=mid)
        upset(lson,ql,qr,s);
    else if(ql>mid)
        upset(rson,ql,qr,s);
    else {
        upset(lson,ql,mid,s);
        upset(rson,mid+1,qr,s);
    }
    pushup(o);
}
inline void subset1(int x) {
    upset(1,1,n,id[x],id[x]+sz[x]-1,0);
}
inline void subset2(int x) {
    //cout<
    while(tp[x]!=1) {
    //cout<
        upset(1,1,n,id[tp[x]],id[x],1);
        x=fa[tp[x]];
    }
    //cout<
    upset(1,1,n,1,id[x],1);
}
int main() {
    rd(n);
    for(int i=2,x;i<=n;i++) {
        rd(x);x++;
        G[x].push_back(i);
        G[i].push_back(x);
    }
    dep[1]=1;fa[1]=-1;
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    /*for(int i=1;i<=n;i++)
        cout<rd(q);
    while(q--) {
        char s[100];int x;
        scanf("%s",s+1);rd(x);x++;
        int res=t[1].sum;
        if(s[1]=='u') {
            subset1(x);//cout<
            printf("%d
",abs(res-t[1].sum));
        }
        else {
            subset2(x);//cout<
            printf("%d
",abs(res-t[1].sum));
        }
    }
}