[SDOI 2009] HH 的项链

知识点

离线查询、树状数组、区间去重

解题思路

按查询右端点升序离线处理。从左到右加入a[i]：若该值此前出现过，在旧位置减1，再在i加1，更新最后出现位置。此时树状数组中每个值仅在最后一次出现处贡献1。对[l,r]取前缀和差就是不同值个数，按原编号输出。

正确性说明

处理到r时，某种值在[l,r]存在，当且仅当其在前r项的最后位置不小于l。树状数组恰在这些最后位置放1，所以区间和与不同值一一对应。所有查询在其右端点完成后回答，恢复原序即可。

易错点

更新旧位置时要减去1；离线排序后按原序输出；相同区间可重复出现；数据大需快速读入。

复杂度

时间O((n+m)log n+m log m)，空间O(n+m+U)，U=10^6。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Fast{int get(){int x=0,c=getchar();while(c<=32&&c!=EOF)c=getchar();while(c>32&&c!=EOF){x=x*10+c-'0';c=getchar();}return x;}}in;struct Q{int l,r,id;};int main(){int n=in.get();vector<int>a(n+1),bit(n+1),last(1000001);for(int i=1;i<=n;i++)a[i]=in.get();int m=in.get();vector<Q>q(m);vector<int>ans(m);for(int i=0;i<m;i++)q[i]={in.get(),in.get(),i};sort(q.begin(),q.end(),[](Q x,Q y){return x.r<y.r;});auto add=[&](int x,int v){for(;x<=n;x+=x&-x)bit[x]+=v;};auto sum=[&](int x){int s=0;for(;x;x-=x&-x)s+=bit[x];return s;};int p=0;for(auto x:q){while(p<x.r){++p;if(last[a[p]])add(last[a[p]],-1);add(p,1);last[a[p]]=p;}ans[x.id]=sum(x.r)-sum(x.l-1);}for(int v:ans)printf("%d\n",v);}