首页 > 代码库 > hdu3333(线段树)

hdu3333(线段树)

区间更新,单点查询。

 

hdu3333

 

#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>#include <map>#include <vector>#include <string>#include <stdlib.h>#include <queue>using namespace std;#define N 30300#define SN 300300struct node{    int x,y;    int key;    int id;}line[N*10];map<int,int>cao;__int64 sum[N];__int64 ans[100100];int l[SN],r[SN];__int64 num[SN];int cmp(node t,node t1){    if(t.y==t1.y)    {        if(t.x==t1.x)    return t.key>t1.key;        return t.x>t1.x;    }    return t.y<t1.y;}void build(int tl,int tr,int s){    l[s]=tl; r[s]=tr; num[s]=0;    if(tl==tr) return ;    int mid=(tl+tr)/2;    build(tl,mid,2*s);    build(mid+1,tr,2*s+1);}void update(int tl,int tr,int x,int s){    if(l[s]==tl&&tr==r[s])    {        num[s]+=x;        return;    }    int mid=(l[s]+r[s])/2;    if(tr<=mid) update(tl,tr,x,2*s);    else if(tl>mid) update(tl,tr,x,2*s+1);    else    {        update(tl,mid,x,2*s);        update(mid+1,tr,x,2*s+1);    }}__int64 query(int x,int s){    if(l[s]==r[s])    {        return num[s];    }    num[2*s]+=num[s];    num[2*s+1]+=num[s];    num[s]=0;    int mid=(l[s]+r[s])/2;    if(x<=mid) return query(x,2*s);    else query(x,2*s+1);}int main(){    int T;    scanf("%d",&T);    while(T--)    {        cao.clear();        memset(sum,0,sizeof(sum));        int cnt=0;        int n;        scanf("%d",&n);        for(int i=1;i<=n;i++)        {            int tmp;            scanf("%d",&tmp);            sum[i]=sum[i-1]+tmp;            if(cao[tmp]==0)            {                cao[tmp]=i;            }            else            {                line[cnt].x=cao[tmp];                line[cnt].y=i;                line[cnt].key=tmp;                cao[tmp]=i;                cnt++;            }        }        int m;        scanf("%d",&m);        for(int i=0;i<m;i++)        {            int x,y;            scanf("%d%d",&x,&y);            line[cnt].id=i;            line[cnt].x=x;            line[cnt].y=y;            line[cnt].key=-1;            cnt++;        }        sort(line,line+cnt,cmp);        build(1,n,1);        for(int i=0;i<cnt;i++)        {            if(line[i].key==-1)            {                __int64 tmp=query(line[i].x,1);                ans[line[i].id]=sum[line[i].y]-sum[line[i].x-1]-tmp;            }            else            {                update(1,line[i].x,line[i].key,1);            }        }        for(int i=0;i<m;i++)            printf("%I64d\n",ans[i]);    }    return 0;}

 

hdu3333(线段树)