首页 > 代码库 > 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(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。