程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3333 Turing Tree（樹狀數組 || 線段樹）

HDU 3333 Turing Tree（樹狀數組 || 線段樹）

編輯：C++入門知識

HDU 3333 Turing Tree（樹狀數組 || 線段樹）

題意：給定一個區間，q個查詢，對於每次查詢回答這個區間內所有不重復的數的和。

思路：可以考慮使用樹狀數組來做。

先讀入所有查詢，離線來做，將所有查詢按右端點升序排序。

那麼我們從給定區間的第一個元素開始遍歷這個區間，在此過程中更新每一個元素上一次出現的位置，每次將現在位置加上a[i]並將lastpos位置減去a[i]，

也就是說，我們每一步都是保留與當前位置距離最近的重復元素值，其余置零，那麼這樣肯定能保證答案正確，

如果遍歷到的這個位置恰好是一個詢問的右端點，那麼我們輸出修改後的區間值之和。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
#define pii (pair)
//#pragma comment(linker, /STACK:1024000000,1024000000) 
using namespace std;  

const int maxn = 30000 + 300;
const int maxq = 100000+1000;
//const int INF = 0x3f3f3f3f;
int n, q;
int a[maxn], lastpos[maxn];
LL C[maxn];
map Hash;
int ha;
struct Query {
	int l, r, id;
	bool operator < (const Query& A) const {
		return r < A.r;
	}
} query[maxq];
LL ans[maxq];
int lowbit(int x) {
	return (x&(-x));
} 
LL sumv(int x) {
	LL ret = 0;
	while(x > 0) {
		ret += C[x]; x -= lowbit(x);
	}
	return ret;
}
void add(int x, int d) {
	while(x <= n) {
		C[x] += d; x += lowbit(x);
	}
}
int dis(int x) {
	if(!Hash.count(x)) return Hash[x] = ++ha;
	return Hash[x];
} 
void init() {
	ha = 0;
	Hash.clear();
	memset(lastpos, 0, sizeof(lastpos));
	memset(C, 0, sizeof(C));
} 
int main() {
//	freopen(input.txt, r, stdin);
	int T; cin >> T;
	while(T--) {
		init();
		cin >> n;
		for(int i = 1; i <= n; i++) scanf(%d, &a[i]);
		cin >> q;
		for(int i = 0; i < q; i++) {
			int u, v; scanf(%d%d, &u, &v);
			query[i].l = u;
			query[i].r = v;
			query[i].id = i;
		}
		sort(query, query+q);
		int cnt = 0;
		for(int i = 1; i <= n; i++) {
			if(!lastpos[dis(a[i])]) add(i, a[i]), lastpos[dis(a[i])] = i;
			else {
				add(i, a[i]);
				add(lastpos[dis(a[i])], -a[i]);
				lastpos[dis(a[i])] = i;
			}
			while(cnt