注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[乱搞题]GTY的人类基因组计划2  

2014-05-15 11:34:37|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

@BZOJ3758GTY的人类基因组计划2

zky神犇出的题

线段树维护区间

然后用longlong xor来判重

其实是骗分的做法。。。

因为不能保证唯一性。。。

选好随机数种子多试几次就A了

还有一种很神的做法,详见zky的blog

bzoj上不能用time(0)...

我re了无数次QAQ

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
int scan() {
    char cc=' ';
    int re=0,fh=1;
    while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
    if(cc=='+') {cc=getchar();fh=1;}
    if(cc=='-') {cc=getchar(); fh=-1;}
    while('0'<=cc&&cc<='9') {
        re=re*10+cc-'0';
        cc=getchar();
    }
    return re*fh;
}
const int N = 100000+100;
const int H = 1000000+7;
int n,m,q,ak,Tn;
int lson[N*2],rson[N*2],flag[N*2],tree[N*2],ntree[N*2];
long long room[N],seed[N];
int pnow[N],ROOT;
struct HASH {
    struct Node {
        long long d;
        Node *next;
        Node() {
            next=NULL;
        }
    }d[H];
    void push(long long a) {
        int x=(a%H+H)%H;
        Node *l=new Node;
        l->next=d[x].next;
        l->d=a;
        d[x].next=l;
    }
    bool find(long long a) {
        int x=(a%H+H)%H;
        Node *l=d[x].next;
        for(; l!=NULL; l=l->next)
            if(l->d==a) return 1;
        return 0;
    }
} hash;
int Build(int l,int r) {
    int ro=++Tn;
    if(l<r) {
        int mid=(l+r)/2;
        lson[ro]=Build(l,mid);
        rson[ro]=Build(mid+1,r);
        tree[ro]=tree[lson[ro]]+tree[rson[ro]];
    } else if(l==r) {
        tree[ro]=0;
        if(l==1) {
            for(int i=1; i<=n; i++) {
                pnow[i]=1;
                room[1]^=seed[i];
            }
            tree[ro]=n;
        }
    }
    return ro;
}
void pushdown(int ro,int l,int r) {
    if(flag[ro]) {
        if(lson[ro]) {
            flag[lson[ro]]=1;
            ntree[lson[ro]]=tree[lson[ro]];
            flag[rson[ro]]=1;
            ntree[rson[ro]]=tree[rson[ro]];
        } else {
            if(!hash.find(room[l]))
                hash.push(room[l]);
        }
        flag[ro]=0;
    }
}
void insert(int ro,int l,int r,int d,int x,int val) {
    int mid=(l+r)/2;
    pushdown(ro,l,r);
    if(l==r) {
        room[l]^=seed[d];
        tree[ro]+=val;
        if(hash.find(room[l])) ntree[ro]=tree[ro];
        else ntree[ro]=0;
        return;
    }
    if(x<=mid) insert(lson[ro],l,mid,d,x,val);
    else insert(rson[ro],mid+1,r,d,x,val);
    tree[ro]=tree[lson[ro]]+tree[rson[ro]];
    ntree[ro]=ntree[lson[ro]]+ntree[rson[ro]];
}
int ask(int ro,int l,int r,int la,int ra) {
    int mid=(l+r)/2,re=0;
    pushdown(ro,l,r);
    if(la<=l&&r<=ra) {
        re=tree[ro]-ntree[ro];
        flag[ro]=1;
        ntree[ro]=tree[ro];
        return re;
    }
    if(la<=mid) re+=ask(lson[ro],l,mid,la,ra);
    if(mid+1<=ra) re+=ask(rson[ro],mid+1,r,la,ra);
    tree[ro] =tree[lson[ro]]+tree[rson[ro]];
    ntree[ro]=ntree[lson[ro]]+ntree[rson[ro]];
    return re;
}
int main() {
    //freopen("input.txt","r",stdin);
    //printf("%f",(double)sizeof(hash)/1024/1024);
    int a,b,i,j,sqn;
    char cc;
    srand(10010);
    //getseed
    n=scan();
    m=scan();
    q=scan();
    for(i=1; i<=n; i++)
        seed[i]=rand()*10000+rand()+rand()*32767;
    ROOT=Build(1,m);
    for(i=1; i<=q; i++) {
        do {
            cc=getchar();
        }
        while(cc==' '||cc=='\r'||cc=='\n');
        if(cc=='C') {
            a=scan();
            b=scan();
            if(pnow[a])
                insert(ROOT,1,m,a,pnow[a],-1);
            insert(ROOT,1,m,a,b,1);
            pnow[a]=b;
        } else {
            a=scan();
            b=scan();
            a=ask(ROOT,1,m,a,b);
            printf("%d\n",a);
        }
    }
    return 0;
}


  评论这张
 
阅读(66)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017