P1972 [SDOI2009] HH的项链

将全部输入排序，进行离散化

#include<bits/stdc++.h>
using namespace std;

#define rint register int
const int N = 1e6 + 7;

int a[N], tree[N], n, ans[N], st[N];
struct Q{
	int l, r, id;
}q[N];

bool cmp(Q x, Q y){
	return x.r < y.r;
}

int lowbit(int x) { return x & (- x); }

void modify(int x, int k){
	for(rint i = x; i <= n;i += lowbit(i))
		tree[i] += k;
}

int query(int x){
	int ans = 0;
	for(rint i = x; i ;i -= lowbit(i)) ans += tree[i];
	return ans;
}

int main(){
	int m;
	scanf("%d", &n);
	for(rint i = 1;i <= n;i ++) scanf("%d", &a[i]);
	scanf("%d", &m);
	for(rint i = 1;i <= m;i ++){
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	int p = 1;
	sort(q + 1, q + m + 1, cmp);
	for(rint i = 1;i <= m;i ++){
		for(rint j = p;j <= q[i].r;j ++){
			if(st[a[j]]) modify(st[a[j]], -1);
			modify(j, 1);
			st[a[j]] = j;
		}
		p = q[i].r + 1;
		ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
	}
	for(rint i = 1;i <= m;i ++){
		printf("%d\n", ans[i]);
	}
	return 0;
}

原文地址：http://www.cnblogs.com/loser–QAQ/p/16904710.html