第一道 Ynoi /se

做法

这道题看起来就像不能用数据结构维护的样子。

考虑 bitset 乱搞。

发现答案为 $|A|+|B|+|C|-3\times |A\cap B\cap C|$。

其中 $|A|+|B|+|C|$ 很容易知道，考虑如何维护 $|A\cap B\cap C|$。

首先要对数字进行离散化。

但……普通的离散化后的值似乎无法维护。

改一下离散化，令 $x$ 离散化后的值为 $\sum_{i=1}^n [a_i\le x]$。（其中 $[表达式]$ 为当表达式成立时返回值是 $1$，不成立则为 $0$）。

那么，设离散化后有两个数 $x,y$，满足 $x<y$，则 $y-x$ 为 $>x$ 且 $\le y$ 的数的个数。

假设有一个区间，要加入一个数 $x$，设其在区间中出现的次数为 $cnt_x$，则可以把 bitset 的第 $x-cnt_x$ 位改为 $1$。显然这个 $x-cnt_x$ 不会与其它数重合。

再看题目，不需要修改，这就不是莫队么！

所以最终我们的解法就是 bitset+莫队 了。

不过注意，我们开不下 $10^5 \times 10^5$。

其实只要分三次计算就好啦 qwq。

代码

马蜂较烂，建议格式化后食用。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
	while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
	return x * f;
}
const int N = 1e5 + 5, M = 34000;
struct Que {
	int l, r, num;
} q[M * 3 + 5];
struct Node {
	int data, num;
	inline bool operator < (const Node &x) const {
		return data < x.data;
	}
} h[N];
bitset <N> ans[M + 5], w;
int n, m, tot;
int a[N], cnt[N], sum[M + 5];
unordered_map <int, int> b;
inline bool cmp1(Que c, Que d) {
	return c.l < d.l;
}
inline bool cmp2(Que c, Que d) {
	return c.r > d.r;
}
inline void add(int x) {
	w[x - cnt[x]] = 1; cnt[x]++;
}
inline void del(int x) {
	cnt[x]--; w[x - cnt[x]] = 0;
}
inline void solve() {
	if (tot >= m) return;
	int num = 0;
	for (int i = 1; i <= M && tot < m; i++) {
		++tot; sum[i] = 0;
		q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1;
		q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1;
		q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1;
	}
	for (int i = 1; i <= num / 3; i++) ans[i].set();
	int step = sqrt(num);
	sort(q + 1, q + num + 1, cmp1);
	for (int i = 1; i <= num; i += step) {
		int l = i, r = min(i + step - 1, num);
		sort(q + l, q + r + 1, cmp2);
	}
	int L = 1, R = 0;
	for (int i = 1; i <= num; i++) {
		if (R < q[i].l || L > q[i].r) {
			for (int j = L; j <= R; j++) del(a[j]);
			L = q[i].l; R = q[i].r;
			for (int j = L; j <= R; j++) add(a[j]);
		}
		else {
			while (R < q[i].r) add(a[++R]);
			while (R > q[i].r) del(a[R--]);
			while (L < q[i].l) del(a[L++]);
			while (L > q[i].l) add(a[--L]);
		}
		ans[q[i].num] &= w;
	}
	for (int i = L; i <= R; i++) del(a[i]);
	for (int i = 1; i <= num / 3; i++) printf("%d\n", sum[i] - 3 * ans[i].count());
}
int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		h[i].data = read();
		b[h[i].data]++;
		h[i].num = i;
	}
	sort(h + 1, h + n + 1);
	int pre = 0, s = 0;
	for (int i = 1; i <= n; i++) {
		if (h[i].data == pre) a[h[i].num] = s;
		else {
			s += b[h[i].data];
			pre = h[i].data;
			a[h[i].num] = s;
		}
	}
	solve(); solve(); solve();
	return 0;
}