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

关于如何判断一个集合是否出现过:

给每个元素随机一个hash权值,然后xor起来即可

插入删除都只需xor

线段树维护区间有效人数和,以及打标记表示这个区间的集合要全部标记为出现过，并把区间内sum值都置0

写hash用了map被虐了TAT

#include<cstdio>
#include<map>
#define N 100010
#define M 200010
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int n,m,q,i,j,loc[N];
int tot,l[M],r[M],val[M],sum[M],ran,set[M],hash[N];bool tag[M];
std::map<int,bool>vis;
char ch;
int build(int a,int b){
  int x=++tot;
  if(a==b)return x;
  int mid=(a+b)>>1;
  l[x]=build(a,mid);r[x]=build(mid+1,b);
  return x;
}
inline void clean(int x,int a,int b){
  if(!x)return;
  tag[x]=1;sum[x]=0;
  if(a==b)vis[set[x]]=1;
}
inline void pb(int x,int a,int b){
  if(tag[x]){
    int mid=(a+b)>>1;
    clean(l[x],a,mid);clean(r[x],mid+1,b);
    tag[x]=0;
  }
}
inline void up(int x){sum[x]=sum[l[x]]+sum[r[x]];}
void add(int x,int a,int b,int c,int p,int w){
  if(a==b){
    set[x]^=p;
    val[x]+=w;
    sum[x]=vis[set[x]]?0:val[x];
    return;
  }
  int mid=(a+b)>>1;
  pb(x,a,b);
  if(c<=mid)add(l[x],a,mid,c,p,w);else add(r[x],mid+1,b,c,p,w);
  up(x);
}
int ask(int x,int a,int b,int c,int d){
  int t=0;
  if(c<=a&&b<=d){
    t=sum[x];
    clean(x,a,b);
    return t;
  }
  int mid=(a+b)>>1;
  pb(x,a,b);
  if(c<=mid)t+=ask(l[x],a,mid,c,d);
  if(d>mid)t+=ask(r[x],mid+1,b,c,d);
  up(x);
  return t;
}
int main(){
  read(n),read(m),read(q);
  build(1,m);
  for(i=1;i<=n;i++)ran*=233,ran+=17,add(1,1,m,loc[i]=1,hash[i]=ran,1);
  while(q--){
    while(!(((ch=getchar())=='C')||(ch=='W')));
    read(i),read(j);
    if(ch=='C')add(1,1,m,loc[i],hash[i],-1),add(1,1,m,loc[i]=j,hash[i],1);
    else printf("%d
",ask(1,1,m,i,j));
  }
  return 0;
}