HDU3874Necklace（树状数组+离线操作）

此题的大意思说有一串珠子，每个珠子都有自己的欣赏值value，现在给你一串珠子每个的欣赏值，并给出一些询问，查询某个区间内部总欣赏值是多少，但是有一个约定就是如果这个区间内部有两个珠子的欣赏值是一样的，那么他们就视为一个。

其实也就是求某个区间内部不同的数的和。

这里学到了一个比较好的方法，那就是离线操作。根据我的理解，离线操作就是为了解决在询问中所遇到的矛盾的，它在本题上的实现就是先将查询排序，比如按照每个查询的右端点的升序排序，这样的话每次查询一个区间的时候，我们就把它的右端点到上一个查询的右端点之间且在之前已经出现过了相同价值的点删除掉，这样的话就可以保证对后面的查询不会有影响。

具体实现就是用一个last[]数组保存每一个value值最初出现的位置，再用一个Right保存上次扫描的区间的右端点（初始化为1，下图中的R表示），每次查询一个区间的和时，先按照Right到这个区间右端点扫描一遍，如果当中有一个value值上次出现的位置不在它自己的位置时，如下图第2个1之前出现的位置L[1]=1，那么我们就把第一个1从树状数组里面去掉，然后同时更新L[1]为当前位置L[1]=2.这样一来当前的1之前就可以保证没有重复的1。而且下次找到另外一个1时，也只会删除位置为2的1.

同时我们还要更新Right值为当前区间的右端点（因为之前区间已经没有重复的了）

同时，由于是按照右端点的升序排列，所以可能会用到之前的1或者不用，用的话同样保证了只有1个1，所以这样排序是对的

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define mem(a) memset(a,0,sizeof(a))
 5 #define MAX(a , b) ((a) > (b) ? (a) : (b))
 6 using namespace std;
 7 
 8 struct QUERY
 9 {
10     int a,b;
11     int index;
12 }query[200005];
13 __int64 c[50005],  ans[200005];
14 int last[1000005], value[50005], N, M, T;
15 
16 int cmp(QUERY x, QUERY y)
17 {
18     return x.b < y.b;
19 }
20 
21 int lowbit(int x)
22 {
23     return x & (-x);
24 }
25 
26 __int64 getSum(int k)
27 {
28     __int64 sum = 0;
29     while(k>=1)
30     {
31         sum += c[k];
32         k -= lowbit(k);
33     }
34     return sum;
35 }
36 
37 void edit(int k, int val)
38 {
39     while(k<=N)
40     {
41         c[k] += val;
42         k += lowbit(k);
43     }
44 }
45 
46 int main()
47 {
48     while(~scanf("%d", &T))while(T--)
49     {
50         mem(query);  mem(c);
51         mem(last);   mem(ans);
52         mem(value);
53         scanf("%d", &N);
54         for(int i=1;i<=N;i++)
55         {
56             scanf("%d", &value[i]);
57             edit(i, value[i]);
58             if(!last[value[i]]) last[value[i]] = i;
59         }
60         scanf("%d", &M);
61         for(int i=1;i<=M;i++)
62         {
63             scanf("%d%d", &query[i].a, &query[i].b);
64             query[i].index = i;
65         }
66         sort(query+1, query+M+1, cmp);
67         int lastRight = 1;
68         for(int i = 1; i <= M; i ++)
69         {
70             for(int j = lastRight; j <= query[i].b; j ++)
71             {
72                 if(last[value[j]] != j)
73                 {
74                     edit(last[value[j]], -value[j]);
75                     last[value[j]] = j;
76                 }
77             }
78             lastRight = query[i].b;
79             ans[query[i].index] = getSum(query[i].b) - getSum(query[i].a-1);
80         }
81         for(int i=1;i<=M;i++)
82         {
83             printf("%I64d
", ans[i]);
84         }
85     }
86     return 0;
87 }