區間更新，單點查詢。

?

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 300300 struct 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; }

?

轉載于:https://www.cnblogs.com/chenhuan001/p/4080121.html

總結

以上是生活随笔為你收集整理的hdu3333(线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。