9
25
2016
0

[BZOJ3578] GTY的人类基因组计划2

考虑用两个set来维护Hash值

一个维护当前有哪些房间里面有人

一个维护哪些Hash值已经被查询过了

然后直接按照操作要求一步步做就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,q,a[N],tx[N],siz[N];
long long Mp[N],Room[N];
set<long long> Hash;
set<int> St;
 
template<typename T>inline int Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
 
void Read_Char(char &x){
while((x=getchar())<'A' || x>'Z');
}
 
inline int Rand_int(){return (rand()<<15)|rand();}
inline long long Rand_ll(){return ((1ll*Rand_int())<<31ll)+Rand_int();}
 
inline void Change(const int &l,const int &r){
Room[tx[l]]^=Mp[l];
siz[tx[l]]--;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
tx[l]=r;
Room[tx[l]]^=Mp[l];
siz[tx[l]]++;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
}
 
inline int Query(const int &l,const int &r){
int ans=0;
static set<int>::iterator I;
while(1){
    I=St.lower_bound(l);
    if(I==St.end() || *I>r)break;
    ans+=siz[*I];
    Hash.insert(Room[*I]);
    St.erase(I);
}
return ans;
}

int main(){
freopen("3578.in","r",stdin);
freopen("3578.out","w",stdout);
Read(n);Read(m);Read(q);siz[1]=n;
for(register int i=1;i<=n;i++){
    Mp[i]=Rand_ll();
    Room[1]^=Mp[i];
    tx[i]=1;
}
St.insert(1);
while(q--){
    static int l,r;
    static char chs;
    Read_Char(chs);Read(l);Read(r);
    if(chs=='C')Change(l,r);
    else printf("%d\n",Query(l,r));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 992

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com