题解

Difficulty：6.5 / Medium

Tag：莫队，bitset

---

查询三个区间，看似需要维护 $6$ 个坐标，$O(n^{\frac{11}{6}})$。实则不然。

我们可以将三个区间拆开来处理，变成 $3m$ 个询问。

但是这个时候询问顺序就打乱了，同一次询问的区间在不同的时间出现，怎么得到答案呢？

答案是通过 bitset 暴力记录下当前的信息，然后将同一次询问的信息按位与即可。

这样就做到了 $O(\frac{nm}{w}+m\sqrt m)$ 了。

但空间也是 $O(\frac{nm}{w})$ 开不下啊。

可以将查询分成 $k$ 组处理，只需要保证 $O(\frac{nm}{kw})$ 能开的下就行。这时时间复杂度就是 $O(\frac{nm}{w}+m\sqrt{mk})$ 了。挺宽松的，不需要卡常。

#include <bits/stdc++.h>
// O(knsqrt(m/k))=O(nsqrt(mk))
// 300000*100000/64
// 应该不会占太多时间，那我乱搞长度了（ 
const int N = 100000, M = 25000, B2 = 375;
struct node{
	int l, r, id;
	bool operator < (const node &b) const{
		if(l / B2 == b.l / B2){
			if((l / B2) & 1) return r < b.r;
			else return r > b.r;
		}
		return l / B2 < b.l / B2;
	}
}q[M * 3 + 5];
namespace DS{
	int idx[N + 5];
	std::bitset <N + 5> ans;
	void add(int val){
		ans.set(idx[val]++);
	}
	void del(int val){
		ans.reset(--idx[val]);
	}
}
std::bitset <N + 5> bits[M + 5];
int ans[M + 5];
int a[N + 5], b[N + 5];
int bucket[N + 5];
int n, m;
int read(){
	int x = 0;
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}
void solve(int m){
	for(int i = 1; i <= m; i++){
		bits[i].set();
		ans[i] = 0;
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= 3; j++){
			int idx = 3 * (i - 1) + j;
			q[idx].l = read(), q[idx].r = read();
			q[idx].id = i;
		}
	}
	std::sort(q + 1, q + m * 3 + 1);
	int l = 1, r = 0;
	for(int i = 1; i <= m * 3; i++){
		ans[q[i].id] += q[i].r - q[i].l + 1;
		while(l > q[i].l) DS::add(a[--l]);
		while(r < q[i].r) DS::add(a[++r]);
		while(l < q[i].l) DS::del(a[l++]);
		while(r > q[i].r) DS::del(a[r--]);
		bits[q[i].id] &= DS::ans;
	}
	while(l > 1) DS::add(a[--l]);
	while(r > 0) DS::del(a[r--]);
	for(int i = 1; i <= m; i++){
		std::cout << ans[i] - bits[i].count() * 3 << '\n';
	}
}
int main(){
	std::cout.tie(0) -> sync_with_stdio(0);
	n = read(), m = read();
	for(int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
	std::sort(b + 1, b + n + 1);
	std::unique(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++){
		a[i] = std::lower_bound(b + 1, b + n + 1, a[i]) - b;
		bucket[a[i]]++;
	}
	for(int i = 1; i <= n; i++){
		DS::idx[i] = DS::idx[i - 1] + bucket[i - 1];
	}
	while(m >= M){
		solve(M);
		m -= M;
	}
	if(m) solve(m);
	
	return 0;
}