[BZOJ 4196][NOI 2005]パッケージマネージャ(チェーン断面+dfsシーケンス)


テーマの説明
コンベヤー?ドア
問題を解く
チェーンは練習問題を切り開いて、構想はとてもとてもとても良いです.最初は小さなバグが出ました.自分でデータ構造を書いた時の成功率を疑っています.
コード
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_n=1e5+5;
const int max_e=max_n*2;
const int max_tree=max_n*5;

int n,q,x,N,ans;
char s[20];
int tot,point[max_n],next[max_e],v[max_e];
int size[max_n],h[max_n],father[max_n],son[max_n];
int top[max_n],in[max_n],out[max_n];
int sum[max_tree],delta[max_tree];

inline void addedge(int x,int y){
    ++tot; next[tot]=point[x]; point[x]=tot; v[tot]=y;
    ++tot; next[tot]=point[y]; point[y]=tot; v[tot]=x;
}

inline void dfs_1(int x,int fa,int dep){
    size[x]=1; h[x]=dep; father[x]=fa;
    int maxson=0;

    for (int i=point[x];i;i=next[i])
      if (v[i]!=fa){
        dfs_1(v[i],x,dep+1);
        size[x]+=size[v[i]];
        if (maxson<size[v[i]]){
            maxson=size[v[i]];
            son[x]=v[i];
        }
      }
}

inline void dfs_2(int x,int fa){
    if (son[fa]!=x) top[x]=x;
    else top[x]=top[fa];
    in[x]=++N;

    if (son[x]) dfs_2(son[x],x);
    for (int i=point[x];i;i=next[i])
      if (v[i]!=fa&&v[i]!=son[x])
        dfs_2(v[i],x);

    out[x]=N;
}

inline void update(int now){
    sum[now]=sum[now<<1]+sum[now<<1|1];
}

inline void pushdown(int now,int l,int r,int mid){
    if (delta[now]>=0){
        sum[now<<1]=delta[now]*(mid-l+1);
        delta[now<<1]=delta[now];
        sum[now<<1|1]=delta[now]*(r-mid);
        delta[now<<1|1]=delta[now];
        delta[now]=-1;
    }
}

inline void interval_change(int now,int l,int r,int lrange,int rrange,int v){
    int mid=(l+r)>>1;
    if (lrange<=l&&r<=rrange){
        sum[now]=(r-l+1)*v;
        delta[now]=v;
        return;
    }

    pushdown(now,l,r,mid);
    if (lrange<=mid)
      interval_change(now<<1,l,mid,lrange,rrange,v);
    if (mid+1<=rrange)
      interval_change(now<<1|1,mid+1,r,lrange,rrange,v);
    update(now);
}

inline int query(int now,int l,int r,int lrange,int rrange){
    int mid=(l+r)>>1,ans=0;
    if (lrange<=l&&r<=rrange) return sum[now];

    pushdown(now,l,r,mid);
    if (lrange<=mid)
      ans+=query(now<<1,l,mid,lrange,rrange);
    if (mid+1<=rrange)
      ans+=query(now<<1|1,mid+1,r,lrange,rrange);
    return ans;
}

inline void QUERY(int u,int t){
    int f1=top[u],f2=top[t],ans=0;
    while (f1!=f2){
        if (h[f1]<h[f2]){
            swap(f1,f2);
            swap(u,t);
        }
        ans+=query(1,1,N,in[f1],in[u]);
        u=father[f1];
        f1=top[u];
    }
    if (in[u]>in[t]) swap(u,t);
    ans+=query(1,1,N,in[u],in[t]);
    int cnt=h[x];
    printf("%d
"
,cnt-ans); } inline void CHANGE(int u,int t){ int f1=top[u],f2=top[t],ans=0; while (f1!=f2){ if (h[f1]<h[f2]){ swap(f1,f2); swap(u,t); } interval_change(1,1,N,in[f1],in[u],1); u=father[f1]; f1=top[u]; } if (in[u]>in[t]) swap(u,t); interval_change(1,1,N,in[u],in[t],1); } inline void INSTALL(int u,int t){ QUERY(u,t); CHANGE(u,t); } inline void UNINSTALL(int x){ ans=query(1,1,N,in[x],out[x]); printf("%d
"
,ans); interval_change(1,1,N,in[x],out[x],0); } int main(){ // freopen("input.txt","r",stdin); scanf("%d",&n); for (int i=1;i<n;++i){ scanf("%d",&x); ++x; addedge(x,i+1); } dfs_1(1,0,1); dfs_2(1,0); //0 1 memset(sum,0,sizeof(sum)); memset(delta,128,sizeof(delta)); scanf("%d",&q); for (int i=1;i<=q;++i){ scanf("%s",s); scanf("%d",&x); ++x; if (s[0]=='i') INSTALL(1,x); else UNINSTALL(x); } }
締め括りをつける
注意線分樹における初期状態(特にデルタ)は、線分樹に現れる状態と重ね合わせてはいけません(本題の0のように).線分樹は直接修正しますか?それとも加減しますか?