hdu 3333 turing tree 成段不重复求和

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <map>
 6 
 7 using namespace std;
 8 
 9 #define MAXN 30010
10 
11 __int64 sum[MAXN];
12 int a[MAXN];
13 map<int,int> hash;
14 
15 struct node
16 {
17     int id,l,r;
18 }tree[100010];
19 
20 int lowbit(int x)
21 {
22     return x&(-x);
23 }
24 
25 void update(int x,int val)
26 {
27     while(x <= MAXN)
28     {
29         sum[x] += val;
30         x += lowbit(x);
31     }
32 }
33 
34 __int64 query(int x)
35 {
36     __int64 s=0;
37     while(x>0)
38     {
39         s += sum[x];
40         x -= lowbit(x);
41     }
42     return s;
43 }
44 
45 bool cmp(node a,node b)
46 {
47     return a.r<b.r;
48 }
49 
50 __int64 ans[100010];
51 int main()
52 {
53     int t,n,q;
54     scanf("%d",&t);
55     while(t--)
56     {
57         memset(sum,0,sizeof(sum));
58         memset(a,0,sizeof(a));
59         scanf("%d",&n);
60         for(int i=1;i<=n;i++)
61             scanf("%d",&a[i]);
62         scanf("%d",&q);
63         for(int i=1;i<=q;i++)
64         {
65             scanf("%d%d",&tree[i].l,&tree[i].r);
66             tree[i].id=i;
67         }
68         hash.clear();
69         sort(tree+1,tree+q+1,cmp);
70         int pt=1;
71         for(int i=1;i<=q;i++)
72         {
73             while(pt<=tree[i].r)
74             {
75                 if(hash[a[pt]] != 0)//说明a[pt]在前面已经出现过了。
76                 {
77                     update(hash[a[pt]],-a[pt]);//删除前面出现的a[pt]
78                 }
79                 update(pt,a[pt]);
80                 hash[a[pt]]=pt;
81                 pt++;
82             }
83             ans[tree[i].id]=query(tree[i].r)-query(tree[i].l-1);
84         }
85         for(int i=1;i<=q;i++)
86             printf("%I64d\n",ans[i]);
87     }
88     return 0;
89 }

用map将当前的值映射到一个下标，如果以前已经映射过了，则在树状数组中取消在上一次的位置的记录

再在当前位置加入当前值。