一道困扰我一天的线段树建模

Question

遇到一个不会做的题目，特此发布此问答
题目：

我的代码：

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
int tree[4 * MAXN];
vector<int> nums;
void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = nums[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }
} 
int queryClosestLarger(int node, int start, int end, int idx, int val) {
    if (start == end) {
        return tree[node];
    }
    int mid = (start + end) / 2;
    if (idx <= mid) {
        return queryClosestLarger(2 * node, start, mid, idx, val);
    } else {
        int rightResult = queryClosestLarger(2 * node + 1, mid + 1, end, idx, val);
        int leftMax = tree[2 * node];
        if (abs(val - leftMax) <= abs(val - rightResult)) {
            return leftMax;
        } else {
            return rightResult;
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    build(1, 0, n - 1);
    for (int i = 1; i < n; ++i) {
        cout << queryClosestLarger(1, 0, n - 1, i - 1, nums[i]) << " ";
    }
    cout << endl;
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

对于这道题，你提出的线段树模型接近正确，但是有几个关键点需要调整才能符合题目的要求。首先，线段树应该支持动态更新，因为每次输入一个新数时，线段树的结构需要反映所有已输入的数。其次，线段树不仅要存储最大值，还要能返回与查询值最接近且比查询值大的数（如果有多个，返回最大的那个）。最后，由于数据可能重复，我们需要在树中记录每个数值出现的次数。

下面是一个修改后的线段树实现，它能够满足题目的需求：

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;

struct Node {
    int val, maxVal, count;
};

const int MAXN = 1e5 + 5;
Node tree[4 * MAXN];
vector<int> nums;
int lazy[4 * MAXN]; // Lazy propagation array

void update(int node, int start, int end, int idx, int delta) {
    if (lazy[node] != 0) {
        tree[node].val += lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    if (start > idx || end < idx) return;
    if (start == end) {
        tree[node].val = idx;
        tree[node].maxVal = idx;
        tree[node].count = 1;
        return;
    }
    
    int mid = (start + end) / 2;
    update(2 * node, start, mid, idx, delta);
    update(2 * node + 1, mid + 1, end, idx, delta);
    
    tree[node].maxVal = max(tree[2 * node].maxVal, tree[2 * node + 1].maxVal);
}

int queryClosestLarger(int node, int start, int end, int l, int r, int val) {
    if (lazy[node] != 0) {
        tree[node].val += lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    if (start > r || end < l) return INT_MIN;
    if (start >= l && end <= r) {
        if (tree[node].maxVal > val) return tree[node].maxVal;
        return INT_MIN;
    }

    int mid = (start + end) / 2;
    int leftResult = queryClosestLarger(2 * node, start, mid, l, r, val);
    int rightResult = queryClosestLarger(2 * node + 1, mid + 1, end, l, r, val);
    
    return max(leftResult, rightResult);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        update(1, 0, 1e5, nums[i], 1); // Assuming input values are in range [0, 1e5]
    }

    for (int i = 1; i < n; ++i) {
        int closestLarger = queryClosestLarger(1, 0, 1e5, 0, 1e5, nums[i]);
        if (closestLarger == INT_MIN) {
            cout << "-1 "; // No value is larger than the current number
        } else {
            cout << closestLarger << " ";
        }
    }
    cout << endl;
    return 0;
}

这个实现中，update 函数用于在线段树中添加或更新一个数的出现情况，而 queryClosestLarger 函数则用于查找与给定值最近且较大的数。注意，为了简化处理，这里假设输入的数都在 [0, 1e5] 范围内，因此线段树的范围被设定为 [0, 1e5]。如果输入范围不同，需要相应调整。

这个版本的代码可以处理动态更新，并在每次查询时找到最近且较大的数。