补一个扫描线题解。
解法
一句话题意：给定一个序列，多次询问区间 $[l,r]$ 中有多少种不同的数。
我们设序列中 $a_i$ 上一次出现的位置为 $pre_i$，如果 $a_i$ 没有出现过，则 $pre_i = 0$。不难发现如果一种数在区间中出现多次，只会产生一次贡献。不妨钦定每种数产生贡献的位置是区间中第一次出现的位置，这时可以发现，产生的总贡献即为 $pre_x \le l - 1$ 的个数，反证法易证。
现在问题即为：给定一个序列 $pre$，多次查询区间 $[l,r]$ 中有多少个 $pre_i \le l - 1$。
我们把每一个 $pre_i$ 抽象到二维平面的点上，把 $i$ 看作横坐标，$pre_i$ 看作纵坐标，问题既转化为了经典的二维数点问题，每次询问左下角为 $(l,0)$，右上角为 $(r,l - 1)$ 的矩形中有几个点。
注意到这个询问是可差分的，我们可以将询问差分为左下角为 $(0,0)$，右上角为 $(r,l - 1)$ 的矩形减去左下角为 $(0,0)$，右上角为 $(l - 1,l - 1)$ 的矩形有几个点，这样方便我们使用扫描线思想。
我们将所有操作按横坐标排序（包括加点操作和查询操作），建立线段树，维护每个纵坐标出现个数。从左向右扫，如果遇到加点操作就在其纵坐标相应的线段树位置上加 $1$，如果遇到查询操作就查询线段树中 $[0,val]$ 的个数。
单次操作复杂度 $\mathcal{O}(\log n)$，共有 $n$ 次加点操作和 $2m$ 次查询操作，总时间复杂度 $\mathcal{O}((n + m) \log n)$。
代码
#include<bits/stdc++.h>
namespace fast_IO
{
/**
* 快读快写
*/
};
using namespace fast_IO;
int n,m,a[1000010],pre[1000010],lst[1000010],ans[1000010],tot;
struct ope
{
int type,x,y,id;
inline bool operator<(const ope &rhs) const
{
if(x==rhs.x) return type<rhs.type;
return x<rhs.x;
}
};
ope op[3000010];
struct node
{
int cnt;
node *lc,*rc;
inline node()
{
cnt=0,lc=rc=nullptr;
}
inline void pushup()
{
cnt=lc->cnt+rc->cnt;
}
};
class seg_tree
{
#define ls l,mid
#define rs mid+1,r
private:
node *root;
inline node *build(int l,int r)
{
node *rt=new node();
if(l<r)
{
int mid=(l+r)/2;
rt->lc=build(ls),rt->rc=build(rs);
}
return rt;
}
inline void fix(node *rt,const int pos,int l,int r)
{
if(l==r)
{
rt->cnt++;
return;
}
int mid=(l+r)/2;
if(pos<=mid) fix(rt->lc,pos,ls);
else fix(rt->rc,pos,rs);
rt->pushup();
}
inline int ask(node *rt,const int L,const int R,int l,int r)
{
if(L<=l && r<=R) return rt->cnt;
int mid=(l+r)/2,ret=0;
if(L<=mid) ret+=ask(rt->lc,L,R,ls);
if(R>mid) ret+=ask(rt->rc,L,R,rs);
return ret;
}
public:
inline void build()
{
root=build(0,n);
}
inline void fix(const int pos)
{
fix(root,pos,0,n);
}
inline int ask(const int L,const int R)
{
return ask(root,L,R,0,n);
}
};
seg_tree tree;
int main()
{
in>>n,tree.build();
for(int i=1;i<=n;i++) in>>a[i],pre[i]=lst[a[i]],lst[a[i]]=i,op[++tot]=(ope){0,i,pre[i],i};
in>>m;
for(int i=1,l,r;i<=m;i++) in>>l>>r,op[++tot]=(ope){1,r,l-1,i},op[++tot]=(ope){2,l-1,l-1,i};
std::sort(op+1,op+tot+1);
for(int i=1;i<=tot;i++)
{
if(op[i].type==0) tree.fix(op[i].y);
else if(op[i].type==1) ans[op[i].id]+=tree.ask(0,op[i].y);
else ans[op[i].id]-=tree.ask(0,op[i].y);
}
for(int i=1;i<=m;i++) out<<ans[i]<<'\n';
fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
return 0;
}
