专栏文章

带修莫队+值域分块

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

文章操作

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

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

带修莫队

初始化

在 qq 数组里记录 $(l,r,k)，分别为每次查询的左边界，右边界与时间戳。
在 MM 数组里记录 (pos,val)(pos,val)，分别为每次修改操作的下标与值。
CPP
while (t--) {
  char c;
  cin >> c;
  if (c == 'Q') {
    ++cnt_q;
    cin >> q[cnt_q].l >> q[cnt_q].r;
    q[cnt_q].t = cnt_r;
    q[cnt_q].id = cnt_q;
  } else {
    ++cnt_r;
    cin >> M[cnt_r].pos >> M[cnt_r].val;
  }
}

修改与查询

我们需要同时进行查询与修改操作。
先进行普通的查询操作。
接着，当当前时间 <qi < q_i 的时间戳时，证明我们需要修改从当前时间到 qiq_i 的时间戳的操作。当当前时间 >qi> q_i 的时间戳时，证明我们需要修改回来过多修改的操作。
CPP
int l = 1, r = 0, t = 0;
for (int i = 1; i <= cnt_q; i++) {
  while (l < q[i].l)
    SUB(a[l++]);
  while (l > q[i].l)
    ADD(a[--l]);
  while (r < q[i].r)
    ADD(a[++r]);
  while (r > q[i].r)
    SUB(a[r--]);
  while (t < q[i].t) 
    modify(i, ++t);
  while (t > q[i].t)
    modify(i, t--);
  ans[q[i].id] = tot;
}

修改

直接修改值，最后 swap 一下，方便下次修改回来。
CPP
void modify(int x, int t) {
	if (M[t].pos >= q[x].l && M[t].pos <= q[x].r) {
		SUB(a[M[t].pos]);
		ADD(M[t].val);
	}
	swap(a[M[t].pos], M[t].val);
}

P1903 [国家集训队] 数颜色 / 维护队列

CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, t, tot, a[N], b[N], cnt[N * 10], pos[N], ans[N]; 

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

struct MODIFY {
	int pos, val;
} M[N];

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

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

bool cmp(Query a, Query b) {
	if (pos[a.l] != pos[b.l]) {
		return a.l < b.l;
	}
	if (pos[a.r] != pos[b.r]) {
		return a.r < b.r;
	}
	return a.t < b.t;
}

void modify(int x, int t) {
	if (M[t].pos >= q[x].l && M[t].pos <= q[x].r) {
		SUB(a[M[t].pos]);
		ADD(M[t].val);
	}
	swap(a[M[t].pos], M[t].val);
}

signed main() {
	cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> n >> t;
	int len = int(pow(n, 2.0 / 3.0));
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[i] = (i - 1) / len + 1;
	}
	int cnt_r = 0, cnt_q = 0;
	while (t--) {
		char c;
		cin >> c;
		if (c == 'Q') {
			++cnt_q;
			cin >> q[cnt_q].l >> q[cnt_q].r;
			q[cnt_q].t = cnt_r;
			q[cnt_q].id = cnt_q;
		} else {
			++cnt_r;
			cin >> M[cnt_r].pos >> M[cnt_r].val;
		}
	}
	sort (q + 1, q + 1 + cnt_q, cmp);
	int l = 1, r = 0, t = 0;
	for (int i = 1; i <= cnt_q; i++) {
		while (l < q[i].l)
			SUB(a[l++]);
		while (l > q[i].l)
			ADD(a[--l]);
		while (r < q[i].r)
			ADD(a[++r]);
		while (r > q[i].r)
			SUB(a[r--]);
		while (t < q[i].t) 
			modify(i, ++t);
		while (t > q[i].t)
			modify(i, t--);
		ans[q[i].id] = tot;
	}
	for (int i = 1; i <= cnt_q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

CF940F Machine Learning

数字过大，先离散化。
对于求出现次数的 mex，我们在修改完后暴力求就可以了。
CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, t, tot, a[N], b[N], cnt[N], pos[N], ans[N], sum[N], idx;

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

struct MODIFY {
	int pos, val;
} M[N];

void ADD(int x) {
	sum[cnt[x]]--, cnt[x]++, sum[cnt[x]]++;
}

void SUB(int x) {
	sum[cnt[x]]--, cnt[x]--, sum[cnt[x]]++;
}

bool cmp(Query a, Query b) {
	if (pos[a.l] != pos[b.l]) {
		return a.l < b.l;
	}
	if (pos[a.r] != pos[b.r]) {
		return a.r < b.r;
	}
	return a.t < b.t;
}

void modify(int x, int t) {
	if (M[t].pos >= q[x].l && M[t].pos <= q[x].r) {
		SUB(a[M[t].pos]);
		ADD(M[t].val);
	}
	swap(a[M[t].pos], M[t].val);
}

signed main() {
	cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> n >> t;
	int len = int(pow(n, 2.0 / 3.0));
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[++idx] = a[i];
		pos[i] = (i - 1) / len + 1;
	}
	int cnt_r = 0, cnt_q = 0;
	while (t--) {
		int op;
		cin >> op;
		if (op == 1) {
			++cnt_q;
			cin >> q[cnt_q].l >> q[cnt_q].r;
			q[cnt_q].t = cnt_r;
			q[cnt_q].id = cnt_q;
		} else {
			++cnt_r;
			cin >> M[cnt_r].pos >> M[cnt_r].val;
			b[++idx] = M[cnt_r].val;
		}
	}
	sort (b + 1, b + 1 + idx);
	int length = unique(b + 1, b + 1 + idx) - (b + 1);
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(b + 1, b + 1 + length, a[i]) - b;
		a[i] = x;
	}
	for (int i = 1; i <= cnt_r; i++) {
		int x = lower_bound(b + 1, b + 1 + length, M[i].val) - b;
		M[i].val = x;
	}
	sort (q + 1, q + 1 + cnt_q, cmp);
	int l = 1, r = 0, t = 0;
	for (int i = 1; i <= cnt_q; i++) {
		while (l < q[i].l)
			SUB(a[l++]);
		while (l > q[i].l)
			ADD(a[--l]);
		while (r < q[i].r)
			ADD(a[++r]);
		while (r > q[i].r)
			SUB(a[r--]);
		while (t < q[i].t)
			modify(i, ++t);
		while (t > q[i].t)
			modify(i, t--);
		int tmp = 1;
		while (sum[tmp])
			tmp++;
		ans[q[i].id] = tmp;
	}
	for (int i = 1; i <= cnt_q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

评论

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

正在加载评论...