题目

洛谷题目

题解

莫队板子题

• 普通莫队的操作

1. 将询问排序
2. 定义L,R指针跳到询问区间

• 排序方式
  将整个区间分为不同块，块长为$\frac{n}{\sqrt{m}}$m​n​有的大佬说是$\sqrt{n}$n​但是推一下就知道$\frac{n}{\sqrt{m}}$m​n​更合理
• 指针跳动 这个应该很好理解吧
• 跳动时答案统计方式（看代码理解吧）
  $cnt[i]$cnt[i]表示颜色为$i$i出现的次数

//inline void add(int x) { if (!cnt[ a[x] ]) ans++; ++cnt[ a[x] ]; }
//inline void del(int x) { --cnt[ a[x] ]; if (!cnt[ a[x] ]) ans--; }
inline void add(int x) { if (!cnt[ a[x] ]++) ans++; }
inline void del(int x) { if (!--cnt[ a[x] ]) ans--; }

/*
while (l < ql) del(l++); 
while (l > ql) add(--l); 
while (r > qr) del(r--); 
while (r < qr) add(++r); 
*/
while (l < ql) ans -= !--cnt[ a[l++] ]; 
while (l > ql) ans += !cnt[ a[--l] ]++; 
while (r > qr) ans -= !--cnt[ a[r--] ]; 
while (r < qr) ans += !cnt[ a[++r] ]++; 

不同的写法效果相同，但常数不同

code

#include <bits/stdc++.h>
using namespace std; 
//const int maxn = 3e4 + 1000; 
//const int maxc = 1e6 + 1000; 
const int maxm = 5e6 + 1000; 

template <typename T>
inline void read(T &s) {
	s = 0; 
	T w = 1, ch = getchar(); 
	while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
	while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	s *= w; 
}

int n, m, k, blo, ans, res[maxm]; 
int a[maxm], cnt[maxm]; 
struct query { int l, r, id, bl; } q[maxm];

inline bool cmp(query aa, query bb) { 
	return (aa.bl == bb.bl) ? aa.r < bb.r : aa.l < bb.l; 
}

//inline void add(int x) { if (!cnt[ a[x] ]) ans++; ++cnt[ a[x] ]; }
//inline void del(int x) { --cnt[ a[x] ]; if (!cnt[ a[x] ]) ans--; }
//inline void add(int x) { if (!cnt[ a[x] ]++) ans++; }
//inline void del(int x) { if (!--cnt[ a[x] ]) ans--; }

int main() {
	read(n);
	for (int i = 1; i <= n; ++i) read(a[i]); 
	read(m); 
//	blo = n / sqrt(m);
	blo = sqrt(n);  
	for (int i = 1; i <= m; ++i) {
		read(q[i].l), read(q[i].r);
		q[i].id = i, q[i].bl = q[i].l / blo; 
	}
	
	sort(q + 1, q + m + 1, cmp); 
	
	int l = 1, r = 0; 
	for (int i = 1; i <= m; ++i) {
		int ql = q[i].l, qr = q[i].r; 
//		while (l < ql) del(l++); 
//		while (l > ql) add(--l); 
//		while (r > qr) del(r--); 
//		while (r < qr) add(++r); 
		
		while (l < ql) ans -= !--cnt[ a[l++] ]; 
		while (l > ql) ans += !cnt[ a[--l] ]++; 
		while (r > qr) ans -= !--cnt[ a[r--] ]; 
		while (r < qr) ans += !cnt[ a[++r] ]++; 
		res[ q[i].id ] = ans; 
	}
	for (int i = 1; i <= m; ++i) {
		printf("%d\n", res[i]); 
	}
	return 0; 
}