SDOI2009[HH的项链]

树状数组。

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]);

}