P4688 [Ynoi2016] 掉进兔子洞

题意

给定长度为 \(n\) 的序列 \(s\)。

有 \(m\) 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。

Sol

不难发现答案即为求：\(r1 - l1 + r2 - l2 + r3 - l3 + 3 - siz\)。其中 \(siz\) 表示三个区间的公共颜色的个数。

仔细想想，发现这个东西和 \(bitset\) 维护种类数很像。

如果我们能使得相同的数也能一一对应，不就可以做了？

考虑在离散化的时候处理一下，发现直接去掉 \(unique\) 就能在中间空出空位。

设当前 \(s_i\) 的个数为 \(cur_{s_i}\)。我们只需要使 \(bitset[s_i + cur_{s_i}] = 1\) 就行了。

至此，我们已经会做 \(1\) 次询问了。

剩下的就简单了，直接套上莫队，空间开不下就跑 \(4\) 遍就行了。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <bitset>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

const int N = 1e5 + 5, M = 2.5e4 + 5;

array <bitset <N>, M> ans;
array <int, N> s, h;

namespace Cpt {

int bsi = 357;

struct Node {

int l, r, id;
bool operator <(const Node &t) {
	if (l / bsi != t.l / bsi) return l < t.l;
	return (l / bsi) & 1 ? r < t.r : r > t.r;
}

};

array <int, N> cur;
bitset <N> isl;

void add(int x) {
	isl[s[x] + cur[s[x]]] = 1;
	cur[s[x]]++;
}

void del(int x) {
	cur[s[x]]--;
	isl[s[x] + cur[s[x]]] = 0;
}


}

array <Cpt::Node, 3 * M> qrl;
array <int, M> suf;

void solve(int &m) {
	int cnt = 0, idx = 0; Cpt::cur.fill(0);
	while (m && cnt <= (int)(2.5e4)) {
		cnt++, m--;
		ans[cnt].set();
		int l1 = read(), r1 = read(),
			l2 = read(), r2 = read(),
			l3 = read(), r3 = read();
		suf[cnt] = r1 - l1 + r2 - l2 + r3 - l3 + 3;
		idx++, qrl[idx].l = l1, qrl[idx].r = r1, qrl[idx].id = cnt;
		idx++, qrl[idx].l = l2, qrl[idx].r = r2, qrl[idx].id = cnt;
		idx++, qrl[idx].l = l3, qrl[idx].r = r3, qrl[idx].id = cnt;
	}
	sort(qrl.begin() + 1, qrl.begin() + 1 + idx);
	Cpt::isl = 0;
	int l = 1, r = 0;
	for (int i = 1; i <= idx; i++) {
		int x = qrl[i].l, y = qrl[i].r;
		while (l > x) l--, Cpt::add(l);
		while (r < y) r++, Cpt::add(r);
		while (l < x) Cpt::del(l), l++;
		while (r > y) Cpt::del(r), r--;
		ans[qrl[i].id] &= Cpt::isl;
	}
	for (int i = 1; i <= cnt; i++)
		write(suf[i] - 3 * ans[i].count()), puts("");
}

int main() {
	int n = read(), m = read();
	for (int i = 1; i <= n; i++)
		s[i] = h[i] = read();
	sort(h.begin() + 1, h.begin() + 1 + n);
	for (int i = 1; i <= n; i++)
		s[i] = lower_bound(h.begin() + 1, h.begin() + 1 + n, s[i]) - h.begin();
	while (m)
		solve(m);
	return 0;
}