Luogu P4688 掉进兔子洞

题意

给定一个长度为 \(n\) 的序列 \(a\)。

有 \(m\) 次询问：每次询问给定三个区间，问将三个区间内同时出现的数删掉后，还剩下多少个数。每次询问独立。

数据范围与约定

\(1 \le n,m \le 10^5\)，\(1 \le a_i \le 10^9\)。

题解

首先发现，每次询问的答案形式为：\(ans_i=len_1+len_2+len_3-3*size\)，其中 \(size\) 为三个区间内同时出现的颜色的个数。

所以只要我们有办法求出 \(size\) 就能解决这道题。很自然的想到 bitset 维护区间内出现的颜色，求一下交集。但是我们要求的是同时出现的颜色个数，而不是颜色种数。bitset 只能记录一个颜色存在或者不存在，不能记录存在多少个。如果换成数组，又没有了除 \(w\) 的常数。

我们可以在离散化上下手，令一个颜色离散化后的值为：序列中，小于这个数的个数加 \(1\)（不加 \(1\) 也行，随便你）。其实就是离散化把去重给去掉而已。

这样有一个好处，我们假设当前颜色为 \(c_1\)，下一个颜色为 \(c_2\)。那么 \(c_2-c_1\) 就是 \(c_1\) 的个数。所以如果颜色 \(c_1\) 出现了 \(cnt\) 次。我们可以在 bitset 上令 \(c_1+cnt-1\) 为 \(1\)。这里需要注意一下，我们不应该把 \(c_1+(cnt-1)-1\) 再置为 \(0\)，而是将其保留。这样有一个好处，\(c_1\) 和 \(c_2\) 之间 \(1\) 的个数，就是 \(c_1\) 出现的次数。那么最后三个区间交集的 bitset 的 \(1\) 的个数，就是我们要求的 \(size\)。

最后一个问题，怎么求每个区间的 bitset？考虑到这个 bitset 因为我们离散化比较特殊的原因，没办法通过区间合并来快速得到，所以不能使用分块或者线段树之类的数据结构了。所以我们考虑使用莫队。

这里有一个问题，我们开不下 \(1e5\) 个长度为 \(1e5\) 的 bitset。我们可以对问题分组，每 \(4e4\) 个问题跑一次莫队，这样我们只需要跑 \(\left\lceil \frac{1e5}{4e4} \right\rceil=3\) 次莫队即可。

代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int S1 = 4e4;//对询问分组
const int S2 = 350;//对莫队分组
/*====================*/
int n, m;
int arr[N];
/*====================*/
struct Query
{
	int l, r, idx;
	Query(int _l = 0, int _r = 0, int _idx = 0)
	{
		l = _l, r = _r, idx = _idx;
	}
	friend bool operator<(const Query& a, const Query& b)
	{
		return (a.l / S2 == b.l / S2) ? (((a.l / S2) & 1) ? (a.r > b.r) : (a.r < b.r)) : (a.l < b.l);
	}
}query[3 * M];
/*====================*/
int ans[M];
/*====================*/
int cnt[N];
bitset<N>temp;
bitset<N>state[S1];
void Add(int pos)
{
	temp[arr[pos] + ++cnt[arr[pos]] - 1] = 1;
}
void Del(int pos)
{
	temp[arr[pos] + cnt[arr[pos]]-- - 1] = 0;
}
void Mo(int idxl, int idxr)
{
	int askl = (idxl - 1) * 3 + 1;
	int askr = (idxr - 1) * 3 + 3;
	sort(query + askl, query + askr + 1);
	/*====================*/
	temp.reset();
	for (int i = idxl; i <= idxr; ++i)
	{
		state[i % S1].set();
	}
	memset(cnt, 0, sizeof(cnt));
	/*====================*/
	int l = 1, r = 0;
	for (int i = askl; i <= askr; ++i)
	{
		while (query[i].l < l)Add(--l);
		while (r < query[i].r)Add(++r);
		while (l < query[i].l)Del(l++);
		while (query[i].r < r)Del(r--);
		state[query[i].idx % S1] &= temp;
	}
	/*====================*/
	for (int i = idxl; i <= idxr; ++i)
	{
		ans[i] -= 3 * state[i % S1].count();
	}
}
/*====================*/
void Solve(void)
{
	do
	{
		cin >> n >> m;
		for (int i = 1; i <= n; ++i)
		{
			cin >> arr[i];
		}
	} while (false);//读入

	do
	{
		vector<int>lib;
		for (int i = 1; i <= n; ++i)
		{
			lib.push_back(arr[i]);
		}
		sort(lib.begin(), lib.end());
		for (int i = 1; i <= n; ++i)
		{
			arr[i] = lower_bound(lib.begin(), lib.end(), arr[i]) - lib.begin() + 1;
		}
	} while (false);//离散化

	do
	{
		int idxl = 1, idxr = S1; idxr = min(idxr, m);
		while (idxl <= idxr)
		{
			for (int i = idxl; i <= idxr; ++i)
			{
				for (int j = 1; j <= 3; ++j)
				{
					int l, r; cin >> l >> r;
					query[(i - 1) * 3 + j] = Query(l, r, i);
					ans[i] += r - l + 1;
				}
			}
			Mo(idxl, idxr);
			idxl += S1, idxr += S1; idxr = min(idxr, m);
		}

	} while (false);//莫队

	do
	{
		for (int i = 1; i <= m; ++i)
		{
			cout << ans[i] << endl;
		}
	} while (false);//输出
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}