HDU3333 Turing Tree(线段树 离线处理)

After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again…
Now given a sequence of N numbers A1, A2, …, AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, …, Aj.
Input
The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:
* Line 1: N (1 ≤ N ≤ 30,000).
* Line 2: N integers A1, A2, …, AN (0 ≤ Ai ≤ 1,000,000,000).
* Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
* Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).
Output
For each Query, print the sum of distinct values of the specified subsequence in one line.

参考题解
这个题目需要离线处理。然后按照区间的右值排序，接着从左到右把每一个数更新到线段树中，并记录它出现的位置。如果一个数已经出现过，那么我们就把他上次出现的位置的值置为0，并更新它出现的位置。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int max_n = 3e4+5, max_q = 1e5+5;
int number[max_n];
LL sum[max_n<<2];
struct Query
{
    int left, right;
    int id;
    LL sum;
}q[max_q];

bool cmpById(Query fir, Query sec)
{
    return fir.id < sec.id;
}

bool cmpBySeg(Query fir, Query sec)
{
    if(fir.right == sec.right)  return fir.left < sec.left;
    return fir.right < sec.right;
}

void update(int pos, int _left, int _right, int cur, int val)
{
    if(_left == _right)
    {
        sum[cur] = val;
        return ;
    }
    int mid = (_left+_right)>>1;
    if(pos <= mid)  update(pos, _left, mid, cur<<1, val);
    if(mid < pos)  update(pos, mid+1, _right, cur<<1|1, val);
    sum[cur] = sum[cur<<1]+sum[cur<<1|1];
}

LL query(int L, int R, int l, int r, int cur)
{
    if(L <= l && r <= R)    return sum[cur];
    int mid = (l+r)>>1;
    LL result = 0;
    if(L <= mid)    result += query(L, R, l, mid, cur<<1);
    if(mid < R)    result += query(L, R, mid+1, r, cur<<1|1);
    return result;
}

int main()
{
    int T, n, m;
    cin >> T;
    while(T--)
    {
        memset(sum, 0, sizeof(sum));
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &number[i]);
        scanf("%d", &m);
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d", &q[i].left, &q[i].right);
            q[i].id = i;
        }
        sort(q+1, q+1+m, cmpBySeg);
        map<int, int> rec;
        int pos = 1;
        for(int i = 1; i <= m; i++)
        {
            while(pos <= q[i].right)
            {
                if(0 == rec[number[pos]])
                {
                    rec[number[pos]] = pos;
                    update(pos, 1, n, 1, number[pos]);
                }
                else
                {
                    update(pos, 1, n, 1, number[pos]);
                    update(rec[number[pos]], 1, n, 1, 0);
                    rec[number[pos]] = pos;
                }
                pos++;
            }
            q[i].sum = query(q[i].left, q[i].right, 1, n, 1);
        }
        sort(q+1, q+1+m, cmpById);
        for(int i = 1; i <= m; i++)
            printf("%lld\n", q[i].sum);
    }
    return 0;
}