题意
给定长度为 \(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;
}