裸的树链剖分
总结题目,实际上就是要求我们做两个操作:
  • 安装:将 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;
}
我居然因为 L 和 r 写反了而调了一个多小时…..
分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注