考虑用两个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;
}
评论 (0)
