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;
}