Bakser's Blog

我是逗比。

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

| Comments

出题人ZKY的题解

GTY的基因其实是有一个奇特的梗的。

丧病的ZKY大爷决定要出树套树,然后就丧病的出了这道题。
然后一开始标程是傻逼的map套set,zky公布题解后纷纷表示绝逼要T成翔。
std大爷zky表示不服。
然后出了一组极限数据标程T成翔,所以大家明白数据如何弱了吧。
于是就有了这玩意
然后有一位神犇wwx用奇特的时间空间和码长虐掉了这道题。
然后就有了现在这种做法:

开一个set记录可以获得收益的位置集合,修改只有q个,所以这个集合里也最多有q个位置,所以每次修改就判断修改涉及的两个位置能否取得收益(hash+map,hash方式也很奇特),然后每次做实验就查找set中l到r中的元素累加起来,并把这些元素都扔进map里判重。
orz wwx!

OrzGTY!!!
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<cstdlib>
using namespace std;
typedef unsigned long long LL;
#define N 100100
set<int> s;
typedef set<int>::iterator iter;
map<LL,bool> hash;
struct hh
{
    int sum;
    LL sta;
}room[N];
int n,m,q,pos[N];
LL seed[N];
inline void get_seed()
{
    srand(112);
    for(int i(1);i<=n;i++)
        seed[i]=(rand()*13131+23131*rand()+756753)*10007;
}
inline void change(int x,int _pos)
{
    room[pos[x]].sta^=seed[x];
    room[pos[x]].sum--;
    if(!hash.count(room[pos[x]].sta))s.insert(pos[x]);
    else s.erase(pos[x]);
    room[pos[x]=_pos].sta^=seed[x];
    room[_pos].sum++;
    if(!hash.count(room[_pos].sta))s.insert(_pos);
    else s.erase(_pos);
}
inline int query(int l,int r)
{
    int res(0);
    for(iter i(s.lower_bound(l));i!=s.end()&&(*i<=r);i=s.lower_bound(l))
    {
        res+=room[*i].sum;
        hash[room[*i].sta]=1;
        s.erase(i);
    }
    return res;
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    get_seed();
    for(int i(1);i<=n;i++)
        room[1].sta^=seed[i],pos[i]=1;
    room[1].sum=n;
    s.insert(1);
    while(q--)
    {
        char c;int x,y;
        scanf(" %c%d%d",&c,&x,&y);
        if(c=='C')change(x,y);
        else printf("%d\n",query(x,y));
    }
    return 0;
}

Comments

comments powered by Disqus