题解：P17723 [SCP-S 2026] 函数 / func

sqtzl · 2026-10-20 15:36:14 · 题解

看题解区都是双指针做法，于是我特此写了一篇线段树做法的题解，先别急着质疑时间复杂度，往下看。

解题思路

我们可以通过枚举右端点 + 按位计算贡献的方式求解。对于每个右端点 r，考虑二进制第 k 位：记所有使得 f(l,r) 的第 k 位为 1 的左端点 l 的数量为 L，则最终答案为：

ans = \sum_{r=1}^{n}\sum_{k=0} L \times 2^k

先说结论，所有能让 f(l,r) 的第 k 位为 1 的左端点 l 一定构成一个前缀（即 1,2,\dots,L 都满足条件）。因此 L 等于最大的满足条件的 l 的下标。

证明

记 S(l,r) = \{a_l,a_{l+1},\dots,a_r\}，那么

根据按位或的单调性：若 \operatorname{OR}(S(L,r)) 的第 k 位为 1，则对所有 l \le L，\operatorname{OR}(S(l,r)) 的第 k 位一定为 1。区间越长，按位或的结果不会变小。
根据 MEX 的定义：若 \operatorname{MEX}(S(L,r)) 的第 k 位为 1，则对所有 l \le L，\operatorname { MEX } (S(l,r)) 的第 k 位为 1 或 \operatorname{OR}(S(l,r)) 的第 k 位为 1。原因：当 \operatorname{ MEX }(S(l,r)) \ne \operatorname{MEX}(S(L,r)) 时，说明原本的 \operatorname{MEX}(S(L,r)) 已经出现在了更长的区间 S(l,r) 中，此时 \operatorname{OR}(S(l,r)) 的第 k 位必然为 1。

综上，当 f(L,r) 的第 k 位为 1 时，所有 l\le L 的 f(l,r) 的第 k 位也为 1。

贡献计算

定义：

那么，

结合“只要其中一个条件满足，第 k 位就为 1”的性质，最大的合法左端点为：

L = \max\left(R_k,\ \min_{0 \le x < 2^k} lst_x\right)

实现

由于 n \le 2 \times 10^6，因此 \operatorname{MEX}(S(l,r)) \le 2 \times 10^6。所以我们只需要用线段树维护 x \in [0, 2\times 10^6] 上 lst_x 的区间最小值即可。

优化

普通线段树的单次区间查询复杂度为 O(\log n)，总时间复杂度会达到 O(n \log n \log V)。

但我们可以观察到：每次查询的区间恰好是 [0, 2^k - 1]，这正好对应线段树上某一个完整的节点区间。因此我们可以在建树时预处理每个 [0,2^k-1] 对应的线段树节点编号，查询时直接取出该节点的最小值，这样就无需递归遍历，将单轮查询优化到 O(1)。

参考代码

#include <bits/stdc++.h>
using namespace std;

#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((tl + tr) >> 1)
#define Max(a, b) ((a) = max((a), (b)))

using i32 = int;
using u64 = unsigned long long;

const i32 N = 2e6 + 5;
const i32 INF = 1e9;
const i32 SEG = 1048575; // 对应 2^20 - 1，线段树值域右端点

i32 n, x;
i32 R[31];
i32 id[N];
u64 ans;
i32 mi[N << 2];

void build(i32 tl, i32 tr, i32 i) {
    if (tl == 0) id[tr] = i;
    if (tl == tr) return;
    build(tl, mid, ls);
    build(mid + 1, tr, rs);
}

void upd(i32 tl, i32 tr, i32 pos, i32 val, i32 i) {
    if (tl == tr) {
        mi[i] = val;
        return;
    }
    if (pos <= mid) upd(tl, mid, pos, val, ls);
    else upd(mid + 1, tr, pos, val, rs);
    mi[i] = min(mi[ls], mi[rs]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    i32 MAXN = 0;
    build(0, SEG, 1);

    cin >> n;
    for (i32 j = 1; j <= n; ++j) {
        cin >> x;
        upd(0, SEG, x, j, 1);

        for (i32 i = 0; i <= 30; ++i) {
            if (x & (1 << i)) {
                R[i] = j;
                Max(MAXN, i + 1);
            }
        }

        for (i32 i = 0; i <= MAXN; ++i) {
            i32 t = 1 << i;
            ans += (u64)max(R[i], (t <= SEG) ? mi[id[t - 1]] : 0) * t;
        }
    }
    cout << ans << '\n';
    return 0;
}