专栏文章

题解：P14379 【MX-S9-T2】「LAOI-16」摩天大楼

DDanielDingDang
P14379题解参与者 2已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@mine3ypx
此快照首次捕获于
2025/12/02 00:55
3 个月前
此快照最后确认于
2025/12/02 00:55
3 个月前
查看原文
本题解中，重新定义 mex\text{mex} 为可重集中没有出现的最小的正整数。
一次询问等价于求出 ∑l=1n∑r=l+1nf(l,r)\displaystyle\sum_{l=1}^n\sum_{r=l+1}^n f(l,r)。其中 f(l,r)=[∃k∈[l,r)∩Z,mexi=lk≠mexi=k+1r]f(l,r)=\left[\exists k\in [l,r)\cap\mathbb{Z},\text{mex}_{i=l}^k\neq \text{mex}_{i=k+1}^r\right]。

简化 ff 的计算过程

这部分直接分讨即可。
  • 如果 [l,r][l,r] 中没有出现 11，f(l,r)=0f(l,r)=0。
  • 如果 [l,r][l,r] 中出现了 11，设 xx 为任意满足 x∈[l,r],ax=1x\in [l,r],a_x=1 的位置：
    • 若 al≠1a_l\neq 1，kk 取 x−1x-1 即可，f(l,r)=1f(l,r)=1。
    • 若 ar≠1a_r\neq 1，kk 取 xx 即可，f(l,r)=1f(l,r)=1。
    • 若 al=ar=1a_l=a_r=1：
      • 如果 [l+1,r−1][l+1,r-1] 中出现了 22，则设 22 的位置为 pp，kk 取 p−1p-1 即可，f(l,r)=1f(l,r)=1。
      • 如果 [l+1,r−1][l+1,r-1] 中没有出现 22，f(l,r)=0f(l,r)=0。

查询操作处理

注意到 f(l,r)=0f(l,r)=0 的情况数明显少于 f(l,r)=1f(l,r)=1 的情况数，考虑正难则反，维护 f(l,r)=0f(l,r)=0 的个数。
根据上述分类讨论，我们只需要处理两种情况。
  • 如果 [l,r][l,r] 中没有出现 11，对于一个极长的不含有 11 的长度为 xx 的连续子序列，其贡献显然为 12x(x+1)\displaystyle\frac{1}{2}x(x+1)。
  • 如果 [l,r][l,r] 中没有出现 22 且 al=ar=1a_l=a_r=1，则对于一个极长的不含有 22 的连续子序列，若其中有 xx 个 11，其贡献显然为 12x(x+1)\displaystyle \frac{1}{2}x(x+1)。
可以简单的用两个 set 分别维护 1,21,2 的出现位置。
代码写比较简洁。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1000010;

int n, tr[N], T, a[N], res;
set<int> s[3];

int lb(int x) { return x & -x; }
void upd(int x, int d) { for (; x < N; x += lb(x)) tr[x] += d; }
int q(int x) { int res = 0; for (; x; x -= lb(x)) res += tr[x]; return res; }

int C(int x) { return x * (x - 1) / 2; }
int g(int l, int r, int op) {
	if (op == 1) return r - l - 1;
	return q(r) - q(l);
}

void upd(int x, int d, int num) {
	if (num == 1) {
		auto itr = s[2].lower_bound(x), itl = prev(itr);
		res -= C(q(*itr) - q(*itl)); upd(x, d);
		res += C(q(*itr) - q(*itl));
	}
	if (d == 1) s[num].insert(x);
	auto it = s[num].find(x), itl = prev(it), itr = next(it);
	res += d * C(g(*itl, *it, num)) + d * C(g(*it, *itr, num));
	res -= d * C(g(*itl, *itr, num));
	if (d == -1) s[num].erase(x);
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> T;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	for (int i = 1; i <= n; i ++ )
		if (a[i] == 1) s[1].insert(i), upd(i, 1);
		else if (a[i] == 2) s[2].insert(i);
	for (int i = 1; i < 3; i ++ )
		s[i].insert(0), s[i].insert(n + 1);
	for (int num = 1, lst = 0; num < 3; num ++ , lst = 0)
		for (int v : s[num])
			if (v) res += C(g(lst, v, num)), lst = v;
	while (T -- )
	{
		int x, d;
		cin >> x >> d;
		if (a[x] == d) { cout << C(n) - res << "\n"; continue; }
		if (a[x] <= 2) upd(x, -1, a[x]);
		if (d <= 2) upd(x, 1, d);
		cout << C(n) - res << "\n", a[x] = d;
	}
	return 0;
}

评论

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

正在加载评论...