﻿HDU 3333 Turing Tree(线段树)-Ocrosoft

# Turing Tree

Problem Description
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.

Sample Input
```

2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5

```

Sample Output
```

1
5
6
3
6

```

Author
3xian@GDUT

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
int x[MAXN * 4], y[MAXN * 4]; LL a[MAXN]; LL sum[MAXN * 4];
struct Node
{
int a, b, c;
bool operator<(const Node t)
{
return b < t.b;
}
}b[MAXN];
map<LL, int> mp; LL ans[MAXN];
void build(int pos, int l, int r)
{
x[pos] = l; y[pos] = r; sum[pos] = 0;//建空树
if (x[pos] == y[pos])return;
else
{
int mid = l + r >> 1;
build(pos * 2, l, mid);
build(pos * 2 + 1, mid + 1, r);
//sum[pos] = (sum[pos * 2] * sum[pos * 2 + 1]) % MOD;
}
}
void update(int pos, int p, LL v)
{
if (x[pos] == p&&y[pos] == p)sum[pos] +=v;
else
{
int mid = x[pos] + y[pos] >> 1;
if (p <= mid)update(pos * 2, p, v);
else update(pos * 2 + 1, p, v);
sum[pos] = (sum[pos * 2] +sum[pos * 2 + 1]);
}
}
LL query(int pos, int l, int r)
{
if (x[pos] == l&&y[pos] == r)return sum[pos];
else
{
int mid = x[pos] + y[pos] >> 1;
LL ans = 0;
if (l <= mid)ans+= query(pos * 2, l, min(mid,r));
if (r > mid)ans+= query(pos * 2 + 1, max(mid+1,l), r);
return ans;
}
}
int main()
{
int T; cin >> T;
while (T--)
{
mp.clear();
int n; cin >> n;
repe(i, 1, n)scanf("%I64d", &a[i]);
build(1, 1, n);
int m; cin >> m;
rep(i, 0, m)
{
scanf("%d%d", &b[i].a, &b[i].b);
b[i].c = i;
}
sort(b, b + m);
int k = 1;
rep(i, 0, m)
{
for (; k <= b[i].b;k++)
{
if (mp[a[k]])update(1, mp[a[k]], -a[k]);//如果线段树中存在该数(点)，则删除
mp[a[k]] = k;
update(1, k, a[k]);//往线段树添加这个数
}
ans[b[i].c] = query(1, b[i].a, b[i].b);
}
rep(i, 0, m)printf("%I64d\n", ans[i]);
}
return 0;
}```