很bt的一个题。

题目描述

您正在打 galgame，然后突然发现您今天太颓了，于是想写个数据结构题练练手：

一个长为 $n$ 的序列 $a$。

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

注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，比如三个区间是 $[1,2,2,3,3,3,3]$，$[1,2,2,3,3,3,3]$ 与 $[1,1,2,3,3]$，就一起扔掉了 $1$ 个 $1$，$1$ 个 $2$，$2$ 个 $3$。

输入格式

第一行两个整数表示 $n,m$。

第二行 $n$ 个整数表示 $a_i$。

之后 $m$ 行，每行 $6$ 个整数 $l_1,r_1,l_2,r_2,l_3,r_3$ 表示这三个区间。

输出格式

对于每个询问，输出一个整数表示答案。

样例 #1

样例输入 #1

5 2
1 2 2 3 3
1 2 2 3 3 4
1 5 1 5 1 5

样例输出 #1

3
0

---

区间查询，典型的莫队题。
首先对N个数进行离散化，这是莫队遍历的基础。
题目需要针对N个数进行三个区间的并集查询，这是第一个难点。
而后要查的不是三个区间是否都有数字存在，——我们知道bitset可以用来查并集数字是否存在，但是题目需要查询三个区间内每个数字个数的最小值。这里有一个奇技淫巧，首先离散化的时候要用multiset，也就是将$5,5,8,8,9$离散化成为$1,1,3,3,5$。然后存放x出现了cnt[x]次，就可以cnt[x]+x-1的那一位来存放。
举个例子来说，如果整个数组被离散化成为$1,1,3,3,3,6$，区间a里的数为$1,3,3,6$，而区间b里面的数为$1,1,3,3,3$，那么第一个bitset为$101101$（高位表示从1位开始），第二个bitset为$111110$，两者的交集即为$101100$，刚好是1个1和2个3。
大致思路就是这样，剩下是细节问题，包括：
1、在莫队遍历的时候要小心不要越界
2、由于需要开bitset数组，会爆内存，因此分几次来做，减少m值。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;const int N = 100010;
int a[N];
int ra[N];
int cnt[N];
struct Item {int l0, r0, l1, r1, l2, r2;
};
vector<Item> items;
bitset<N> cur;
int n, m;
struct Query {int l, r, b, i;
};
Query qu[70000];
bitset<N> bts[20005];void init() {multiset<int> st;map<int, int> h;int hid = 0;int t[N];for (int i = 1; i <= n; ++i) {cin >> t[i];st.insert(t[i]);}for (auto x : st) {hid++;ra[hid] = x;if (!h.count(x))h[x] = hid;}for (int i = 1; i <= n; ++i) {a[i] = h[t[i]];}
}void add(int x) {cur[cnt[x] + x] = 1;cnt[x] ++;
}void rem(int x) {cnt[x] --;cur[cnt[x] + x] = 0;
}void work(const vector<Item> &vec) {cur.reset();for (int i = 0; i < 20005; ++i)bts[i].set();memset(cnt, 0, sizeof(cnt));int blk = sqrt(n);int sz = vec.size();int qi = 0;for (auto [l0, r0, l1, r1, l2, r2] : vec) {qu[qi] = { l0, r0, l0 / blk, qi };qi++;qu[qi] = { l1, r1, l1 / blk, qi };qi++;qu[qi] = { l2, r2, l2 / blk, qi };qi++;}sort(qu, qu + qi, [&](Query x, Query y) {if (x.b == y.b)return x.b & 1 ? x.r > y.r : x.r < y.r;elsereturn x.b < y.b;});int L = 1, R = 0;for (int i = 0; i < qi; ++i) {auto [l, r, b, idx] = qu[i];while (R < r)add(a[++R]);while (L > l) add(a[--L]);while (R > r)rem(a[R--]);while (L < l)rem(a[L++]);bts[idx / 3] &= cur;}for (int i = 0; i < sz; ++i) {auto [l0, r0, l1, r1, l2, r2] = vec[i];int rm = bts[i].count();int tot = (r0 - l0 + 1 - rm) + (r1 - l1 + 1 - rm) + (r2 - l2 + 1 - rm);printf("%d\n", tot);}
}int main(){//freopen("in.txt", "r", stdin);scanf("%d%d", &n, &m);init();for (int i = 0; i < m; ++i) {int l0, r0, l1, r1, l2, r2;scanf("%d%d%d%d%d%d", &l0, &r0, &l1, &r1, &l2, &r2);items.push_back({ l0, r0, l1, r1, l2, r2 });}int SUB_NUM = 5;int sz = m / SUB_NUM;for (int i = 0, j = 0; j < SUB_NUM; ++ j, i += sz) {auto start = items.begin() + i, end = items.begin() + i + sz;if (j == SUB_NUM - 1)end = items.end();vector<Item> sub(start, end);work(sub);}return 0;
}