链接：https://ac.nowcoder.com/acm/contest/26896/1036
来源：牛客网

题目描述

萧芸斓是Z国的公主，平时的一大爱好是采花。
今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。
花园足够大，容纳了 n 朵花，花有 c 种颜色（用整数 1−c 表示），且花是排成一排的，以便于公主采花。
公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。
由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 m 个行程，然后一一向你询问公主能采到多少朵花（她知道你是编程高手，定能快速给出答案！），最后会选择令公主最高兴的行程（为了拿到更多奖金！）。

输入描述: 

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

输出描述: 

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

题型：

树状数组--区间修改与单点查询

思路：

这一道题难度中等偏下，在想出来需要维护的东西之后就更简单了（P.S:这道题注意输出的是采到的花的颜色数而不是数量！和题目中的“能采到多少朵花”我只能说牛头不对马嘴，所以雨巨当时讲的就是能采到多少朵花，而不是采到的花的颜色数，不过雨巨对于能采到多少朵花的分析，其实是和采到的花的颜色数的分析是类似的）
下面是分析的过程
我们可以先随意捏造一组花的数据（为了直观），如：
然后最关键的部分来了：如何能够任意选择某个区间，就能直接获得采到的花的颜色数呢？
如果仔细思考过这个问题，会发现，要想每次输入一个区间，就能输出一个值是不合理的，至少在时间复杂度上是不合理的，因为树状数组没办法用区间加减来维护这种值
所以，考虑先把所有的区间询问存储起来，排序之后统一处理。
至于区间如何排序可以先放一放，先看看这些区间的答案是如何求出来的，这也是本题的难点
对于
我们设last[i]为与第i个元素相同的上一个元素所在的位置，lastst[i]为与第i个元素相同的上一个的上一个元素所在的位置，初始都设为0，再设一个tong[i]来存储第i个元素出现的次数，最后设一个tree[i]表示从此处开始，到当前的右区间的采到的花的颜色数（听起来有些拗口，看下面模拟的过程应该能够看懂）
则初始有
我们以右区间为基准，即将右区间从第一个位置扫到最后一个位置
当右区间指向第一个位置 1 时，有

当右区间指向第二个位置 3 时，有

当右区间指向第三个位置 2 时，有

重要的来了！当右区间指向第四个位置 1 时，由于1之前已经出现过，说明开始存在区间右界为4的区间，使得采到的花的颜色数不为0，此时可以得出，需要对[lastst[1]+1~last[1]]（即[1,1]）之间的区间进行+1操作（注意！流程应该为元素先放入桶中，如果桶内元素>=2，则先执行区间+1操作，再更新last和lastst！），执行完上述操作后，有

此时观察一下这个tree数组的值，我们可以看到，tree[i]所对应的值就是区间[i，当前右区间位置]的值（如区间[1,4]的值为1，[2,4],[3,4],[4,4]的值都为0）
同理，当右区间指向第五个位置 3 时

同理，观察一下这个tree数组的值，tree[i]所对应的值就是区间[i，当前右区间位置]的值（如区间[1,5]的值为2，[2,5]的值为1,[3,5],[4,5],[5,5]的值都为0）
为了突出重点，中间的模拟步骤部分省略，直接跳到关键的部分
自行对比一下，下面是当右区间指向第七个位置 4 时的值

现在，当右区间指向第八个位置 3 时，发现3出现了第三次，但是操作仍旧与之前的相同，即对[lastst[3]+1~last[3]]（即[3,5]）之间的区间进行+1操作

最后再放一张当右区间指向最后一个位置时的图片，自行对比是否正确

以上就是模拟过程了，可以发现，代码主要就是区间修改（+1）和单点查询（查询左区间对应的的值），因此代码的自定义函数部分其实就是裸的板子
模拟过程结束了，回到区间排序这个问题上来，我们也不难想出，区间排序应该是以右区间升序排序
这就是大致上的思路过程，其实思路有了（知道应该维护什么了）还是很简单的
（P.S.:昨天刚说写了一篇目前写的最长的题解，今天似乎就更长了...，不过能够锻炼树状数组的构造思维还是很开心的一件事~）

代码： 

#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;
}