题解：P15582 [KTSC 2026] 平衡序列 / Balanced Sequence

Redshift_Shine · 2026-03-04 19:12:02 · 题解

根据原定义，定义 k 阶平衡序列为长度为 2^k-1 的平衡序列。

显然，任何数都可以作为 1 阶平衡序列，其余第 i 阶平衡序列需要由 (i-1) 阶平衡序列拓展得到。

不难使用线段树判断区间最大值及其唯一性。并且，由于平衡序列的构建方法，可以发现覆盖任意特定单点的平衡序列个数为 \log 量级。

使用 set 维护每一阶平衡序列的中心位置，每次更新值时只更改可能覆盖该点的平衡序列，时间复杂度不难做到 O(n\log n+q\log^2 n)。

// #include <iostream>
#include <set>
#include <vector>
using namespace std;
const int N = 1e5 + 10, B = 17;
using ll = long long;
int n, a[N], rnk[N];
struct st
{
    int mx;
    bool only;
    st operator+(const st &x) const
    {
        if (mx == x.mx)
            return {mx, false};
        return mx > x.mx ? *this : x;
    }
};
st tr[N << 2];
ll res;
set<int> vld[B];
void build(int x = 1, int l = 0, int r = n - 1)
{
    if (l == r)
    {
        tr[x] = {a[l], true};
        rnk[l] = x;
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    tr[x] = tr[x << 1] + tr[x << 1 | 1];
}
st query(int lb, int rb, int x = 1, int l = 0, int r = n - 1)
{
    if (l >= lb and r <= rb)
        return tr[x];
    int mid = (l + r) >> 1;
    if (rb <= mid)
        return query(lb, rb, x << 1, l, mid);
    if (lb > mid)
        return query(lb, rb, x << 1 | 1, mid + 1, r);
    return query(lb, rb, x << 1, l, mid) + query(lb, rb, x << 1 | 1, mid + 1, r);
}
ll initialize(int N, vector<int> A)
{
    n = N;
    for (int i = 0; i < n; i++)
        a[i] = A[i], vld[0].emplace(i), res++;
    build();
    for (int i = 1, pv; (1 << (i + 1)) - 1 <= n; i++)
    {
        for (auto &j : vld[i - 1])
        {
            pv = j + (1 << (i - 1));
            if (pv + (1 << i) - 1 >= n)
                break;
            if (!vld[i - 1].count(pv + (1 << (i - 1))))
                continue;
            auto buf = query(pv - (1 << i) + 1, pv + (1 << i) - 1);
            if (!buf.only or a[pv] != buf.mx)
                continue;
            vld[i].emplace(pv);
            // cerr << i << ' ' << pv << '\n';
            res++;
        }
    }
    return res;
}
ll update_sequence(int p, int v)
{
    for (int i = 1; i < B; i++)
    {
        auto it = vld[i].upper_bound(p - (1 << i)), it2 = it;
        while (it2 != vld[i].end() and *it2 < p + (1 << i))
            it2++, res--;
        vld[i].erase(it, it2);
    }
    a[p] = v;
    tr[rnk[p]] = {v, true};
    for (int i = (rnk[p] >> 1); i; i >>= 1)
        tr[i] = tr[i << 1] + tr[i << 1 | 1];
    for (int i = 1, ivs, pv, ivs2; i < B; i++)
    {
        ivs = (1 << i) - 1 + (1 << (i - 1));
        ivs2 = (1 << (i - 1)) - 1;
        auto it = vld[i - 1].lower_bound(p - ivs);
        for (; it != vld[i - 1].end() and *it <= p + ivs2; it++)
        {
            pv = *it + (1 << (i - 1));
            if (pv + (1 << i) - 1 >= n)
                break;
            if (!vld[i - 1].count(pv + (1 << (i - 1))))
                continue;
            auto buf = query(pv - (1 << i) + 1, pv + (1 << i) - 1);
            if (!buf.only or a[pv] != buf.mx)
                continue;
            vld[i].emplace(pv);
            res++;
        }
    }
    return res;
}