BZOJ4196 [Noi2015]软件包管理器（洛谷P2146）

树链剖分

BZOJ题目传送门

洛谷题目传送门

看懂题目后就是比较裸的树剖了。安装就是把x到根节点都改为1，卸载就是把x的子树都改为0。

注意询问的内容。

论10s时限跑了9.9s的快感。

代码：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define F inline
using namespace std;
struct tree{ int l,r,x,f; }t[N<<];
struct edge{ int nxt,to; }ed[N<<];
int n,m,k,p,h[N],fa[N],sz[N],to[N],dep[N],tp[N],L[N],R[N];
F char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    return l==r?EOF:*l++;
}
F int _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)&&ch!='i'&&ch!='u') ch=readc();
    if (ch=='i'||ch=='u'){
        char s=ch;
        for (int i=;i<=+*(s=='u');i++) ch=readc();
        return s;
    }
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
F void writec(int x){ if (x>) writec(x/); putchar(x%+); }
F void _write(int x){ writec(x),puts(""); }
#define addedge(x,y) ed[++k]=(edge){h[x],y},h[x]=k
void dfs1(int x){
    sz[x]=,dep[x]=dep[fa[x]]+;
    for (int i=h[x],v;i;i=ed[i].nxt){
        dfs1(v=ed[i].to),sz[x]+=sz[v];
        if (sz[v]>sz[to[x]]) to[x]=v;
    }
}
void dfs2(int x){
    L[x]=++p;
    if (to[x]) tp[to[x]]=tp[x],dfs2(to[x]);
    for (int i=h[x],v;i;i=ed[i].nxt)
        if ((v=ed[i].to)!=to[x])
            tp[v]=v,dfs2(v);
    R[x]=p;
}
void build(int x,int l,int r){
    t[x].l=l,t[x].r=r,t[x].f=-;
    if (l==r) return; int mid=l+r>>;
    build(x<<,l,mid),build(x<<|,mid+,r);
}
F void pshd(int x){
    t[x<<].f=t[x<<|].f=t[x].f,t[x].f=-;
    t[x<<].x=(t[x<<].r-t[x<<].l+)*t[x<<].f;
    t[x<<|].x=(t[x<<|].r-t[x<<|].l+)*t[x<<|].f;
}
void mdfy(int x,int l,int r,int w){
    if (t[x].l>r||t[x].r<l) return;
    if (t[x].l>=l&&t[x].r<=r){
        t[x].x=(t[x].r-t[x].l+)*w;
        t[x].f=w; return;
    }
    if (~t[x].f) pshd(x);
    mdfy(x<<,l,r,w),mdfy(x<<|,l,r,w);
    t[x].x=t[x<<].x+t[x<<|].x;
}
int srch(int x,int l,int r){
    if (t[x].l>r||t[x].r<l) return ;
    if (t[x].l>=l&&t[x].r<=r) return t[x].x;
    if (~t[x].f) pshd(x);
    return srch(x<<,l,r)+srch(x<<|,l,r);
}
void nsrt(int x){
    while (tp[x]!=)
        mdfy(,L[tp[x]],L[x],),x=fa[tp[x]];
    mdfy(,,L[x],);
}
int find(int x){
    int ans=;
    while (tp[x]!=)
        ans+=srch(,L[tp[x]],L[x]),x=fa[tp[x]];
    return ans+srch(,,L[x]);
}
int main(){
    n=_read();
    for (int i=;i<=n;i++) fa[i]=_read()+,addedge(fa[i],i);
    dfs1(),tp[]=,dfs2(),build(,,n);
    for (m=_read();m;m--){
        int f=_read(),x=_read()+,y;
        if (f=='i') _write(dep[x]-find(x)),nsrt(x);
        else _write(srch(,L[x],R[x])),mdfy(,L[x],R[x],);
    }
    return ;
}