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

DanielDingDang · 2025-11-03 20:01:21 · 题解

本题解中，重新定义 \text{mex} 为可重集中没有出现的最小的正整数。

一次询问等价于求出 \displaystyle\sum_{l=1}^n\sum_{r=l+1}^n f(l,r)。其中 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]。

简化 f 的计算过程

这部分直接分讨即可。

• 如果 [l,r] 中没有出现 1，f(l,r)=0。
• 如果 [l,r] 中出现了 1，设 x 为任意满足 x\in [l,r],a_x=1 的位置：
  • 若 a_l\neq 1，k 取 x-1 即可，f(l,r)=1。
  • 若 a_r\neq 1，k 取 x 即可，f(l,r)=1。
  • 若 a_l=a_r=1：
  • 如果 [l+1,r-1] 中出现了 2，则设 2 的位置为 p，k 取 p-1 即可，f(l,r)=1。
  • 如果 [l+1,r-1] 中没有出现 2，f(l,r)=0。

查询操作处理

注意到 f(l,r)=0 的情况数明显少于 f(l,r)=1 的情况数，考虑正难则反，维护 f(l,r)=0 的个数。

根据上述分类讨论，我们只需要处理两种情况。

• 如果 [l,r] 中没有出现 1，对于一个极长的不含有 1 的长度为 x 的连续子序列，其贡献显然为 \displaystyle\frac{1}{2}x(x+1)。
• 如果 [l,r] 中没有出现 2 且 a_l=a_r=1，则对于一个极长的不含有 2 的连续子序列，若其中有 x 个 1，其贡献显然为 \displaystyle \frac{1}{2}x(x+1)。

可以简单的用两个 set 分别维护 1,2 的出现位置。

代码写比较简洁。

#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;
}