http://www.zybbs.org/JudgeOnline/problem.php?id=1878

其实很想写在线划分树虐这题……但是考虑到我有可能会晕或者会吐，最后还是写了萎缩的离线算法！

第一次交居然忘了删掉调试输出……我太2了，看着输出中一堆乱七八糟的东西居然高兴地交了上去

原来printf这么慢……我一开始写出来rank2，膜拜了tim的代码后发现他加了个输出优化，然后我也加了，速度几乎快了一半……

将数字从左到右插入，每插入一个数字就处理右端点是这个点的所有询问。即插入一个数后要维护这个点之前的所有点，到这个点的区间内不同数字个数。

设当前点为b，考虑这个点的数字前一次出现的点i：

1.如果左端点a在点1..i中，那么a..b中不同数字的个数和a..b-1是一样的（i和b相同，可以忽略b）。

2.如果左端点a在点i+1..b-1中，那么a..b中不同数字个数就是a..b-1中不同数字个数+1（即b所对应的数字）。

3.b对应的数字还没出现过，那么不管左端点在哪里都+1，参照2

4.左端点就是b，那么答案显然是1

于是我们其实每次做的事情就是给i+1..b这个区间+1。每个询问就是询问某个位置上的数是多少。

显然可以线段树/树状数组……树状数组的区间+1就是(1..b)+1后(1..i)-1。

#include <stdio.h>
int a[50000],n,i=-1,m,k[50001],q[1000001];
char str[3000000],*p=str,out[1000000],*o=out;
struct query{struct query *next;int l,a}*map[50001],st[200000];
inline void I(x,y){for(;x;x-=x&-x)k[x]+=y;}
inline Q(x){int ans=0;for(;x<=i;x+=x&-x)ans+=k[x];return ans;}
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}main(){
	int l,r;char buf[10];fread(p,1,3000000,stdin);
	for(n=getint();++i!=n;a[i]=getint());
	for(i=m=getint();i--;(map[r]=st+i)->l=l){l=getint();st[i].next=map[r=getint()];}
	for(i=0;i!=n;)for(I(q[a[i]],-1),I(q[a[i]]=++i,1);map[i];map[i]=map[i]->next)map[i]->a=Q(map[i]->l);
	for(;m--;*o++='\n')if(!st[m].a)*o++=48;
	else{
		for(l=0;st[m].a;st[m].a/=10)buf[l++]=st[m].a%10+48;
		while(l--)*o++=buf[l];
	}*--o=0;
	return puts(out),0;
}

• inline
• block