P4867 Gty的妹子序列 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个查询 $(l,r,L,R)$.
对于每个查询，你需要求出 $\sum _{k=L}^R[k\in a_{l\cdots r}]$.

Limitations

$1\le n\le 10^5$
$1\le m\le 10^6$
$1\le a_i\le n$
$1\le l\le r\le n$
$1\le L\le R\le n$
$5\text{s},32\text{MB}$

Solution

空间限制很小，只能用莫队.
考虑 add 和 del，需要一个 ds 支持值域上单点加，区间和.
值域只有 $10^5$，显然可用 BIT 直接维护.
当然，为了根号平衡，还可用值域分块.
用 BIT 的时间复杂度为 $O(n\sqrt{m}\log n)$
用分块的时间复杂度为 $O(n\sqrt{m}+m\sqrt{n})$.
可能要调块长.

Code

$3.02\text{KB},3.01\text{s},24.55\text{MB}\text{(in total, C++20 with O2)}$
代码用的分块，但 fastio 删了.

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

// #define LOCAL
#ifdef LOCAL
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif

// fastio

int lowbit(int x){
	return x & -x;
}

// block
struct Block {
	int n, size, blocks;
	vector<int> a, s;
	inline Block() {}
	inline Block(int _n, int _size) : n(_n), size(_size) {
		blocks = (n + size - 1) / size;
		a.resize(n);
		s.resize(blocks);
	}
	
	inline int L(int x) { return size * x; }
	inline int R(int x) { return min(n, L(x) + size) - 1; }
	
	inline void add(int x, int v) { a[x] += v, s[x / size] += v; }
	inline int _ask(int l, int r) {
		int res = 0;
		for (int i = l; i <= r; i++) res += a[i];
		return res;
	}
	
	inline int ask(int l, int r) {
		const int bl = l / size, br = r / size;
		if (bl == br) return _ask(l, r);
		int res = _ask(l, R(bl)) + _ask(L(br), r);
		for (int i = bl + 1; i < br; i++) res += s[i];
		return res;
	}
};
struct Query { 
    int l, r, a, b, id;
    inline Query() {}
    inline Query(int _l, int _r, int _a, int _b, int _id) 
         : l(_l), r(_r), a(_a), b(_b), id(_id) {}
}; 

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	const int n = read<int>(), m = read<int>();
	vector<int> a(n);
	for (int i = 0; i < n; i++) a[i] = read<int>(), a[i]--;
	
	const int B = sqrt(n);
	vector<int> cnt(n);
	Block bit(n, B);
	
	auto add = [&](int x) {
		if (cnt[x]++ == 0) bit.add(x, 1);
	};
	auto del = [&](int x) {
		if (--cnt[x] == 0) bit.add(x, -1);
	};
	
	vector<Query> qry(m);
	for (int i = 0, l, r, a, b; i < m; i++) {
		scanf("%d %d %d %d", &l, &r, &a, &b);
		l--, r--, a--, b--;
		qry[i] = Query(l, r, a, b, i);
	}
	
	
	sort(qry.begin(), qry.end(), [&](const Query &a, const Query &b) {
        if (a.l / B == b.l / B) {
            return a.r < b.r;
        }
        return a.l / B < b.l / B;
    });
	
	vector<int> ans(m);
	int l = 0, r = -1;
	for (auto [ql, qr, qa, qb, id] : qry) {
		while (ql < l) add(a[--l]);
        while (r < qr) add(a[++r]);
        while (l < ql) del(a[l++]);
        while (qr < r) del(a[r--]);
        ans[id] = bit.ask(qa, qb);
	}
	
	for (int i = 0; i < m; i++) {
        write(ans[i]);
        putchar_unlocked('\n');
    }
	
	return 0;
}