题意：询问不同区间不同值的个数
//思路1 700+ms
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define CL(a,b) memset(a,b,sizeof(a))
const int M(100010);
const int N(1020);
int f[N],r[M];
struct data{
int x,sub;
}a[M];
struct dat{
int l,r;
int sub;
}ans[N];
int vis[M];
bool cmp(data x,data y)
{
return x.x<y.x;
}
bool cm(dat x,dat y )
{
return x.l<y.l||(x.l==y.l&&x.r<y.r);
}
int main()
{
int m,i,n,j,q;
while(scanf("%d",&m)!=EOF)
{
for(i=1;i<=m;i++)
{
scanf("%d",&a[i].x);
a[i].sub=i;
}
sort(a+1,a+m+1,cmp);
r[a[1].sub]=0;
for(i=2,j=0;i<=m;i++)//离散化
{
if(a[i-1].x==a[i].x)
r[a[i].sub]=j;
else
{
j++;
r[a[i].sub]=j;
}
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&ans[i].l,&ans[i].r);
ans[i].sub=i;
}
sort(ans,ans+q,cm);
CL(f,0); CL(vis,0);//vis记录出现个数
for(i=0;i<q;i++)
{
if(i==0)
{
CL(vis,0);
for(j=ans[i].l;j<=ans[i].r;j++)
{
if(!vis[r[j]])
f[ans[i].sub]++;
vis[r[j]]++;
}
continue;
}
if(ans[i].r<ans[i-1].r)
{
if((ans[i].l-ans[i-1].l+ans[i-1].r-ans[i].r)>(ans[i].r-ans[i].l))
{
CL(vis,0);
for(j=ans[i].l;j<=ans[i].r;j++)
{
if(!vis[r[j]])
f[ans[i].sub]++;
vis[r[j]]++;
}
}
else
{
f[ans[i].sub]=f[ans[i-1].sub];
for(j=ans[i-1].l;j<ans[i].l;j++)
{
vis[r[j]]--;
if(vis[r[j]]==0)
f[ans[i].sub]--;
}
for(j=ans[i].r+1;j<=ans[i-1].r;j++)
{
vis[r[j]]--;
if(vis[r[j]]==0)
f[ans[i].sub]--;
}
}
}
else
{
if((ans[i].l-ans[i-1].l)>(ans[i-1].r-ans[i].l))
{
CL(vis,0);
for(j=ans[i].l;j<=ans[i].r;j++)
{
if(!vis[r[j]])
f[ans[i].sub]++;
vis[r[j]]++;
}
}
else
{
f[ans[i].sub]=f[ans[i-1].sub];
for(j=ans[i-1].l;j<ans[i].l;j++)
{
vis[r[j]]--;
if(vis[r[j]]==0)
f[ans[i].sub]--;
}
for(j=ans[i-1].r+1;j<=ans[i].r;j++)
{
if(!vis[r[j]])
f[ans[i].sub]++;
vis[r[j]]++;
}
}
}
}
for(i=0;i<q;i++)
printf("%d\n",f[i]);
}
}
//参考：http://blog.csdn.net/sqplfh/article/details/6840996
具体思路：先把N个保存下来，进行离散，然后用就可以用flag记录某个数前面出现的位置，再把询问保存下来，按右端点排序。
对N个数依次处理，删除该数前面出现的，在当前位置插入该数。当处理到第i个位置的数，且询问的右端点也为i是，统计个数。
// 300+ms 线段树优化
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define CL(a,b) memset(a,b,sizeof(a))
#define MID(a,b) (a+b)>>1
const int M(100010);
const int N(1020);
int tree[M<<2],r[M],f[N];
struct data{
int x,sub;
}a[M];
struct dat{
int l,r;
int sub;
}ans[N];
int vis[M];
bool cmp(data x,data y)
{
return x.x<y.x;
}
bool cm(dat x,dat y )
{
return x.r<y.r;
}
inline void pushup(int t)
{
tree[t]=tree[t<<1]+tree[t<<1|1];
}
void insert(int t,int x,int val,int l,int r)
{
if(l==r)
{
tree[t]=val;
return;
}
int mid=MID(l,r);
if(x<=mid)
insert(t<<1,x,val,l,mid);
if(x>mid)
insert(t<<1|1,x,val,mid+1,r);
pushup(t);
}
int query(int t,int ql,int qr,int l,int r)
{
if(ql<=l&&qr>=r)
return tree[t];
int mid=MID(l,r);
if(qr<=mid)
return query(t<<1,ql,qr,l,mid);
else if(ql>mid)
return query(t<<1|1,ql,qr,mid+1,r);
else
return query(t<<1,ql,qr,l,mid)+query(t<<1|1,ql,qr,mid+1,r);
}
int main()
{
int m,i,n,j,q;
while(scanf("%d",&m)!=EOF)
{
for(i=1;i<=m;i++)
{
scanf("%d",&a[i].x);
a[i].sub=i;
}
sort(a+1,a+m+1,cmp);
r[a[1].sub]=0;
for(i=2,j=0;i<=m;i++)
{
if(a[i-1].x==a[i].x)
r[a[i].sub]=j;
else
{
j++;
r[a[i].sub]=j;
}
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&ans[i].l,&ans[i].r);
ans[i].sub=i;
}
sort(ans,ans+q,cm);
CL(vis,-1); CL(tree,0);
for(i=1,j=0;i<=m&&j<q;i++)
{
if(vis[r[i]]!=-1)
{
insert(1,vis[r[i]],0,1,m);
}
insert(1,i,1,1,m);
vis[r[i]]=i;
while(i==ans[j].r)
{
f[ans[j].sub]=query(1,ans[j].l,ans[j].r,1,m);
j++;
//printf("%d\n",tree[1]);
}
}
for(i=0;i<q;i++)
printf("%d\n",f[i]);
}
}