CF707D Persistent Bookcase 可持久化线段树

维护一个二维零一矩阵（n,m<=1000），支持四种操作（不超过10^5次）:

将(i,j)置一
将(i,j)置零
将第i行零一反转yu
回到第K次操作前的状态
每次操作后输出全局一共有多少个一

你发现如果每一次操作都复制一整行的话是可以用 $bitset$ 优化的，自带/32

所以，我们对于每一个时刻维护一个线段树，其中 $i$ 节点表示第 $i$ 行对应的 $bitset$ 编号.

对于前 $3$ 个操作，每一次操作时都暴力新建一个 bitset，然后每次在可持久化线段树上最多更新一个单点.

顺便在线段树的节点上再维护一个 $1$ 的数量即可.

#include <bits/stdc++.h>

#define M 1004

#define N 100005

#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)

using namespace std;

bitset<M>v[N],uni,oo;

int rt[N];

namespace seg

{

    #define lson t[x].ls

    #define rson t[x].rs

    int tot;

    int newnode() { return ++ tot; }

    struct Node

    {

        int ls,rs,id,sum;

    }t[N*40];

    int update(int x,int l,int r,int p,int v)

    {

        int now=newnode();

        t[now]=t[x];

        if(l==r)

        {

            t[now].id=v;

            return now;

        }

        int mid=(l+r)>>1;

        if(p<=mid)

        {

            t[now].ls=update(lson,l,mid,p,v);

        }

        else

        {

            t[now].rs=update(rson,mid+1,r,p,v);

        }

        t[now].sum=t[t[now].ls].sum+t[t[now].rs].sum;

        return now;

    }

    int modify(int x,int l,int r,int p,int v)

    {

        int now=newnode();

        t[now]=t[x];

        if(l==r)

        {

            t[now].sum=v;

            return now;

        }

        int mid=(l+r)>>1;

        if(p<=mid) t[now].ls=modify(lson,l,mid,p,v);

        else t[now].rs=modify(rson,mid+1,r,p,v);

        t[now].sum=t[t[now].ls].sum+t[t[now].rs].sum;

        return now;

    }

    int query(int x,int l,int r,int p)

    {

        if(!x) return 0;

        if(l==r)  return t[x].id;

        int mid=(l+r)>>1;

        if(p<=mid) return query(lson,l,mid,p);

        else return query(rson,mid+1,r,p);

    }

    void dfs(int x,int l,int r)

    {

        if(!x) return;

        if(l==r) printf("%d %d\n",l,t[x].sum);

        int mid=(l+r)>>1;

        dfs(lson,l,mid), dfs(rson,mid+1,r);

    }

    #undef lson

    #undef rson

};

int main()

{

    // setIO("now");

    int n,m,q,i,j;

    scanf("%d%d%d",&n,&m,&q);

    for(i=1;i<=m;++i) uni[i]=1;

    for(i=1;i<=q;++i)

    {

        int op,a,b,c;

        scanf("%d",&op);

        rt[i]=rt[i-1];

        if(op==1)

        {

            scanf("%d%d",&a,&b);

            int pre=seg::query(rt[i-1],1,n,a);

            v[i]=v[pre];

            v[i][b]=1;

            rt[i]=seg::update(rt[i-1],1,n,a,i);

            oo=v[i]&uni;

            rt[i]=seg::modify(rt[i],1,n,a,oo.count());

        }

        if(op==2)

        {

            scanf("%d%d",&a,&b);

            int pre=seg::query(rt[i-1],1,n,a);

            v[i]=v[pre];

            v[i][b]=0;

            rt[i]=seg::update(rt[i-1],1,n,a,i);

            oo=v[i]&uni;

            rt[i]=seg::modify(rt[i],1,n,a,oo.count());

        }

        if(op==3)

        {

            int x;

            scanf("%d",&x);

            int pre=seg::query(rt[i-1],1,n,x);

            v[i]=v[pre]^uni;

            rt[i]=seg::update(rt[i-1],1,n,x,i);

            oo=v[i]&uni;

            rt[i]=seg::modify(rt[i],1,n,x,oo.count());

        }

        if(op==4)

        {

            int x;

            scanf("%d",&x);

            rt[i]=rt[x];

        }

        printf("%d\n",seg::t[rt[i]].sum);

    }

    return 0;

}

巴特西

CF707D Persistent Bookcase 可持久化线段树

最新文章

热门文章