BZOJ4939[Ynoi2016]掉进兔子洞（莫队+bitset）
題目鏈接
BZOJ
洛谷
扯點別的
聽說這是比較親民的一道Ynoi，于是我就去摸了一下，于是一個晚上就沒了……不過至少還是學到了\(bitset\)維護可重集合的方法，以及當空間開不下時分組處理詢問的花操作……
解析
大佬們說容易想到bitset，那就想到bitset吧……
這種形如“幾個集合共同含有的元素”的問題容易讓人想\(bitset\)搞一搞，但是我們發現裸的\(bitset\)只能表示有沒有，不能表示有多少，下面就是神奇的讓\(bitset\)能表示有多少的方法
就這道題而言首先肯定是離散化，但是離散化時我們不去重，這樣相同元素會是連續的一段，我們取第一個出現的位置作為離散化后的值，簡單舉個例子：1,4,2,4,4,5 => hash[1] = 0,hash[2] = 1,hash[4] = 2,hash[5] = 5
假設我們要加入一個數\(x\)，它之前已經在這個集合中出現了\(cnt\)次，那么我們把\(x + cnt\)那一位置為\(1\)，刪除同理，即：bitset中第\(i + j\)個位置表示數字\(i\)第\(j + 1\)次出現
這樣當我們把每個\(bitset\)與起來就相當于對每個數的出現次數取了個\(min\)
回到題目，假設我們知道了三個區間的\(bitset\)與起來是\(S\)，那么答案顯然就是\(len1 + len2 + len3 - |S| \times 3\)
我們發現\(bitset\)加入和刪除都能很快處理，詢問的又是區間，那么就可以上莫隊試試了，莫隊的時候維護一下每個數出現的次數即可
還有一點，直接開\(1e5\)個\(bitset\)肯定開不下，于是我們把詢問分組，每組上一次莫隊即可
分組大小可以算算，我比較懶就從\(1e4\)開始試然后到\(3e4\)的時候就過了……
代碼
#include <cstdio> #include <cstring> #include <iostream> #include <bitset> #include <algorithm> #define MAXN 100003 #define belong(x) ((x) / per_block)typedef long long LL; struct Query {int l, r, id; } qry[90005]; int arr[MAXN], hash[MAXN], cnt[MAXN], N, M, per_block, idx; std::bitset<MAXN> cur, ans[30003]; bool vis[30003];bool operator <(const Query &q1, const Query &q2) {return belong(q1.l) == belong(q2.l) ? q1.r < q2.r : belong(q1.l) < belong(q2.l); } bool cmp(const Query &q1, const Query &q2) { return q1.id < q2.id; }int main() {scanf("%d%d", &N, &M);for (int i = 0; i < N; ++i) scanf("%d", arr + i), hash[i] = arr[i];std::sort(hash, hash + N);for (int i = 0; i < N; ++i)arr[i] = std::lower_bound(hash, hash + N, arr[i]) - hash;while (per_block * per_block < N) ++per_block;while (M) {memset(cnt, 0, sizeof cnt);memset(vis, 0, sizeof vis);cur.reset();int tot = std::min(30000, M);for (int k = 0; k < tot * 3; ++k) scanf("%d%d", &qry[k].l, &qry[k].r), qry[k].id = k / 3;std::sort(qry, qry + tot * 3);for (int l = 0, r = -1, i = 0; i < tot * 3; ++i) {--qry[i].l, --qry[i].r;while (r < qry[i].r) ++r, cur[arr[r] + cnt[arr[r]]] = 1, ++cnt[arr[r]];while (r > qry[i].r) --cnt[arr[r]], cur[arr[r] + cnt[arr[r]]] = 0, --r;while (l < qry[i].l) --cnt[arr[l]], cur[arr[l] + cnt[arr[l]]] = 0, ++l;while (l > qry[i].l) --l, cur[arr[l] + cnt[arr[l]]] = 1, ++cnt[arr[l]];if (!vis[qry[i].id]) vis[qry[i].id] = 1, ans[qry[i].id] = cur;else ans[qry[i].id] &= cur;}std::sort(qry, qry + tot * 3, cmp);for (int i = 0; i < tot; ++i) {int p1 = i * 3, p2 = p1 + 1, p3 = p2 + 1;printf("%d\n", qry[p1].r - qry[p1].l + qry[p2].r - qry[p2].l + qry[p3].r - qry[p3].l + 3 - (int)ans[i].count() * 3);}M -= tot;}return 0; } //Rhein_E轉載于:https://www.cnblogs.com/Rhein-E/p/10506971.html
總結
以上是生活随笔為你收集整理的BZOJ4939[Ynoi2016]掉进兔子洞（莫队+bitset）的全部內容，希望文章能夠幫你解決所遇到的問題。
