HUD-3333 离线 + 树状数组 + 区间不同值和 + 思想

第一次做这种题，没有这种思想，总结一下。

HUD-3333是一道求解指定区间内不重复元素的和值。由于输入数据特别大，还不会离散化，因此使用map映射不同值。

题目大意：

现在给定N个数字序列A1，A2，...，AN和多个Queries（i，j）（1≤i≤j≤N）。对于每个Query（i，j），您将计算子序列Ai，Ai + 1，...，Aj中不同值的总和。

输入

第一行是整数T（1≤T≤10），决定下面的测试用例数。

对于每种情况，输入格式如下：

*第1行：N（1≤N≤30,000）。

*第2行：N个整数A1，A2，...，AN（0≤Ai≤1,000,000,000）。

*第3行：Q（1≤Q≤100,000），查询数。

*接下来的Q行：每行包含2个整数i，j，代表一个查询（1≤i≤j≤N）。

输出

对于每个查询，在一行中打印指定子序列的不同值之和。

样本输入

2

3

1 1 4

2

1 2

2 3

5

1 1 2 1 3

3

1 5

2 4

3 5

样本输出

1

5

6

3

6

思路：

1.首先使用一个pre[]数组，pre[i]表示输入数据中第i个数的前一个重复数的下标，如果第i个数第一次出现，则pre[i] = 0;

2.使用一个map映射map<long long, int>，用于保存当前输入数值的最后一次出现的位置(下标)，配合更新pre;

3.采用树状数组msum保存区间不重复的和值，初始为空。

4.离线所有查询操作，对查询操作按找所有提问区间的 r 排序(即按照所有提问区间的右端升序排序) 。这样可以保证当有大的区间覆盖小的区间时，不需要重新计算小的那一部分。

5.按照离线的问题数量，将输入数据列一个一个的加入树状数组中(输入的数最后不一定都加入了树状数组，减少没必要的计算)，如果当前加入的数now ， 它的前面已经加入了这个数，即pre[now]不为0，则删除前面已经加入的，重新加入now这个数。这样保证了每次重复出现了的数都将在区间后面一个接一个的更新，使得区间具有了向后扩展的性质。

6.在加入树状数组的过程中，当到达了问题的区间 r 时，就计算一次区间和。利用树状数组的性质取计算。

7.按照提问顺序保存答案顺序，最后依此输出即可。

AC代码：

#include<cstdio> 
#include<cstring>
#include<map>
#include<algorithm>
using namespace std; 
typedef long long ll;
const int maxn = 3e5 + 5;
const int Q = 1e5 + 5;
map<ll ,int>mmp;
ll a[maxn], msum[maxn], ANS[maxn];
int pre[maxn], t, n, q;

struct Node{
	int l, r, id;
}node[Q];//离线问题

bool cmp(Node a, Node b){
	if(a.r == b.r){
		return a.l < b.l;
	}
	return a.r < b.r;
}

void update(int x, ll v){
	for(int i = x;i <= n;i += i & (-i)){
		msum[i] += v;
	}
}

ll getNum(int x){
	ll ans = 0;
	for(int i = x; i > 0;i -= i & (-i)){
		ans += msum[i];
	}
	return ans;
}
 
int main(){
	scanf("%d", &t);
	while(t--){
		memset(msum, 0 ,sizeof msum);
		memset(ANS, 0, sizeof ANS);
		memset(pre, 0, sizeof pre);
		mmp.clear();
		scanf("%d", &n);
		for(int i = 1;i <= n;i++){
			scanf("%lld", a + i);
			pre[i] = mmp[a[i]];
			mmp[a[i]] = i;//保存最后一次出现的位置 
		}
		scanf("%d", &q);
		for(int i = 1;i <= q;i++){
			scanf("%d%d", &node[i].l, &node[i].r);
			node[i].id = i;	//保存提问的顺序，从而保证输出的顺序！！！！ 
		}
		sort(node + 1, node + q + 1, cmp);//按r的大小排序 
		int now = 1; //逐个加入 
		for(int i = 1; i <= q;i++){
			while(now <= node[i].r){
				if(pre[now]){
					update(pre[now], -a[now]);
				}
				update(now, a[now]);
				now++;
			}
			ANS[node[i].id] = getNum(node[i].r) - getNum(node[i].l - 1);
		}
		for(int i = 1;i <= q;i++){
			printf("%lld\n",ANS[i]);
		}
	}
	
	return 0;
}