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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2009[HH的项链]  

2010-07-26 18:20:17|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

树状数组。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

山东2009年省选 HH的项链

*/

#include <stdio.h>

#include <string.h>

 

const int MAXN=50000+2;

const int MAXM=200000+2;

const int MAXKIND=1000000+2;

typedef struct struct_query* query;

struct struct_query{int R,i;query n;};

typedef struct struct_kind* kind;

struct struct_kind{int p;kind n;};

struct_query pool[MAXM];

query top=pool;

struct_kind kind_pool[MAXKIND];

kind kind_top=kind_pool;

int N,M,L,R;

int necklace[MAXN];

query Q[MAXN];

kind k[MAXKIND];

int st[MAXN];

int answer[MAXM];

void add_query(int L,int R,int i)

{

     top->R=R,top->i=i,top->n=Q[L],Q[L]=top++;

}

void add_kind(int x,int p)

{

     kind_top->p=p,kind_top->n=k[x],k[x]=kind_top++;

}

void inc(int x,int value)

{

     for (;x<=N;x+=(x)&(-x)) st[x]+=value;

}

void sum(int x,int& value)

{

     for (;x;x-=(x)&(-x)) value+=st[x];

}

int main()

{

    scanf("%d",&N);

    for (int i=1;i<=N;i++) scanf("%d",necklace+i);

    scanf("%d",&M);

    for (int i=0;i<M;i++)

        scanf("%d%d",&L,&R),add_query(L,R,i);

    for (int i=N;i>=1;i--)

        add_kind(necklace[i],i);

    for (int i=0;i<MAXKIND;i++)

        if (k[i]) inc(k[i]->p,1);

    for (int L=1;L<=N;L++)

    {

        for (query q=Q[L];q;q=q->n)

            sum(q->R,answer[q->i]);

        inc(k[necklace[L]]->p,-1);

        if (k[necklace[L]]=k[necklace[L]]->n) inc(k[necklace[L]]->p,1);

    }

    for (int i=0;i<M;i++) printf("%d\n",answer[i]);

}

 

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

历史上的今天

评论

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

页脚

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