bzoj 3578: GTY的人类基因组计划2

.

题意：m个房间n个人，每次可以把一个人移到某个房间，或者问l~r房间的价值和。一个房间的价值定义为这个房间里的人数，但加入这些人的编号构成的集合已经询问过了，即在之前的某次询问中，有一个房间已经有完全一样的人，不多也不少。
题解：每个数随机一个哈希值，集合的哈希值就是每个元素的哈希值异或起来，方便插入删除，用个map维护出现过没有；然后用一个set维护当前有哪些房间是可以做出贡献的，查询就lower_bound一下就好了。感觉好像很慢，但这样确实跑的过去
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,q,h[100010],a[100010],pos[100010],sz[100010];
map<int,bool>mp;
set<int>s;

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    sz[1]=n;
    for(int i=1;i<=n;i++)
    a[1]^=(h[i]=rand()*rand());
    for(int i=1;i<=n;i++)
    pos[i]=1;
    mp[0]=1;
    s.insert(1);
    while(q--)
    {
        char ss[5];
        int x,y;
        scanf("%s%d%d",ss,&x,&y);
        if(ss[0]=='C')
        {
            sz[pos[x]]--;
            a[pos[x]]^=h[x];
            if(!mp[a[pos[x]]])
            s.insert(pos[x]);
            else
            s.erase(pos[x]);
            pos[x]=y;
            sz[pos[x]]++;
            a[pos[x]]^=h[x];
            if(!mp[a[pos[x]]])
            s.insert(pos[x]);
            else
            s.erase(pos[x]);
        }
        else
        {
            int ans=0;
            for(set<int>::iterator it=s.lower_bound(x);it!=s.end()&&*it<=y;s.erase(it++))
            {
                mp[a[*it]]=1;
                ans+=sz[*it];
            }
            printf("%d\n",ans);
        }/*
        for(auto i:s)
        printf("%d ",i);
        puts("");*/
    }
}