数列找不同（莫队）

题目链接

问题分析

数据应该比较水。这里当作普通莫队的模板题。

思路

将 \(N\) 个整数分块，每块大小为 \(S\) 。将所有询问离线，并排序。左端点在不同块的，左端点小的在前，否则右端点小的在前。

之后每个询问按顺序一个个做。求出 \((l,r)\) 之后，可以花费 \(O(1)\) 转移到 \((l-1,r),(l+1,r),(l,r+1),(l,r-1)\) 。

复杂度证明

排序复杂度为 \(O(m \log m)\)

将左右两个端点分开考虑。对于左端点，由于排过序的关系，从一个转移到下一个最多走 \(S\) 步， 为 \(O(S)\) ；对于右端点，在每个块（按左端点所在的块算）内有序，所以一个块最多花费 \(O(n)\) ，这样右端点为 \(O(n\times \frac{n}{S})\) 。

于是求答案的时间复杂度为 \(O(m \times S + n\times \frac{n}{S})\) 。在本题 \(n,m\) 同阶的情况下取 \(S=\sqrt{n}\) ，时间复杂度为 \(O(n\sqrt{n})\) 。

参考程序

#include <bits/stdc++.h>
using namespace std;

const int Maxn=100010;
int N, Q, A[Maxn], Block;
struct query  {
	int L, R, l, r, Ind;
	inline void Gen(int _Ind) {
		l = (L + Block - 1) / Block;
		r = (R + Block - 1) / Block;
		Ind = _Ind;
		return;
	}
} Query[Maxn];
int Ans[Maxn];
int L, R, Flag, Cnt[Maxn];

inline bool Cmp(query x, query y) {
	if (x.l < y.l) return true;
	if (x.l > y.l) return false;
	if (x.R < y.R) return true;
	return false;
}

int main() {
	scanf("%d%d", &N, &Q);
	Block = int(sqrt(N));
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
	for (int i = 1; i <= Q; ++i) scanf("%d%d", &Query[i].L, &Query[i].R);
	for (int i = 1; i <= Q; ++i) Query[i].Gen(i);
	sort(Query + 1, Query + Q + 1, Cmp);
//	for (int i = 1; i <= Q; ++i) printf("%d %d\n", Query[i].L, Query[i].R);
	L = 1; R = 0; Flag = 0;
	for (int i = 1; i <= Q; ++i) {
		while (R < Query[i].R) if (++Cnt[A[++R]] == 2) ++Flag;
		while (R > Query[i].R) if (--Cnt[A[R--]] == 1) --Flag;
		while (L < Query[i].L) if (--Cnt[A[L++]] == 1) --Flag;
		while (L > Query[i].L) if (++Cnt[A[--L]] == 2) ++Flag;
//		for (int j = 1; j <= N; ++j) printf("%d ", Cnt[j]); printf("\n");
		if (!Flag) Ans[Query[i].Ind] = 1;
	}
	for (int i = 1; i <= Q; ++i) 
		if (Ans[i]) printf("Yes\n"); else printf("No\n");
	return 0;
}