裸的树链剖分。
总结题目，实际上就是要求我们做两个操作：
安装：将 x 到根节点路径上的未安装的点安装，即将 x 到根节点这一段区间全部改为1(即线段树的区间修改)。-
卸载：将 x 以及 x 的子树的所有已安装的节点卸载，即将 x 的子树 (包括 x 在内) 的所有节点改为0(即线段树的区间修改)。
你没看错，这题的线段树没有询问，只有修改！
如果是算改变了多少状态，该怎么办呢？
我们发现，线段树的一号节点 (即根节点) 是维护的整棵树的值。
那么令线段树的每一个节点权值为这个节点代表的区间的和。
因为安装数量==线段树根节点的权值。所以我们可以在修改前用 sum1 记录当前安装状态。修改后再用 sum2 记录当前安装状态。这次改变的总数即为 abs(sum1-sum2)。
子树的修改怎么办呢？
我们来观察一下，按照样例，可以发现：
每一个节点后面都紧跟着它的子节点!
也就是说，节点 x 与它的所有子节点是一段连续的区间! 这段连续的区间就是 seg(x)~seg(x)+size(x)-1！
所以就很简单了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf("A")
#define C printf(" ")
using namespace std;
const int N=1e5+2;
template <typename Tp> inline void IN(Tp &x){
int f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;
}
struct Node{
int fa,dep,size,son,top,seg;
#define fa(x) tree[x].fa
#define d(x) tree[x].dep
#define s(x) tree[x].size
#define son(x) tree[x].son
#define top(x) tree[x].top
#define seg(x) tree[x].seg
}tree[N];
struct Edge{
int nxt,to;
#define nxt(x) edge[x].nxt
#define to(x) edge[x].to
}edge[N<<2];
struct Tree{
int val,lazy;
#define v(x) segtree[x].val
#define lazy(x) segtree[x].lazy
}segtree[N<<2];
int num[N<<2],rev[N<<2],head[N<<2],n,m,cnt;
inline void pushup(int x){v(x)=v(x<<1)+v(x<<1|1);}
inline void pushdown(int k,int l,int r){
int mid=(l+r)>>1;
v(k<<1)=lazy(k)*(mid-l+1);v(k<<1|1)=lazy(k)*(r-mid);
lazy(k<<1)=lazy(k<<1|1)=lazy(k);lazy(k)=-1;return;
}
inline void build(int k,int l,int r){
int mid=(l+r)>>1;v(k)=0;lazy(k)=-1;
if(l==r)return;else build(k<<1,l,mid),build(k<<1|1,mid+1,r);
}
inline void update(int k,int l,int r,int L,int R,int val){
int mid=(l+r)>>1;if(r<L||R<l)return;
if(L<=l&&r<=R){v(k)=val*(r-l+1);lazy(k)=val;return;}
if(lazy(k)!=-1)pushdown(k,l,r);
update(k<<1,l,mid,L,R,val);update(k<<1|1,mid+1,r,L,R,val);pushup(k);
}
inline void change(int x,int y,int val){
while(top(x)!=top(y)){
if(d(x)<d(y))swap(x,y);
update(1,1,seg(0),seg(top(x)),seg(x),val);x=fa(top(x));
}if(d(x)>d(y))swap(x,y);update(1,1,seg(0),seg(x),seg(y),val);return;
}
inline void dfs1(int u,int f){
s(u)=1,fa(u)=f,d(u)=d(f)+1;
for(register int i=head[u];i;i=nxt(i)){
int v=to(i);if(v==f)continue;
dfs1(v,u);s(u)+=s(v);
if(s(v)>s(son(u)))son(u)=v;
}return;
}
inline void dfs2(int u,int f){
if(son(u)){
seg(son(u))=++seg(0),top(son(u))=top(u);
rev[seg(0)]=son(u),dfs2(son(u),u);
}for(register int i=head[u];i;i=nxt(i)){
int v=to(i);if(!top(v)&&v!=f){
seg(v)=++seg(0),top(v)=v;
rev[seg(0)]=v;dfs2(v,u);
}
}return;
}char op[12];
inline void add(int x,int y){
nxt(++cnt)=head[x],head[x]=cnt,to(cnt)=y;
nxt(++cnt)=head[y],head[y]=cnt,to(cnt)=x;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);
for(register int x,i=2;i<=n;++i)
{scanf("%d",&x);x++;add(x,i);}
scanf("%d",&m);
dfs1(1,0);seg(0)=seg(1)=top(1)=rev[1]=1;
dfs2(1,0);build(1,1,seg(0));
for(register int x,i=1;i<=m;++i){
scanf("%s%d",op,&x);++x;
int sum1=v(1),sum2;
if(op[0]=='i'){
change(1,x,1);sum2=v(1);printf("%d\n",abs(sum1-sum2));
}else if(op[0]=='u'){
update(1,1,seg(0),seg(x),seg(x)+s(x)-1,0);
sum2=v(1);printf("%d\n",abs(sum1-sum2));
}
}return 0;
}
0 条评论