题解 P2087 【GTY的人类基因组计划2】

· · 题解

这题没有题解？？做的人太少了。。

为什么标签是平衡树和线段树。。。

自己完全是按照提示全STL水过的啊 set map就好了。

这题开始能想到一些思路，但是不懂怎么hash。。

现在知道集合hash可以用xor的啊~

先随机一个long long范围的数字，之后xor就是整个集合的hash值了。。

听说用妹子生日做srand()的种子会有神秘加成

代码：

#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib> 
#include <iostream>
#include <algorithm>
using namespace std;
#define uLL unsigned long long
#define MAXN 0x186AF
map<uLL,bool> hash;
set<int> zt;
uLL h[MAXN],an[MAXN],size[MAXN];
int at[MAXN];
char ch[8];
int main(){
    freopen("input2.txt","r",stdin);
    freopen("input2.out","w",stdout);
    srand(2001+06+28);  //这个数多少不重要啦，不小心被卡就换个就行了。。
    int n,m,q; cin>>n>>m>>q;    
    for(int i=1;i<=n;i++){
        int k1=rand()<<16|rand()%1000000000,
            k2=rand()<<16|rand()%2000000000;
        an[i]=(uLL)k1*k2; h[1]^=an[i]; at[i]=1;  //蜜汁hash
    }
    hash.clear(); zt.insert(1); size[1]=n;
    for(int i=1;i<=q;i++){
        int x,y; scanf("%s%d%d",ch,&x,&y);
        if(ch[0]=='C'){
            if(at[x]==y) continue;
            zt.erase(at[x]); zt.erase(y);
            h[at[x]]^=an[x]; size[at[x]]--;
            if(!hash[h[at[x]]]) zt.insert(at[x]);        
            at[x]=y; h[y]^=an[x]; size[y]++;             
            if(!hash[h[y]]) zt.insert(y); //直接模拟，有重复的就删
        }
        else{
            int ans=0; 
            set<int>::iterator it=zt.lower_bound(x);
            for(;it!=zt.end()&&*it<=y;it=zt.lower_bound(x)){
                ans+=size[*it]; hash[h[*it]]=1; zt.erase(it);
            } //把满足条件的i都加上 (x<=i<=y)
            printf("%d\n", ans);
        }
    }
}

其实出题人不想让我们这么水的是么