luogu1972 [SDOI2009]HH的项链

莫队裸题还不带修改

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, m, qcnt, ans, col[1000005], bse, blc[50005], a[50005], qwq[200005];
struct Query{
	int xxx, yyy, idx;
}q[200005];
bool cmp(Query u, Query v){
	if(blc[u.xxx]==blc[v.xxx])	return u.yyy<v.yyy;
	else	return blc[u.xxx]<blc[v.xxx];
}
void del(int x){
	if(--col[x]==0)	ans--;
}
void add(int x){
	if(++col[x]==1)	ans++;
}
void md(){
	int l=1, r=0;
	for(int i=1; i<=m; i++){
		while(l<q[i].xxx)	del(a[l++]);
		while(l>q[i].xxx)	add(a[--l]);
		while(r<q[i].yyy)	add(a[++r]);
		while(r>q[i].yyy)	del(a[r--]);
		qwq[q[i].idx] = ans;
	}
}
int main(){
	cin>>n;
	bse = sqrt(n);
	for(int i=1; i<=n; i++){
		scanf("%d", &a[i]);
		blc[i] = (i - 1) / bse + 1;
	}
	cin>>m;
	for(int i=1; i<=m; i++){
		scanf("%d %d", &q[i].xxx, &q[i].yyy);
		q[i].idx = i;
	}
	sort(q+1, q+1+m, cmp);
	md();
	for(int i=1; i<=m; i++)
		printf("%d
", qwq[i]);
	return 0;
}

也可以考虑维护一个pre，代表每个颜色的前面的出现的位置，然后树状数组

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int pre[1000005], n, m, cnt, lst=1, c[50005];
struct Point{
	int pr, co;
}pnt[50005];
struct Ques{
	int ll, rr, lask, rask;
}qu[200005];
struct Asks{
	int lc, li, ans, id;
}ak[400005];
bool cmp1(Asks x, Asks y){
	return x.lc<y.lc;
}
bool cmp2(Asks x, Asks y){
	return x.id<y.id;
}
int lowbit(int x){
	return x & -x;
}
void add(int pos){
	if(!pos){
		c[pos]++;
		return ;
	}
	while(pos<=n){
		c[pos]++;
		pos += lowbit(pos);
	}
}
int query(int pos){
	int re=0;
	while(pos){
		re += c[pos];
		pos -= lowbit(pos);
	}
	return re+c[0];
}
int main(){
	cin>>n;
	for(int i=1; i<=n; i++){
		scanf("%d", &pnt[i].co); 
		pnt[i].pr = pre[pnt[i].co];
		pre[pnt[i].co] = i;
	}
	cin>>m;
	for(int i=1; i<=m; i++){
		scanf("%d %d", &qu[i].ll, &qu[i].rr);
		ak[++cnt] = (Asks){qu[i].ll-1, qu[i].ll-1, 0, cnt};
		ak[++cnt] = (Asks){qu[i].rr, qu[i].ll-1, 0, cnt};
		qu[i].lask = cnt - 1;
		qu[i].rask = cnt;
	}
	sort(ak+1, ak+1+cnt, cmp1);
	for(int i=1; i<=cnt; i++){
		while(lst<=ak[i].lc){
			add(pnt[lst].pr);
			lst++;
		}
		ak[i].ans = query(ak[i].li);
	}
	sort(ak+1, ak+1+cnt, cmp2);
	for(int i=1; i<=m; i++)
		printf("%d
", ak[qu[i].rask].ans-ak[qu[i].lask].ans);
	return 0;
}