离线做法
树状数组
对查询的右端点升序排列
每次只保存距离右端点r最近的颜色,并把上一次的端点删掉
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],tr[N],n,m;
struct Q{
int l,r,id;
bool operator<(const Q &t){
// if(r==t.r)return l<t.l;
return r<t.r;
}
}q[N];
int lsp[N],ans[N];
void add(int x,int c){
for(int i=x;i<=n;i+=i&-i)tr[i]+=c;
}
int sum(int x){
int ans=0;
for(int i=x;i;i-=i&-i)ans+=tr[i];
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++){cin>>q[i].l>>q[i].r;q[i].id=i;}
sort(q+1,q+m+1);
// for(int i=0;i<m;i++){
// cout<<q[i].l<<" "<<q[i].r<<endl;
// }
int last=1;
for(int i=1;i<=m;i++){
int l=q[i].l,r=q[i].r,id=q[i].id;
for(int j=last;j<=r;j++){
if(lsp[a[j]])add(lsp[a[j]],-1);
add(j,1);
lsp[a[j]]=j;
}
last=r+1;
ans[id]=sum(r)-sum(l-1);
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}
很想丹钓战你不觉得吗
话说有题解吗那三道题
我想补一补
noi.cn上有官方题解