BZOJ3578 GTY的人类基因组计划2

2014.12.22 12:37 Mon| 2 visits oi_2015| 2015_刷题日常| Text

Solution

善用STL。额,善用STL……

膜拜ZKY大神出题人。

传送门

事实上,完全不需要用map,只需要 set< set<int> >

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define lson pos<<1
#define rson pos<<1|1

set<int> s[N<<2];
set< set<int> > p;
int n,m,q,belong[N],sum[N<<2],lazy[N<<2];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void pushdown(int pos,int l,int r)
{
    int mid=(l+r)>>1;
    if(l==mid) p.insert(s[lson]);
    if(mid+1==r) p.insert(s[rson]);
    sum[lson]=sum[rson]=0;
    lazy[lson]=lazy[rson]=1;
    lazy[pos]=0;
}

void modify(int pos,int l,int r,int x,int y,int type)
{
    if(l==r)
    {
        if(type) s[pos].insert(y);
        else s[pos].erase(y);
        if(p.find(s[pos])==p.end()) sum[pos]=s[pos].size();
        else sum[pos]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(lazy[pos]) pushdown(pos,l,r);
    if(x<=mid) modify(lson,l,mid,x,y,type);
    else modify(rson,mid+1,r,x,y,type);
    sum[pos]=sum[lson]+sum[rson];
}

int query(int pos,int l,int r,int x,int y)
{
    if(x<=l&&y>=r)
    {
        int re=sum[pos];
        sum[pos]=0; lazy[pos]=1;
        if(l==r) p.insert(s[pos]);
        return re;
    }
    int mid=(l+r)>>1;
    if(lazy[pos]) pushdown(pos,l,r);
    int re=0;
    if(x<=mid) re+=query(lson,l,mid,x,y);
    if(y>mid) re+=query(rson,mid+1,r,x,y);
    sum[pos]=sum[lson]+sum[rson];
    return re;
}

int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) modify(1,1,n,belong[i]=1,i,1);
    char opt[3]; int x,y;
    while(q--)
    {
        scanf("%s",opt);
        x=read(); y=read();
        switch(opt[0])
        {
            case 'C':
                modify(1,1,n,belong[x],x,0); modify(1,1,n,belong[x]=y,x,1);
            break;
            case 'W':
                printf("%d\n",query(1,1,n,x,y));
            break;
        }
    }
}