题解： P2087 GTY的人类基因计划2

· · 题解

P2087 GTY的人类基因组计划2

题目大意

给定 n 个人和 m 个房间，初始时所有人都在 1 号房间。有两种操作，第一种是将 i 号人从 a 号房间移动到 b 号房间，第二种是对一段区间里的人数求和，特殊地，每种人的组合只能被加一次和。

其中，n,m,q\leq 10^5。

解题思路

存在类似于区间求和的操作，考虑使用线段树。

但是存在人数的移动以及状态的变化，所以我们就需要思考该如何维护了。

给房间和每一个人随机一个哈希值，记每个房间当前的哈希值为 room_i，每个人的哈希值为 rd_i，则第 i 个房间加入第 j 个人后哈希值变为 room_i \oplus rd_j，而第 j 个人离开了 i 号房间后则哈希值为 room_i \oplus rd_j \oplus rd_j = room_i，我们发现，利用异或计算的性质，我们成功解决了人数组合的问题。

使用 map 把每一个出现过的异或哈希值塞进去，再在线段树中维护一个 tag 数组维护当前房间是否可以被加和，在维护区间和时 tag 便作为一个系数出现在 sum 的计算中。

对于人数的移动，考虑分拆为一个房间的人离开和另外一个房间的人加入，对于这两个操作分别更新一下哈希值和 tag 数组即可。

时间复杂度 O(N\log N)。

代码

//上文已描述得很详细，不过多注释
#include<bits/stdc++.h>
#include<time.h>
using namespace std;

const int N=1e5+5;

void FileIO(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

int start;
int n,m,q,rd[N],pos[N];
unordered_map<int,int> mp1,mp;

namespace SGT{
    int sum[N<<2],room[N<<2];
    int tag[N<<2];//available or not

    #define ls rt<<1
    #define rs rt<<1|1
    #define lson ls,l,md
    #define rson rs,md+1,r

    void push_up(int rt){
        sum[rt]=sum[ls]*tag[ls]+sum[rs]*tag[rs];
    }
    void push_down(int rt){
        if(tag[rt])return;
        tag[ls]=tag[rs]=0;
        sum[rt]=0,tag[rt]=1;
    }
    void build(int rt,int l,int r){
        sum[rt]=0,room[rt]=start,tag[rt]=1;
        if(l==r){
            if(l==1){
                sum[rt]=n;
                for(int i=1;i<=n;i++){
                    do{
                        rd[i]=rand()%(INT_MAX)+1;
                    }while(mp1[rd[i]]);
                    mp1[rd[i]]=1;
                    room[rt]^=rd[i];
                    pos[i]=1;
                }
            }
            return;
        }

        int md=(l+r)>>1;
        build(lson); build(rson);
        push_up(rt);
    }
    int qry(int rt,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            if(tag[rt]==0){
                return 0; // not available
            }
            if(l==r){
                mp[room[rt]]=1;
            }
            tag[rt]=0;
            return sum[rt];
        }

        push_down(rt);
        int md=(l+r)>>1,res=0;
        if(L<=md){
            res+=qry(lson,L,R);
        }
        if(R>md){
            res+=qry(rson,L,R);
        }
        push_up(rt);
        return res;
    }

    void del(int rt,int l,int r,int x,int pos){
        if(l==r){
            if(tag[rt]==0){
                mp[room[rt]]=1;
            }
            room[rt]^=rd[x];
            if(mp[room[rt]]==0){
                tag[rt]=1;
            }
            else{
                tag[rt]=0;
            }
            sum[rt]--;
            return;
        }
        push_down(rt);
        int md=(l+r)>>1;
        if(pos<=md){
            del(lson,x,pos);
        }
        else{
            del(rson,x,pos);
        }
        push_up(rt);
    }
    void insert(int rt,int l,int r,int x,int pos){
        if(l==r){
            if(tag[rt]==0){
                mp[room[rt]]=1;
            }
            room[rt]^=rd[x];
            sum[rt]++;
            if(mp[room[rt]]==0){
                tag[rt]=1;
            }
            else{
                tag[rt]=0;
            }
            return;
        }
        push_down(rt);
        int md=(l+r)>>1;
        if(pos<=md){
            insert(lson,x,pos);
        }
        else{
            insert(rson,x,pos);
        }
        push_up(rt);
    }
    void upd(int rt,int l,int r,int x,int new_pos,int &pos){
        del(rt,l,r,x,pos);
        insert(rt,l,r,x,new_pos);
        pos=new_pos;
        return;
    }
}

namespace sunburstfan{
    using namespace SGT;
    void solve(){
        cin>>n>>m>>q;

        start=rand()%(INT_MAX)+1;
        build(1,1,m);

        for(int i=1;i<=q;i++){
            char opt;
            int x,y;
            cin>>opt>>x>>y;
            if(opt=='C'){
                upd(1,1,m,x,y,pos[x]);
            }
            else{
                int res=qry(1,1,m,x,y);
                cout<<res<<"\n";
            }
        }

        return;
    }
}
using namespace sunburstfan;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    srand(time(NULL));

    int T=1;
    while(T--){
        solve();
    }

    return 0;
}