HDU 3333 Turing Tree

题目链接

题意：给定一个数组，每次询问一个区间，求出这个区间不同数字的和

思路：树状数组离线处理，把询问按右端点判序，然后用一个map记录下每个数字最右出现的位置，因为一个数字在最右边出现，左边那些数字等于没用了，利用树状数组进行单点修改区间查询即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

const int N = 30005;
const int M = 100005;
typedef long long ll;

int t, n, a[N];
map<int, int> g;

struct Query {
	int l, r, id;
	void read(int id) {
		scanf("%d%d", &l, &r);
		this->id = id;
	}
} query[M];

bool cmp(Query a, Query b) {
	return a.r < b.r;
}

ll ans[M], bit[N];

#define lowbit(x) (x&(-x))

void add(int x, ll v) {
	while (x < N) {
		bit[x] += v;
		x += lowbit(x);
	}
}

ll get(int x) {
	ll ans = 0;
	while (x) {
		ans += bit[x];
		x -= lowbit(x);
	}
	return ans;
}

ll get(int l, int r) {
	return get(r) - get(l - 1);
}

int main() {
	scanf("%d", &t);
	while (t--) {
		g.clear();
		memset(bit, 0, sizeof(bit));
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			query[i].read(i);
		sort(query, query + n, cmp);
		int id = 1;
		for (int i = 0; i < n; i++) {
			while (id <= query[i].r) {
				if (g.count(a[id])) {
					int v = g[a[id]];
					add(v, -a[id]);
					add(id, a[id]);
					g[a[id]] = id;
				} else {
					add(id, a[id]);
					g[a[id]] = id;
				}
				id++;
			}
			ans[query[i].id] = get(query[i].l, query[i].r);
		}
		for (int i = 0; i < n; i++)
			printf("%I64d\n", ans[i]);
	}
	return 0;
}

HDU 3333 Turing Tree（树状数组离线处理）