Nacl

很高兴能在杭电新生赛出题，这也是我 ，感觉还不错。春季联赛还有一道我的题，敬请期待！其实新生赛已经结束很久，现在将题目公开在我的博客。

题目名字比较奇怪，因为当时某个人宣称 NaCl 是他的 npy，没有其他特别的意思。

提交链接：https://www.luogu.com.cn/problem/T544700

题目描述

小 y 喜欢在乐扣刷题，某一天做到了这样一个题

有一个长度为 \(n\) 的数组 \(a\)，求出数组的所有子段和，并将这 \(\frac{n(n+1)}{2}\) 个数降序排列，他想知道第 \(k\) 个数有多大。

小 y 很快就解决了这个问题。但是小 y 觉得比起子段和，二元组的和更加美妙，比如 2Na(s)+Cl₂(g)→2NaCl(s)，于是小 y 决定将子段和改成子段中最大值与最小值的和。

小 y 有一个长度为 \(n\) 的数组 \(a\)，定义 \(\text{val}(l，r)=\min(a_l,a_{l+1},\dots,a_{r-1},a_r) + \max(a_l,a_{l+1},\dots,a_{r-1},a_r)\)。 小 y 想知道对于所有的 \(\text{val}(l,r)，1\le l\le r\le n\)，降序排列后，第 \(k\) 个数是多少，也就是第 \(k\) 大的 \(\text{val}\)。

输入格式

第一行一个正整数 \(T\) (\(T\le200\)) 表示数据组数。

对于每组数据：

第一行输入三个整数 \(n\) 和 \(k\)，\((1\le n\le10^5，1\le k\le \frac{n(n+1)}{2})\) 分别表示数组长度，要求第多少大的 \(\text{val}\)。

第二行包含 \(n\) 个用空格分隔的整数，其中第 \(i\) 个数字表示 \(a_i\) 的值。 \((0\le a_i\le 10^9)\)

保证 \(\sum n=1064824\)

输出格式

对于每组数据，输出一个整数，表示所有的 \(\text{val}(l,r)，1\le l\le r\le n\) 中，第 \(k\) 大的 \(\text{val}\) 的大小。

输入 #1

2
5 3
1 2 3 3 4
10 10
9 6 7 5 5 4 7 2 5 8

输出 #1

7
13

题解

题解文件找不到了，我就贴图片吧。

更新：更快的复杂度（2026-09-26）

本节的优化思路由 ChatGPT 提供，代码据此整理。

原题解对每个位置二分左右的最大值，每次判定需要 \(O(n\log n)\)。可以把这一步改成离线扫描：固定答案 \(x\)，对最小值位置 \(i\) 设阈值 \(t=x-a_i\)。不达标的区间必须完全不包含任何 \(a_j\ge t\) 的位置。

按 \(a_i\) 从大到小处理位置，阈值 \(t\) 单调递增；同时删除所有 \(a_j<t\) 的位置。用并查集合并相邻的已删除位置，就能在均摊 \(O(\alpha(n))\) 时间内找到包含 \(i\) 的已删除连续段边界，也就是左右最近的 \(a_j\ge t\) 的位置。将这两个边界限制在 \(i\) 作为最小值时的归属范围内，即可直接算出不达标区间数。

下面是完整的 C++17 实现。最小值相同的区间按“左侧严格小于、右侧小于等于”的边界规则分配给最右侧最小值位置，与原题解一致。

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

struct DeletedDSU {
    int n;
    vector<int> parent, size, left, right;
    vector<char> removed;

    explicit DeletedDSU(int n)
        : n(n), parent(n + 1), size(n + 1, 1),
          left(n + 1), right(n + 1), removed(n + 1, false) {
        iota(parent.begin(), parent.end(), 0);
        iota(left.begin(), left.end(), 0);
        iota(right.begin(), right.end(), 0);
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != x) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        left[a] = min(left[a], left[b]);
        right[a] = max(right[a], right[b]);
    }

    void erase(int x) {
        if (removed[x]) return;
        removed[x] = true;
        if (x > 1 && removed[x - 1]) unite(x, x - 1);
        if (x < n && removed[x + 1]) unite(x, x + 1);
    }

    pair<int, int> nearestAlive(int x) {
        int root = find(x); // x is removed when this is called
        return {left[root] - 1, right[root] + 1};
    }
};

int64 kthLargest(const vector<int>& a, int64 k) {
    int n = static_cast<int>(a.size()) - 1;
    vector<int> L(n + 1), R(n + 1), st;

    // Previous strictly smaller element.
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? 1 : st.back() + 1;
        st.push_back(i);
    }

    // Next smaller-or-equal element.
    st.clear();
    for (int i = n; i >= 1; --i) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back() - 1;
        st.push_back(i);
    }

    vector<int> order(n), removeOrder;
    iota(order.begin(), order.end(), 1);
    sort(order.begin(), order.end(), [&](int x, int y) {
        return a[x] > a[y];
    });
    removeOrder = order;
    reverse(removeOrder.begin(), removeOrder.end());

    auto countAtLeast = [&](int64 x) {
        DeletedDSU dsu(n);
        int ptr = 0;
        int64 count = 0;

        for (int i : order) {
            int64 threshold = x - a[i];
            while (ptr < n && a[removeOrder[ptr]] < threshold) {
                dsu.erase(removeOrder[ptr++]);
            }

            int64 total = 1LL * (i - L[i] + 1) * (R[i] - i + 1);
            if (a[i] >= threshold) {
                count += total;
                continue;
            }

            auto [p, q] = dsu.nearestAlive(i);
            int64 leftChoices = i - max(L[i], p + 1) + 1;
            int64 rightChoices = min(R[i], q - 1) - i + 1;
            int64 below = leftChoices * rightChoices;
            count += total - below;
        }
        return count;
    };

    int64 maxA = *max_element(a.begin() + 1, a.end());
    int64 low = 0, high = 2 * maxA;
    while (low < high) {
        int64 mid = low + (high - low + 1) / 2;
        if (countAtLeast(mid) >= k) low = mid;
        else high = mid - 1;
    }
    return low;
}

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        int64 k;
        cin >> n >> k;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        cout << kthLargest(a, k) << '\n';
    }
    return 0;
}

单次判定为 \(O(n\alpha(n))\)，排序和单调栈预处理为 \(O(n\log n)\)；答案上界为 \(2A\) 时，总复杂度为 \(O(n\log n+n\alpha(n)\log(2A+1))\)，空间复杂度为 \(O(n)\)。

赛时情况

比赛时有 5 个老哥 AC 了这道题(1001)，可能是因为码量比较大吧。