专栏文章

莫队2+值域分块

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioii3gz
此快照首次捕获于
2025/12/02 19:45
3 个月前
此快照最后确认于
2025/12/02 19:45
3 个月前
查看原文

P3834 【模板】可持久化线段树 2

因为 ai≤109a_i \leq 10^9，但 n≤2×105n \leq 2 \times 10^5，因此对 aa 数组进行离散化。
将 aa copy 到 bb 中，记录 fx=aif_x = a_i，代表离散化后下标 xx 对应的是 aia_i，且将 aia_i 替换为其在 bb 中去重后的下标 xx。
令 cntxcnt_x 为离散化后的值 xx 在当前区间的出现次数，sumblsum_{bl} 为第 blbl 个块中所有元素的次数。
遍历每个块，用 sumsum 找到包含了第 kk 小元素的块，再枚举这个块，用 cntcnt 找到这个元素即可。
CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, num, len, ans[N], sum[N], cnt[N], a[N], b[N];
map<int, int> f;

struct query {
	int l, r, k, id;
} q[N];

bool cmp(query a, query b) {
	return (a.l / len == b.l / len ? a.r < b.r : a.l < b.l);
}

void add_sub(int x, int val) {
	int bl = x / num;
	cnt[x] += val;
	sum[bl] += val;
}

int rk(int k) {
	for (int i = 0; i <= num; i++) {
		if (k <= sum[i]) {
			for (int j = i * num; j <= (i + 1) * num; j++) {
				if (k <= cnt[j]) {
					return j;
				} else {
					k -= cnt[j];
				}
			}
		} else {
			k -= sum[i];
		}
	}
	return k + 1;
}

signed main() {
	cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> n >> m;
	len = sqrt(n);
	num = n / len + (n % len > 0);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort (b + 1, b + 1 + n);
	int length = unique(b + 1, b + 1 + n) - (b + 1);
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(b + 1, b + 1 + length, a[i]) - b;
		f[x] = a[i];
		a[i] = x;
	}
	for (int i = 1; i <= m; i++) {
		cin >> q[i].l >> q[i].r >> q[i].k;
		q[i].id = i;
	}
	sort (q + 1, q + 1 + m, cmp);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++) {
		while (l > q[i].l)
			add_sub(a[--l], 1);
		while (r < q[i].r)
			add_sub(a[++r], 1);
		while (l < q[i].l)
			add_sub(a[l++], -1);
		while (r > q[i].r)
			add_sub(a[r--], -1);
		ans[q[i].id] = f[rk(q[i].k)];
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << '\n';
	return 0;
}

P4137 Rmq Problem / mex

cnticnt_i 和 sumisum_i 跟上一题一样。
对于查询 mex，遍历所有块：
  • 若 sumi=sizisum_i = siz_i，则块满了。
  • 若 sumi<sizisum_i < siz_i，说明有一个没出现的数字，再根据 cntcnt 找。
注意判断所有块都满的情况，输出 Rnum+1R_{num} + 1。
CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, num, len, ans[N], cnt[N], siz[N], L[N], R[N], pos[N], a[N], sum[N];

struct query {
	int l, r, id;
} q[N];

bool cmp(query a, query b) {
	if (a.l / len != b.l / len) {
		return a.l < b.l; 
	}
	if (a.l / len % 2)
		return a.r > b.r;
	return a.r < b.r;
}

void init() {
	len = sqrt(2e5);
	num = 2e5 / len + (2e5 / len > 0);
	for (int i = 1; i <= num; i++) {
		L[i] = (i - 1) * len + 1;
		R[i] = i * len;
		siz[i] = len;
	}
	R[num] = 2e5;
	siz[num] = R[num] - L[num] + 1;
	L[1] = 0;
	siz[1]++;
	for (int i = 1; i <= num; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
		}
	}
}

void ADD(int x) {
	cnt[a[x]]++;
	(cnt[a[x]] == 1) && (sum[pos[a[x]]]++);
}

void SUB(int x) {
	cnt[a[x]]--;
	(cnt[a[x]] == 0) && (sum[pos[a[x]]]--);
}

int query() {
	for (int i = 1; i <= num; i++) {
		if (sum[i] == siz[i]) {
			continue;
		}
		for (int j = L[i]; j <= R[i]; j++) {
			if (cnt[j] == 0)
				return j;
		}
	}
	return R[num] + 1;
}

signed main() {
	cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	init();
	for (int i = 1; i <= m; i++) {
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort (q + 1, q + 1 + m, cmp);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++) {
		while (l > q[i].l)
			ADD(--l);
		while (r < q[i].r)
			ADD(++r);
		while (l < q[i].l)
			SUB(l++);
		while (r > q[i].r)
			SUB(r--);
		ans[q[i].id] = query();
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << '\n';
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...