【题解】NOI2015软件包管理器

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

实际上就是树链剖分板子题。

对于\(install\)操作，直接查询它到\(0\)节点有多少已经安装了的，再用总数减去它。

对于\(uninstall\)操作，记录一个\(dfs\)序结束时间的\(endseg[]\)数组，直接把\(\left[toseg_i,endseg_i\right]\)全部赋零。

可以把编号加一方便编写

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<bitset>

#include<vector>

#include<map>

#include<ctime>

#include<cstdlib>

#include<set>

#include<bitset>

#include<stack>

#include<list>

#include<cmath>

using namespace std;

#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)

#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)

#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)

#define Max(a,b) ((a)<(b)?(b):(a))

#define Min(a,b) ((a)<(b)?(a):(b))

#define TMP template<class ccf>

typedef long long ll;

TMP inline ccf qr(ccf k){

    char c=getchar();

    ccf x=0;

    int q=1;

    while(c<48||c>57)

    q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

    x=x*10+c-48,c=getchar();

    if(q==-1)

    x=-x;

    return x;

}

const int maxn=1e5+15;

struct E{

    int to,nx;

}e[maxn<<1];

int r[maxn];

int head[maxn];

int toseg[maxn];

int seg[maxn<<2];

int tag[maxn<<2];

int d[maxn];

int top[maxn];

int edseg[maxn];

int son[maxn];

int siz[maxn];

int cnt;

int n,q;

int t1;

inline void add(int fr,int to,bool f){

    e[++cnt]=(E){to,head[fr]};

    head[fr]=cnt;

    if(f)

    add(to,fr,0);

}

void dfs1(int now,int last){

    //cout<<now<<last<<endl;

    siz[now]=1;

    r[now]=last;

    d[now]=d[last]+1;

    ERP(t,now){

    if(e[t].to!=last){

        dfs1(e[t].to,now);

        siz[now]+=siz[e[t].to];

        if(siz[e[t].to]>siz[son[now]])

        son[now]=e[t].to;

    }

    }

}

int dcnt;

void dfs2(int now,int last){

    toseg[now]=++dcnt;

    top[now]=last;

    if(son[now])

    dfs2(son[now],last);

    ERP(t,now)

    if(e[t].to!=r[now]&&e[t].to!=son[now])

        dfs2(e[t].to,e[t].to);

    edseg[now]=dcnt;

}

#define midd register int mid=(l+r)>>1

#define pushup(x) seg[x]=seg[(x)<<1]+seg[(x)<<1|1]

inline void pushdown(int pos,int l,int r){

    if(tag[pos]==-1)

    return;

    midd;

    tag[pos<<1]=tag[pos<<1|1]=tag[pos];

    if(tag[pos]){

    seg[pos<<1]=(mid-l+1);

    seg[pos<<1|1]=(r-mid);

    }

    else

    seg[pos<<1]=seg[pos<<1|1]=0;

    tag[pos]=-1;

}

#define lef L,R,l,mid,pos<<1

#define rgt L,R,mid+1,r,pos<<1|1

void upd(int k,int L,int R,int l,int r,int pos){

    if(L>r||R<l)

    return;

    if(L<=l&&r<=R){

    tag[pos]=k;

    if(k)

        seg[pos]=r-l+1;

    else

        seg[pos]=0;

    return;

    }

    midd;

    pushdown(pos,l,r);

    if(L<=mid)upd(k,lef);

    if(R>mid)upd(k,rgt);

    pushup(pos);

}

int ask(int L,int R,int l,int r,int pos){

    if(L>r||R<l)

    return 0;

    if(L<=l&&r<=R)

    return seg[pos];

    midd;

    int ret=0;

    pushdown(pos,l,r);

    ret=ask(lef)+ask(rgt);

    pushup(pos);

    return ret;

}

#define Swap(x,y) ((x)^=(y)^=(x)^=(y))

#define all 1,n,1

inline int install(int u,int v){

    int ret=0;

    while(top[u]!=top[v]){

    if(d[u]<d[v])

        Swap(u,v);

    ret+=toseg[u]-toseg[top[u]]+1-ask(toseg[top[u]],toseg[u],all);

    upd(1,toseg[top[u]],toseg[u],all);

    u=r[top[u]];

    }

    if(toseg[u]<toseg[v])

    Swap(u,v);

    ret+=toseg[u]-toseg[v]+1-ask(toseg[v],toseg[u],all);

    upd(1,toseg[v],toseg[u],all);

    return ret;

}

inline int uninstall(int u){

    int ret=0;

    ret=ask(toseg[u],edseg[u],all);

    upd(0,toseg[u],edseg[u],all);

    return ret;

}

char c[50];

int main(){

#ifndef ONLINE_JUDGE

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=qr(1);

    RP(t,2,n){

    t1=qr(1)+1;

    add(t,t1,1);

    }

    dfs1(1,0);

    dfs2(1,1);

    q=qr(1);

    RP(t,1,q){

    cin>>c;

    t1=qr(1)+1;

    if((c[0])==('i'))

        printf("%d\n",install(t1,1));

    else

        printf("%d\n",uninstall(t1));

    }

    return 0;

}