首页 > 代码库 > BZOJ3578 GTY的人类基因组计划2 HASH

BZOJ3578 GTY的人类基因组计划2 HASH

2024-09-06 10:21:11   216人阅读

题意：有N个人M个房间，初始时所有人都在1号房间，维护：1、让某个人去某个房间  2、假如[l,r]中所有的人还未一起统计过，Ans+=人数。输出Ans

题解：

集合HASH get

根据异或的性质，a^x^x=a，因此一个集合的HASH值就是其所有元素的异或起来的值

接下来就是STL大法好

将每个房间看成一个集合，每个人赋一个初始rand，set存储当前所有HASH值没有出现过的房间。对于每个询问，二分出所有区间之间的房间，统计答案即可。

技术分享
#include <set>#include <map>#include <cstdio>#include <cstring>#include <cstdlib>#include <climits>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXN=100000+2;int N,M,Q,b[MAXN],c[MAXN];ll h[MAXN],a[MAXN];char S[4+2];set<int> s;set<int>::iterator it;map<ll,bool> m;int main(){    srand(1999+9+7);    scanf("%d %d %d",&N,&M,&Q);    for(int i=1;i<=N;i++){        a[i]=(ll)rand()<<16,b[i]=1;        h[1]^=a[i],c[1]++;    }    s.insert(1);    for(int i=1,x,y;i<=Q;i++){        scanf("%s",S);        if(S[0]==‘C‘){            scanf("%d %d",&x,&y);            s.erase(b[x]),s.erase(y);            h[b[x]]^=a[x],c[b[x]]--;            if(!m[h[b[x]]]) s.insert(b[x]);            h[y]^=a[x],c[y]++;            if(!m[h[y]]) s.insert(y);            b[x]=y;        }        if(S[0]==‘W‘){            scanf("%d %d",&x,&y);            int ans=0;            for(it=s.lower_bound(x);it!=s.end() && *it<=y;it=s.lower_bound(x))                m[h[*it]]=1,ans+=c[*it],s.erase(it);            printf("%d\n",ans);        }    }    return 0;}
View Code

 

BZOJ3578 GTY的人类基因组计划2 HASH


联系
我们