题目背景
无
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入输出格式
输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：
M 行，每行一个整数，依次表示询问对应的答案。
输入输出样例
输入样例#1：
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出样例#1：
2
2
4
说明
数据范围：
对于100%的数据，N <= 500000，M <= 500000。
解析:
我居然为了这道题去学了主席树？？？结果发现树状数组秒解？？？主席树还MLE？？？
我真是超级蒻啊，居然真不会写。。。
口胡请见谅。。。
正解：离线+树状数组/主席树/分块/模拟（雾
我们分析题目，会发现实际上题目就是要我们求一个区间内的不同的数。
我们有一个巧妙的模板解法，可以用不同的数据结构实现：
以每个不同的位置建立数据结构。
我们设一个数组\(a[i]=num\)表示在\(i\)位置上，总共有\(num\)种不同的数。
对于修改：
对于任意的一个数列，我们按照顺序将这个数列从\(1-n\)的位置上的数依次加入\(a\)数组，我们会发现，实际上我们只需维护在当前插入位置\(i\)下，\(1-i\)中各个不同的数出现的最后的位置。
对于询问：
题解有一个\(dalao\)总结的精辟：对于若干个询问的区间[l,r]，如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的。
当然这种做法相当于告诉我们要边处理插入边记录答案，而不能处理完后再记录答案。
对于数组\(a\)，数的位置是移动的。
举个例子：
\(1~2~1~3~4\)
这个数列中，我们的\(a\)数组原先是
\(0~0~0~0~0\)
\(a\)数组加入位置\(1\)的\(1\)后
\(1~0~0~0~0\)
加入位置\(2\)的\(2\)后
\(1~1~0~0~0\)
加入位置\(3\)的\(1\)后
\(0~1~1~0~0\)
就到这里为止，我们就能得出结论：对于一个区间内相同的数字，我们只用关心它最后出现的位置，这样相当于我们只允许所有相同的数字在这个区间内出现一次。
这样我们就可以得出在某一个区间不同的数的总数了，就是插入\(i\)位置的数时\(a\)数组中所有\(1\)的个数。
参考代码：
AC 树状数组
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 500010
#define MOD 2520
#define E 1e-12
using namespace std;
int ask[N<<1],n,m,last[N<<1],a[N<<1],ans[N<<1];
struct rec{
int l,r;
int id;
}q[N];
int query(int x)
{
int ans=0;
for(;x;x-=x&-x) ans+=ask[x];
return ans;
}
void add(int x,int y)
{
for(;x<=n;x+=x&-x) ask[x]+=y;
}
bool cmp(rec a,rec b)
{
return a.r<b.r;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp);
int next=1;
for(int i=1;i<=m;i++){
for(int j=next;j<=q[i].r;j++){
int v=a[j];
if(last[v])
add(last[v],-1);
add(j,1);
last[v]=j;
}
next=q[i].r+1;
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
无耻的贴上MLE2个点的主席树：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 500010
#define MOD 2520
#define E 1e-12
#define ri register int
using namespace std;
struct tree{
int lc,rc;
int sum;
}t[N<<6];
int tot,n,m,root[N*20],last[N*20];
inline int read()
{
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline int build(int l,int r)
{
int p=++tot;
if(l==r) return p;
int mid=(l+r)>>1;
t[p].lc=build(l,mid);
t[p].rc=build(mid+1,r);
return p;
}
inline int change(int pre,int v,int l,int r,int val)
{
int p=++tot;
t[p].lc=t[pre].lc,t[p].rc=t[pre].rc,t[p].sum=t[pre].sum+v;
if(l==r) return p;
int mid=(l+r)>>1;
if(val<=mid) t[p].lc=change(t[pre].lc,v,l,mid,val);
else t[p].rc=change(t[pre].rc,v,mid+1,r,val);
return p;
}
inline int query(int x,int pre,int l,int r)
{
if(l==r) return t[pre].sum;
int mid=(l+r)>>1;
if(x<=mid) return query(x,t[pre].lc,l,mid)+t[t[pre].rc].sum;
else return query(x,t[pre].rc,mid+1,r);
}
int main()
{
n=read();
root[0]=t[0].lc=t[0].rc=t[0].sum;
for(ri i=1;i<=n;i++){
int x;
x=read();
if(last[x]){
int t=change(root[i-1],-1,1,n,last[x]);
root[i]=change(t,1,1,n,i);
}
else{
root[i]=change(root[i-1],1,1,n,i);
}
last[x]=i;
}
m=read();
for(ri i=1;i<=m;i++)
{
int l,r;
l=read(),r=read();
printf("%d\n",query(l,root[r],1,n));
}
return 0;
}