题解 | #[HEOI2012]采花#

题目描述

第一行三个空格隔开的整数 n、c以及 m。
接下来一行 n 个空格隔开的整数，每个数在[1, c]间，第 i 个数表示第 i 朵花的颜色。
接下来 m 行每行两个空格隔开的整数 l 和 r（l≤r），表示女仆安排的行程为公主经过第 l 到第 r 朵花进行采花。

共 m 行，每行一个整数，第 i 个数表示公主在女仆的第 i 个行程中能采到的花的颜色数。

题型：

#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int N=2097153;
int tree[N],a[N],last[N],lastst[N],tong[N];
int n,m,c;
struct node{
	int id,L,R,ans;
}d[N];
int lowbit(int x){
	return x&(-x);
}

void add(int i,int val){
	while(i<=n){
		tree[i]+=val;
		i+=lowbit(i);
	}
}

int sum(int i){
	int ans=0;
	while(i>0){
		ans+=tree[i];
		i-=lowbit(i);
	}
	return ans;
}

int cmp(struct node a,struct node b){
	return a.R<b.R;
}

int cmp2(struct node a,struct node b){
	return a.id<b.id;
}

signed main(){
	scanf("%lld%lld%lld",&n,&c,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;i++){
		d[i].id=i;
		scanf("%lld%lld",&d[i].L,&d[i].R);
	}
	sort(d+1,d+1+m,cmp); //按照右区间升序排序
	int pos=1;
	for(int i=1;i<=n;i++){
		tong[a[i]]++;
		if(tong[a[i]]>=2){ //元素出现次数>=2次，执行区间+1操作
			add(lastst[a[i]]+1,1);
			add(last[a[i]]+1,-1);
		}
		lastst[a[i]]=last[a[i]]; //更新lastst
		last[a[i]]=i; //更新last
		while(d[pos].R==i && pos<=m){ //获取答案并且存储在对应区间内
			d[pos].ans=sum(d[pos].L);
			pos++;
		}
	}
	sort(d+1,d+1+m,cmp2); //按照输入顺序升序排序
	for(int i=1;i<=m;i++){
		printf("%lld\n",d[i].ans);
	}
	return 0;
}