C26I:Relaxing Bounds

http://poj.openjudge.cn/practice/C26I/

C++

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

struct RangeMaxPointQuery {
    int base;
    vector<int> tree;

    RangeMaxPointQuery(int n = 0) {
        init(n);
    }

    void init(int n) {
        base = 1;
        while (base < n) base <<= 1;
        tree.assign(base * 2, 0);
    }

    // range [l, r], chmax with val
    void update(int l, int r, int val) {
        if (l > r) return;

        l += base;
        r += base;

        while (l <= r) {
            if (l & 1) {
                tree[l] = max(tree[l], val);
                ++l;
            }
            if (!(r & 1)) {
                tree[r] = max(tree[r], val);
                --r;
            }
            l >>= 1;
            r >>= 1;
        }
    }

    // max value covering point pos
    int query(int pos) const {
        int res = 0;
        pos += base;

        while (pos > 0) {
            res = max(res, tree[pos]);
            pos >>= 1;
        }

        return res;
    }
};

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

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<long long> a(n);
        vector<long long> xs;

        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            xs.push_back(a[i]);
        }

        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        RangeMaxPointQuery seg((int)xs.size());

        int ans = 0;

        for (int i = 0; i < n; ++i) {
            long long x = a[i];

            int pos = lower_bound(xs.begin(), xs.end(), x) - xs.begin();

            int best = seg.query(pos);
            int dp = best + 1;

            ans = max(ans, dp);

            long long L = x - dp;
            long long R = x + dp;

            int l = lower_bound(xs.begin(), xs.end(), L) - xs.begin();
            int r = upper_bound(xs.begin(), xs.end(), R) - xs.begin() - 1;

            seg.update(l, r, dp);
        }

        cout << ans << '\n';
    }

    return 0;
}

这是一个使用离散化与线段树优化动态规划（DP）的问题。

题目逻辑解读

核心 DP 转移：
- 对于序列中的每一个数 $a [i]$ ，我们要找到一个最优的 $d p$ 值（代表以当前元素结尾或经过当前元素的最长序列长度）。
- $d p [i] = query (a [i]) + 1$ 。这里的 query(a[i]) 是查询当前所有已经生效的区间中，包含点 $a [i]$ 的区间的最大权值。
- 更新操作：计算出 $d p [i]$ 后，该元素会产生一个影响范围，即区间 $[a [i] - d p [i], a [i] + d p [i]]$ 。我们将线段树中对应这一段范围的所有点与 $d p [i]$ 取 $m a x$ 。
线段树类型（标记永久化/对偶线段树）：
- 代码实现的是一种区间修改、点查询的线段树。
- update(l, r, val)：区间修改，使用 tree[p] = max(tree[p], val)。
- query(pos)：点查询，从叶子节点到根节点的路径上取所有标记的最大值。
坐标离散化：
- 由于 $a [i]$ 的数值可能很大，但 $n$ 的规模在 $10^{5}$ 左右，因此先将所有出现的 $a [i]$ 进行排序去重，映射到 $[0, size - 1]$ 的索引空间。

Python 代码实现

为了在 Python 中达到较好的性能，我们使用迭代式线段树（zkw 线段树风格），并利用 bisect 模块进行快速检索。

python

import sys
from bisect import bisect_left, bisect_right

class RangeMaxPointQuery:
    def __init__(self, n):
        self.base = 1
        while self.base < n:
            self.base <<= 1
        self.tree = [0] * (self.base * 2)

    def update(self, l, r, val):
        """区间 [l, r] 与 val 取 max"""
        if l > r:
            return
        l += self.base
        r += self.base
        while l <= r:
            if l % 2 == 1:
                if val > self.tree[l]: self.tree[l] = val
                l += 1
            if r % 2 == 0:
                if val > self.tree[r]: self.tree[r] = val
                r -= 1
            l >>= 1
            r >>= 1

    def query(self, pos):
        """点查询：返回覆盖该点的所有区间的最大标记"""
        res = 0
        pos += self.base
        while pos > 0:
            if self.tree[pos] > res:
                res = self.tree[pos]
            pos >>= 1
        return res

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    t_cases = int(next(it))
    
    output = []
    for _ in range(t_cases):
        n = int(next(it))
        a = [int(next(it)) for _ in range(n)]
        
        # 离散化
        xs = sorted(list(set(a)))
        m = len(xs)
        
        seg = RangeMaxPointQuery(m)
        ans = 0
        
        for x in a:
            # 找到 x 在离散化后的位置
            pos = bisect_left(xs, x)
            
            # 查询点查询最大值
            best = seg.query(pos)
            dp = best + 1
            
            if dp > ans:
                ans = dp
                
            # 计算更新范围 [x - dp, x + dp]
            left_val = x - dp
            right_val = x + dp
            
            # 找到范围内对应离散化索引的边界
            l_idx = bisect_left(xs, left_val)
            r_idx = bisect_right(xs, right_val) - 1
            
            # 区间更新
            seg.update(l_idx, r_idx, dp)
            
        output.append(str(ans))
    
    sys.stdout.write("\n".join(output) + "\n")

if __name__ == "__main__":
    solve()

关键优化与解读

迭代式线段树：
- 在 Python 中，传统的递归线段树开销极大。迭代式线段树通过 while l <= r 循环实现区间定位，通过 pos >>= 1 实现点查询，避开了递归深度限制，速度提升显著。
- self.tree 数组存储的是该节点代表的区间被更新过的最大 $d p$ 值。
离散化查找：
- bisect_left(xs, x)：相当于 C++ 的 lower_bound。
- bisect_right(xs, x + dp) - 1：相当于查找小于等于 x + dp 的最大元素的索引。
时间复杂度分析：
- 坐标离散化： $O (N \log N)$ 。
- 单次 DP 转移：包含两次二分查找 $O (\log N)$ 和一次线段树操作 $O (\log N)$ 。
- 总复杂度： $O (T \cdot N \log N)$ 。对于 $N = 10^{5}$ 的规模，Python 在 $2 \sim 3$ 秒内通常可以完成。
内存优化：
- 使用了 sys.stdin.read().split() 配合生成器/迭代器，这比逐行读取更能有效利用内存并加快速度。
- sys.stdout.write 用于一次性输出结果，减少了 I/O 次数。

C26I:Relaxing Bounds ​

题目逻辑解读 ​

Python 代码实现 ​

关键优化与解读 ​

C26I:Relaxing Bounds

题目逻辑解读

Python 代码实现

关键优化与解读