夏晓光(loveJY)的博客

Ynoi做的第二道题
感言:

有 $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$。

好的我们一开题就直接完蛋自闭了没有做过如此强大的套路弃疗了

正经的,我们需要对三个区间支持类似于数点去重的东西....而且还要支持1e5次询问

三维数点我只会bitset.....然而并没有想到啊

如果我们能有一个神奇的bitset把三个区间的信息记录下来然后&一下不就是得到要去掉的数的个数了吗?

而你又神奇的发现好像只需要一个莫队就能消掉区间的限制,而且bitset单点加入和查询O1!

然而问题又来了,bitset他现在还不够神奇,不能够记录重复了多少个...因为每个位置上的信息只有0/1

我们再想一下能不能莫队来帮助记录??因为我们总共的数字数是n大小的

那么参照之前BJOI那道题推倒的做法我们可以这样更改bitset记录方式

val[p]表示bitsetp位置的权值是什么,cnt[p]表示这个权值在原序列出现次数

每个位置p到$p-cnt[val[p]]$记录了这$cnt[p]$个数出现情况,也就是说出现第一次位置p是1,出现第二次把位置p-1置为1....第k次把p-k置为1

这样and起来就真的是要删掉的数个数了!

还有个问题,我们空间开不下啊

所以我们可以把1e5次询问分成3组,然后循环利用同一个ansbitset就行了,典型的以空间换时间

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<map>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
const int M = 34010;
#define ll long long
int a[MAXN], n, m, nans[MAXN], tp, tot, cnt[MAXN];
map<int, int> mp;
bitset<MAXN> ans[M], nb;
struct Qry {
	int l, r, t;
} q[M*3];
inline bool cmp1(const Qry &a, const Qry &b) {
	return a.l < b.l;
}
inline bool cmp2(const Qry &a, const Qry &b) {
	return a.r < b.r;
}
inline void ins(int p) {
	nb[p - cnt[p]] = 1;
	cnt[p]++;
}
inline void del(int p) {
	cnt[p]--;
	nb[p - cnt[p]] = 0;
}
inline void solve() {
	if(tot >= m)return ;
	for(int i = 1; i <= M - 10 && tot <= m; ++i, ++tot) {
		++tp;
		scanf("%d%d", &q[tp].l, &q[tp].r);
		q[tp].t = i; nans[i] += q[tp].r - q[tp].l + 1;
		++tp;
		scanf("%d%d", &q[tp].l, &q[tp].r);
		q[tp].t = i; nans[i] += q[tp].r - q[tp].l + 1;
		++tp;
		scanf("%d%d", &q[tp].l, &q[tp].r);
		q[tp].t = i; nans[i] += q[tp].r - q[tp].l + 1;
	}
	for(int i = 1; i <= tp / 3; ++i)ans[i].set();
	sort(q + 1, q + tp + 1, cmp1);
	int nl = 0, nr = 0;
	for(int i = 1; i <= tp; i += 320) {
		int r = min(tp, i + 319);
		sort(q + i, q + r + 1, cmp2);
		//分块的神仙排序法
	}
	for(int i = 1; i <= tp; ++i) {
		if(nr < q[i].l) {
			for(int j = nl; j <= nr; ++j)del(a[j]);
			nl = q[i].l; nr = q[i].r;
			for(int j = nl; j <= nr; ++j)ins(a[j]);
			//优化?
		} else {
			while(nl < q[i].l)del(a[nl]), ++nl;
			while(nl > q[i].l)--nl, ins(a[nl]);
			while(nr < q[i].r)nr++, ins(a[nr]);
			while(nr > q[i].r)del(a[nr]), nr--;
		}
		ans[q[i].t] &= nb;
	}
	for(int i = nl; i <= nr; ++i)del(a[i]);
	for(int i = 1; i <= tp / 3; ++i)printf("%lld\n", nans[i] - ans[i].count() * 3);
	for(int i = 1; i <= tp / 3; ++i)nans[i] = 0; tp = 0;
}
int main() {
	tot = 1;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i)mp[a[i]]++;
	map<int, int>::iterator it, it1;
	for(it = mp.begin(), it1 = it, ++it1; it1 != mp.end(); ++it, ++it1)it1->second += it->second;
	for(int i = n; i >= 1; --i)a[i] = mp[a[i]];
	solve();
	solve();
	solve();
	return 0;
}