洛谷P1972(树状数组+离线)

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入格式

第一行：一个整数N，表示项链的长度。

第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。

第三行：一个整数M，表示HH 询问的个数。

接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式

M 行，每行一个整数，依次表示询问对应的答案。

这道题是可以离线+树状数组去做。具体怎么做？就是把询问排序（询问右区间小到大）然后用树状数组去维护一个前缀和，这个前缀和就是表示从1到i出现了多少个不同的数。但是为什么要去离线？我们是为了每次从给定数组左边往右边去延伸得答案。就是我要知道一个[L,R]区间的答案，我不需要知道R+1后面的数字是什么，他对答案无法造成影响，把询问按照区间排序就可以一次从给定序列左边往右边出答案。
那么这里还有问题，就是如果是询问[L,R]区间的答案，仅用树状数组维护前缀和怎么知道[1,L-1]里面有没有哪些是[L,R]区间里面有的，但是普通算前缀和会不小心把它减掉？所采取的方法就是对于我们不断延伸的询问的右区间，我们把每个不同的数所在的区间，都放在目前询问的这个区间的最后出现的地方。也就是说，2,1,3,1,2,3,当我查询[1,3]区间（只是举例）的时候，我2这个数字是放在树状数组第一个区间这个位置的，但是当我查询到[x,5]区间的时候，2这个数字最后一个出现是在5的位置，所以就吧树状数组原本区间1这个地方含有的记录消去（-1），反而在5这个区间的位置+1；这样我们就能再不断延伸区间右端点的时候能够不重复，不少的去得到答案，仅仅只是使用树状数组去维护前缀和。
如果有任何不理解的地方，欢迎继续来询问。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const long long max_ = 1000000 + 50;
int tree_[max_], yuan[max_], pan[max_],n,m;

inline int read()
{
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}

struct k {
	int L, R, ans,wei;
}wenti[max_];
inline int low_bit(int x) {
	return x & (-x);
}

void add_(int x,int value) {
	while (x <= n) {
		tree_[x] += value;
		x += low_bit(x);
	}
}

int ask(int x) {
	int ans = 0;
	while (x > 0) {
		ans += tree_[x];
		x -= low_bit(x);
	}
	return ans;
}
bool cmp(const k &t1, const k &t2) {
	return t1.R < t2.R;
}
bool cmp2(const k &t1, const k &t2) {
	return t1.wei < t2.wei;
}
void solve() {
	for (int i = 1; i <= m; i++) {
		for (int j = wenti[i - 1].R + 1; j <= wenti[i].R; j++) {
			if (pan[yuan[j]])add_(pan[yuan[j]], -1);
			pan[yuan[j]] = j; add_(pan[yuan[j]], 1);
		}
		wenti[i].ans = ask(wenti[i].R) - ask(wenti[i].L - 1);
	}
}
int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		yuan[i] = read();
	}
	m = read();
	for (int i = 1; i <= m; i++) {
		wenti[i].L = read();
		wenti[i].R = read();
		wenti[i].wei = i;
	}
	//cout << endl;
	
	
wenti[0].R = 0;
	sort(wenti + 1, wenti + m + 1, cmp);
	/*for (int i = 1; i <= m; i++) {
		cout<<wenti[i].L <<" "
		<<wenti[i].R <<" "
		<<wenti[i].wei ;
		cout << endl;
	}*/
	solve();
	sort(wenti + 1, wenti + m + 1, cmp2);
	for (int i = 1; i <= m; i++) {
		printf("%d\n", wenti[i].ans);
	}
	return 0;
}