题意： 询问区间不同种类颜色数
[2016-11-15]
离线好厉害
对于每一个区间询问，一个数只考虑一次，那么考虑他最后出现的一次
将询问按r排序
从1到n扫描,用树状数组维护一个位置应不应该考虑(记不记入答案)，让每种颜色最后一个出现位置贡献
last[x]是x上一个出现的位置，每到一个a[i]，last位置-1，i位置+1，并更新last
然后对于所有r==i的询问计算答案
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=5e4+,M=2e5+,INF=1e6+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,a[N],last[INF];
struct data{
int l,r,id,ans;
bool operator <(const data &rhs)const{return r<rhs.r;}
}q[M];
inline bool cmp(data a,data b){return a.id<b.id;}
int c[N];
inline int lowbit(int x){return x&-x;}
inline void add(int p,int v){
for(;p<=n;p+=lowbit(p)) c[p]+=v;
}
inline int sum(int p){
int res=;
for(;p>;p-=lowbit(p)) res+=c[p];
return res;
}
int main(){
n=read();
for(int i=;i<=n;i++) a[i]=read(); m=read();
for(int i=;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+,q++m);
int p=;
for(int i=;i<=n;i++){
if(last[a[i]]) add(last[a[i]],-);
add(i,); //printf("%d %d %d %d\n",i,a[i],last[a[i]],p);
last[a[i]]=i;
while(q[p].r==i) q[p].ans=sum(q[p].r)-sum(q[p].l-),p++;
}
sort(q+,q++m,cmp);
for(int i=;i<=m;i++) printf("%d\n",q[i].ans);
}
[2017-01-14]
用主席树做起来直观多了，特别在做了BZOJ3514之后这就是水题啊
last[i]表示i位置的数上一个出现位置，查询区间中last[i]<l的个数，序列建主席树，last权值线段树上就是[0...l-1]的权值和啊
注意权值从0开始注意权值从0开始注意权值从0开始
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lc(x) t[x].l
#define rc(x) t[x].r
const int N=2e5+,MX=1e6+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,Q,x,ql,qr,last[N],pos[MX];
struct node{
int l,r,size;
}t[N*];
int sz,root[N];
void ins(int &x,int l,int r,int p){
t[++sz]=t[x];x=sz;
t[x].size++;
if(l==r) return;
int mid=(l+r)>>;
if(p<=mid) ins(t[x].l,l,mid,p);
else ins(t[x].r,mid+,r,p);
}
int que(int x,int y,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return t[y].size-t[x].size;
else{
int mid=(l+r)>>,ans=;
if(ql<=mid) ans+=que(lc(x),lc(y),l,mid,ql,qr);
if(mid<qr) ans+=que(rc(x),rc(y),mid+,r,ql,qr);
return ans;
}
} int main(){
//freopen("in.txt","r",stdin);
n=read();
for(int i=;i<=n;i++){
x=read();
last[i]=pos[x];
pos[x]=i;
}
for(int i=;i<=n;i++) root[i]=root[i-],ins(root[i],,n,last[i]);//,printf("last %d %d\n",i,last[i]);
Q=read();
while(Q--){
ql=read();qr=read();
printf("%d\n",que(root[ql-],root[qr],,n,,ql-));
}
}