莫队
- 离线询问
- 首先考虑暴力怎么做
- 对于每次询问，移动左右指针，开一个桶记录数的出现次数，复杂度: $ O(nm) $
- 分块，然后区间如果左端点块编号不同，则按右端点排序，否则按左端点对应块编号排序
- 假设块长为 $ B $ ,对于同一个块内右端点最多移动 $ n $ 次,有 $ \frac{n}{B} $ 个,复杂度为 $ O(\frac{n^2}{B}) $
- 对于块编号相同的左端点，最多移动次数为 $ B $ 次, $ m $ 次询问,因此最多移动次数为 $ mB $
- 对于块编号不同的左端点块间距离为 $ 2B $,一共 移动 $ 2B \cdot \frac{n}{B}=2n $ 次
- 一般 $ B $ 取 $ \sqrt n $ 即可,此处让 $ \frac{n^2}{B}=mB 即B=\sqrt \frac{n^2}{m} $
cpp
struct Node{
int id,l,r;
};
int cnt[N],w[M];
int be[M],L[M],R[M],tot,block,res;
bool cmp(Node x,Node y){
return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.l]&1)?x.r<y.r:x.r>y.r);
//奇数块从小到大，偶数块相反
}
void add(int x){
if(!(cnt[w[x]]++))res++;
}
void del(int x){
if(!(--cnt[w[x]]))res--;
}
void solve(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
cin>>m;
vector<Node> q(m);
vector<int> ans(m);
for(int i=0;i<m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
block=sqrt((double)n*n/m),tot=(n+block-1)/block;
for(int i=1;i<=tot;i++){
int l=(i-1)*block+1,r=min(i*block,n);
for(int j=l;j<=r;j++)be[j]=i;
}
sort(q.begin(),q.end(),cmp);
for(int k=0,l=1,r=0;k<m;k++){
auto [id,ql,qr]=q[k];
while(r<qr)add(++r);
while(r>qr)del(r--);
while(l<ql)del(l++);
while(l>ql)add(--l);
ans[id]=res;
}
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}