bzoj3809 Gty的二逼妹子序列 & bzoj3236 [Ahoi2013]作业 莫队+分块

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=3809

https://lydsy.com/JudgeOnline/problem.php?id=3236

几乎是双倍经验。

题解

对于第一道题目：

如果没有 \(a, b\) 这个区间的限制，那么这道题就是 bzoj1878 [SDOI2009]HH的项链。

这道题虽然有 \(log\) 的做法，不过很多人应该都是拿这道题作为莫队的入门题的。

考虑如果带上范围限制怎么做。

一种显然的做法就是在莫队修改的时候用树状数组维护一下。但是复杂度 \(O(m\sqrt n \log n)\) GG。

我们需要一种能够 \(O(1)\) 进行修改，查询可以稍微慢一些的数据结构。

符合这个要求的只有分块。

于是做法就是 在莫队修改的时候用分块维护一下每一个权值块的和。

第二道题类似，只是需要多求一个某个区间某个范围的数的个数，一样求就可以了。

时间复杂度 \(O(m\sqrt n)\)。

Code bzoj3809

#include

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair pii;

template inline void read(I &x) {
	int f = 0, c;
	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
	x = c & 15;
	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
	f ? x = -x : 0;
}

const int N = 100000 + 7;
const int M = 1000000 + 7;
const int B = 316 + 7;

#define bl(x) (((x) - 1) / blo + 1)
#define st(x) (((x) - 1) * blo + 1)
#define ed(x) std::min((x) * blo, n)

int n, m, blo, cnt;
int a[N], s[N], ans[N], ansb[N];
int ansc[M];

struct Query {
	int l, r, a, b, *ans;
	inline bool operator < (const Query &b) const { return bl(l) != bl(b.l) ? l < b.l : r < b.r; }
} q[M];

inline void qadd(int x, int k) {
	ans[x] += k;
	ansb[bl(x)] += k;
}
inline int qsum(int l, int r) {
	int cnt = 0;
	for (int i = l; i <= std::min(ed(bl(l)), r); ++i) cnt += ans[i];
	for (int i = bl(l) + 1; i < bl(r); ++i) cnt += ansb[i];
	if (bl(l) != bl(r)) for (int i = st(bl(r)); i <= r; ++i) cnt += ans[i];
	return cnt;
}

inline void madd(int x) {
	++cnt;
	++s[a[x]];
	if (s[a[x]] == 1) qadd(a[x], 1);
}
inline void mdel(int x) {
	++cnt;
	--s[a[x]];
	if (!s[a[x]]) qadd(a[x], -1);
}

inline void work() {
	std::sort(q + 1, q + m + 1);
	int l = 1, r = 0;
	for (int i = 1; i <= m; ++i) {
		while (l > q[i].l) madd(--l);
		while (r < q[i].r) madd(++r);
		while (l < q[i].l) mdel(l++);
		while (r > q[i].r) mdel(r--);
		*q[i].ans = qsum(q[i].a, q[i].b);
//		dbg("l = %d, r = %d: ", l, r);
//		for (int i = 1; i <= n; ++i) dbg("%d%c", ans[i], " \n"[i == n]);
//		if (i >= 106250) dbg("i = %d, cnt = %d\n", i, cnt);
	}
	for (int i = 1; i <= m; ++i) printf("%d\n", ansc[i]);
}

inline void init() {
	read(n), read(m);
	blo = sqrt(n);
	for (int i = 1; i <= n; ++i) read(a[i]);
	for (int i = 1; i <= m; ++i) read(q[i].l), read(q[i].r), read(q[i].a), read(q[i].b), q[i].ans = ansc + i;
}

int main() {
#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
#endif
	init();
	work();
	fclose(stdin), fclose(stdout);
	return 0;
}

Code bzoj 3236

#include

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair pii;

template inline void read(I &x) {
	int f = 0, c;
	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
	x = c & 15;
	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
	f ? x = -x : 0;
}

const int N = 100000 + 7;
const int M = 1000000 + 7;
const int B = 316 + 7;

#define bl(x) (((x) - 1) / blo + 1)
#define st(x) (((x) - 1) * blo + 1)
#define ed(x) std::min((x) * blo, n)

int n, m, blo;
int a[N], s[N], ans[N], ansb[N], ansa[N];
pii ansc[M];

struct Query {
	int l, r, a, b;
	pii *ans;
	inline bool operator < (const Query &b) const { return bl(l) != bl(b.l) ? l < b.l : r < b.r; }
} q[M];

inline void qadd(int x, int k) {
	ans[x] += k, ansa[bl(x)] += k;
	if (ans[x] == 1 && k == 1) ++ansb[bl(x)];
	if (ans[x] == 0 && k == -1) --ansb[bl(x)];
}
inline int qsumb(int l, int r) {
	int cnt = 0;
	for (int i = l; i <= std::min(ed(bl(l)), r); ++i) cnt += !!ans[i];
	for (int i = bl(l) + 1; i < bl(r); ++i) cnt += ansb[i];
	if (bl(l) != bl(r)) for (int i = st(bl(r)); i <= r; ++i) cnt += !!ans[i];
	return cnt;
}
inline int qsuma(int l, int r) {
	int cnt = 0;
	for (int i = l; i <= std::min(ed(bl(l)), r); ++i) cnt += ans[i];
	for (int i = bl(l) + 1; i < bl(r); ++i) cnt += ansa[i];
	if (bl(l) != bl(r)) for (int i = st(bl(r)); i <= r; ++i) cnt += ans[i];
	return cnt;
}

inline void madd(int x) {
	++s[a[x]];
	qadd(a[x], 1);
}
inline void mdel(int x) {
	--s[a[x]];
	qadd(a[x], -1);
}

inline void work() {
	std::sort(q + 1, q + m + 1);
	int l = 1, r = 0;
	for (int i = 1; i <= m; ++i) {
		while (l > q[i].l) madd(--l);
		while (r < q[i].r) madd(++r);
		while (l < q[i].l) mdel(l++);
		while (r > q[i].r) mdel(r--);
		*q[i].ans = pii(qsuma(q[i].a, q[i].b), qsumb(q[i].a, q[i].b));
//		dbg("l = %d, r = %d: ", l, r);
//		for (int i = 1; i <= n; ++i) dbg("%d%c", ans[i], " \n"[i == n]);
//		if (i >= 106250) dbg("i = %d, cnt = %d\n", i, cnt);
	}
	for (int i = 1; i <= m; ++i) printf("%d %d\n", ansc[i].fi, ansc[i].se);
}

inline void init() {
	read(n), read(m);
	blo = sqrt(n);
	for (int i = 1; i <= n; ++i) read(a[i]);
	for (int i = 1; i <= m; ++i) read(q[i].l), read(q[i].r), read(q[i].a), read(q[i].b), q[i].ans = ansc + i;
}

int main() {
#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
#endif
	init();
	work();
	fclose(stdin), fclose(stdout);
	return 0;
}