526互联

Codeforces Round 368 (Div. 2) D. Persistent Bookcase 主席树维护bitset

发布时间 2023-03-22 21:13:42作者: liyishui

在学主席树时找到了这道题

本来yyyy了一个二维的主席树这种东西，然后发现很多信息好像维护不了

观察到n和m都很小，考虑把一整行看成一个节点，开一个bitset

然后区间取反、单点修改，就都可以直接做啦。

最开始不敢直接这么做，总觉得在结构体里再封装一个bitset太大

但其实还好，时间复杂度1000/w=15.625，这题还能接受

学了一种新的写法，之前的update总是用void 搭配 &传参

这题还需要类似push_up地合并子区间信息，用return 当前节点编号的写法会清晰很多。

 
 
有个笨蛋没算好空间，开太小wa，开不够re，开太大me，中间不小心ce
是谁我不说:D
J就是说正常是节点数的32倍，但这题大概能开多大开多大。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
const int N=maxn*maxn*2;
int History=0,n,m,q;
struct tree{
    int ls,rs,sum;
    bitset<maxn>f;
}t[N];
int rt[N],tot;
int op_123(int p,int shelf,int pos,int op,int l=1,int r=n){
    int q=++tot;
    t[q]=t[p];// 其实不会cost太多时间，1000/w 
    //cout<<p<<" "<<shelf<<" "<<pos<<" "<<l<<" "<<r<<endl;
    if(l==r){ 
        if(pos!=-1 ) {
            if(op==1) t[q].f[pos]=1;
            else t[q].f[pos]=0;
        }
        else {for(int j=1;j<=m;j++) t[q].f.flip(j);}
        t[q].sum=t[q].f.count();
        return q;// 这种写法扩展性好像更强一点，起码清楚、支持合并子信息 
    }
    int mid=l+r>>1;
    if(shelf<=mid) t[q].ls=op_123(t[p].ls,shelf,pos,op,l,mid);
    else t[q].rs=op_123(t[p].rs,shelf,pos,op,mid+1,r);
    t[q].sum=t[t[q].ls].sum+t[t[q].rs].sum;
    return q;
}
int main(){
    //freopen("lys.in","r",stdin);
    cin>>n>>m>>q;
    for(int i=1;i<=q;i++){
        int op;cin>>op;
        //cout<<":: "<<op<<endl;
        if(op==1){
            int x,y;cin>>x>>y;
            //cout<<x<<" "<<y<<endl;
            rt[i]=op_123(rt[i-1],x,y,1);
        }
        if(op==2){
            int x,y;cin>>x>>y;
            rt[i]=op_123(rt[i-1],x,y,2);
        }
        if(op==3){
            int x;cin>>x;
            //op_3(int& p,int shelf,int k,int l=1,int r=n){
            rt[i]=op_123(rt[i-1],x,-1,3);
        }
        if(op==4){
            int k;cin>>k;
            rt[i]=rt[k];
        }
        cout<<t[rt[i]].sum<<endl;
    }
}