普通莫队
cpp
namespace Mo{
// 普通莫队
struct Node{
int id,l,r;
};
// be块编号，[L,R]块边界
vector<int> be,L,R;
// block块大小, tot块数量
int block,tot;
vector<Node> que; // 询问
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 init(int n){
block=sqrt(n);
// block=max(1ll,sqrt(1.0*n*n/m));
tot=(n+block-1)/block;
be.assign(n+1,0);
L.assign(tot+1,0);
R.assign(tot+1,0);
que.clear();
for(int i=1;i<=tot;i++){
L[i]=block*(i-1)+1,R[i]=min(block*i,n);
for(int j=L[i];j<=R[i];j++)be[j]=i;
}
}
void add_query(int l,int r){
int id=que.size();
que.push_back({id,l,r});
}
}
using namespace Mo;
void solve(){
int n,m;
cin>>n;
vector<int> w(n+1);
int mx=0;
for(int i=1;i<=n;i++)cin>>w[i],mx=max(mx,w[i]);
cin>>m;
init(n);
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
add_query(l,r);
}
auto work=[&](){
sort(que.begin(),que.end(),cmp);
vector<int> ans(que.size());
vector<int> cnt(mx+1);
int res=0;
auto add=[&](int x){
if(!(cnt[w[x]]++))res++;
};
auto del=[&](int x){
if(!(--cnt[w[x]]))res--;
};
int l=1,r=0;
for(auto [id,ql,qr]:que){
while(r<qr)add(++r);
while(r>qr)del(r--);
while(l<ql)del(l++);
while(l>ql)add(--l);
ans[id]=res;
}
return ans;
};
for(auto &x:work())cout<<x<<"\n";
}