Luogu4688 [Ynoi2016]掉进兔子洞 【莫队,bitset】

题目链接：洛谷

我们知道要求的是\([l_1,r_1],[l_2,r_2],[l_3,r_3]\)的可重集取交的大小，肯定是要用bitset的，那怎么做可重集呢？

那就是要稍微动点手脚，首先在离散化的时候，将\(a_x\)设为\(\leq a_x\)的数的个数，然后再插入一个数的时候，将\(a_x-cnt_{a_x}\)设为1，删除的时候设为0，然后直接取交就可以了。正确性比较显然。

还有一个问题就是如何存下\(100000*100000\)的bitset，那肯定是存不下的，所以把询问分成3部分，然后每块分别做就可以用时间换空间了。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef long long LL;

const int N = 100010, M = 33340;

int n, m, _n, len, a[N], val[N], cnt[N], ql, qr, tmp[M];

bitset<N> ans[M], now;

struct Query {

	int l, r, id;

	inline bool operator < (const Query &o) const {

		if(l / len != o.l / len) return l / len < o.l / len;

		if(l / len & 1) return r > o.r;

		return r < o.r;

	}

} que[N];

inline void add(int x){++ cnt[x]; now[x - cnt[x]] = 1;}

inline void del(int x){now[x - cnt[x]] = 0; -- cnt[x];}

inline void solve(int m){

	for(Rint i = 1;i <= n;i ++) cnt[i] = 0;

	for(Rint i = 1;i <= m;i ++) ans[i].set(), tmp[i] = 0; now.reset(); ql = 1; qr = 0;

	for(Rint i = 1;i <= 3 * m;i ++) scanf("%d%d", &que[i].l, &que[i].r), tmp[que[i].id = (i + 2) / 3] += que[i].r - que[i].l + 1;

	sort(que + 1, que + 3 * m + 1);

	for(Rint i = 1;i <= 3 * m;i ++){

		while(ql > que[i].l) add(a[-- ql]);

		while(qr < que[i].r) add(a[++ qr]);

		while(qr > que[i].r) del(a[qr --]);

		while(ql < que[i].l) del(a[ql ++]);

		ans[que[i].id] &= now;

	}

	for(Rint i = 1;i <= m;i ++) printf("%d\n", tmp[i] - 3 * ans[i].count());

}

int main(){

	scanf("%d%d", &n, &m); len = sqrt(n);

	for(Rint i = 1;i <= n;i ++) scanf("%d", a + i), val[i] = a[i];

	sort(val + 1, val + n + 1);

	_n = unique(val + 1, val + n + 1) - val - 1;

	for(Rint i = 1;i <= n;i ++) a[i] = lower_bound(val + 1, val + _n + 1, a[i]) - val;

	for(Rint i = 1;i <= _n;i ++) val[i] = 0;

	for(Rint i = 1;i <= n;i ++) ++ val[a[i]];

	for(Rint i = 1;i <= _n;i ++) val[i] += val[i - 1];

	for(Rint i = 1;i <= n;i ++) a[i] = val[a[i]];

	solve(m / 3); solve((m + 1) / 3); solve((m + 2) / 3);

}