[BZOJ 4196][NOI 2005]パッケージマネージャ(チェーン断面+dfsシーケンス)
テーマの説明
コンベヤー?ドア
問題を解く
チェーンは練習問題を切り開いて、構想はとてもとてもとても良いです.最初は小さなバグが出ました.自分でデータ構造を書いた時の成功率を疑っています.
コード
注意線分樹における初期状態(特にデルタ)は、線分樹に現れる状態と重ね合わせてはいけません(本題の0のように).線分樹は直接修正しますか?それとも加減しますか?
コンベヤー?ドア
問題を解く
チェーンは練習問題を切り開いて、構想はとてもとてもとても良いです.最初は小さなバグが出ました.自分でデータ構造を書いた時の成功率を疑っています.
コード
#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のように).線分樹は直接修正しますか?それとも加減しますか?