2 6 1 2 3 4 3 5 3 1 2 3 5 2 6 6 1 1 1 2 3 5 3 1 1 2 4 3 5
3 7 14 1 3 6
题意:给你一串数字,让你求区间[l,r]内的和,要求重复数字只求一次。
树状数组做法:大家肯定会想到离线,但是离线后排序如何排,这里有一个思路:
由于要去重,我们考虑将询问按右区间从小到大排序,对于询问,我们逐个去掉前面
重复的值,只保留当前的。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<iostream> #include<queue> #include<cmath> #include<map> #include<stack> #include<bitset> using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; const int maxn=50000+100; const int maxm=200000+100; LL c[maxn], ans[maxm]; int pre[maxn],hash[1000000+10]; struct node{ int l,r; int id; }q[maxm]; int num[maxn]; int t,n,m; int lowbit(int x) { return x&(-x); } void update(int x,LL w) { while(x<maxn) { c[x]+=w; x+=lowbit(x); } } LL query(int x) { LL s=0; while(x>0) { s+=c[x]; x-=lowbit(x); } return s; } int cmp(node l1,node l2) { return l1.r<l2.r; } int main() { int x,y; scanf("%d",&t); while(t--) { CLEAR(hash,-1); CLEAR(c,0); scanf("%d",&n); REPF(i,1,n) { scanf("%I64d",&num[i]); pre[i]=hash[num[i]]; hash[num[i]]=i; update(i,num[i]); } scanf("%d",&m); REP(i,m) { scanf("%d%d",&x,&y); q[i].l=x;q[i].r=y; q[i].id=i; } sort(q,q+m,cmp); int rr=0; REP(i,m) { for(int j=rr+1;j<=q[i].r;j++) { if(pre[j]!=-1)//卧槽,只保留当前位置的num[j],精髓啊 update(pre[j],-num[j]); } rr=q[i].r; ans[q[i].id]=query(q[i].r)-query(q[i].l-1); } REP(i,m) printf("%I64d\n",ans[i]); } return 0; }
原文:http://blog.csdn.net/u013582254/article/details/42226529