洛谷 P1972 [SDOI2009] HH的項鍊

題目連結

https://www.luogu.org/problem/P1972

分析

将詢問離線，同時要用到樹狀數組。

先把詢問按右端點升序排序，依次處理，此時對于重複出現的數，我們實際上隻關心目前最靠右的。

AC代碼

#include <cstdio>
#include <algorithm>

using namespace std;

inline int get_num() {
	int num = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
		num = num * 10 + c - '0', c = getchar();
	return num;
}

const int maxn = 5e5 + 5, maxc = 1e6 + 5;

struct Question {
	int l, r, id;
	bool operator < (const Question& rhs) const {
		return r < rhs.r;
	}
} q[maxn];

int n, m, num[maxn], last[maxc], bit[maxn], ans[maxn];

inline int ask(int x) {
	int sum = 0;
	while (x) sum += bit[x], x -= x & (-x);
	return sum;
}

inline void add(int x, int d) {
	while (x <= n)
		bit[x] += d, x += x & (-x);
}

int main() {
	n = get_num();
	for (int i = 1; i <= n; ++i) num[i] = get_num();
	m = get_num();
	for (int i = 1; i <= m; ++i)
		q[i].l = get_num(), q[i].r = get_num(), q[i].id = i;
	sort(q + 1, q + m + 1);
	int j = 0;
	for (int i = 1; i <= m; ++i) {
		while (j < q[i].r) {
			++j;
			if (last[num[j]]) add(last[num[j]], -1);
			add(j, 1);
			last[num[j]] = j;
		}
		ans[q[i].id] = ask(q[i].r) - ask(q[i].l - 1);
	}
	for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
	return 0;
}