标签 最大子段和 下的文章

「Codeforces 280D」K-Maximum Subsequence Sum

题目链接：Codeforces 280D

你有一个长度为 $n$ 的序列 $a_i$，接下来进行 $m$ 次操作，操作分为如下 $2$ 种：

• 0 i val：将第 $i$ 个数 $a_i$ 修改为 $val$。
• 1 l r k：你需要在序列 $a_l, a_{l + 1}, \cdots, a_r$ 中找出至多 $k$ 个不相交的子序列，使得他们的和最大。形式化地，你需要找出至多 $k$ 对 $(x_1, y_1), (x_2, y_2), \cdots, (x_t, y_t)$（其中 $l\le x_1\le y_1<x_2\le y_2<\cdots<x_t \le y_t\le r$，$0\le t\le k$），使得 $(a_{x_1} + a_{x_1 + 1} + \cdots + a_{y_1}) + (a_{x_2} + a_{x_ 2 + 1} + \cdots + a_{y_2})+\cdots + (a_{x_t} + a_{x_t + 1} + \cdots + a_{y_t})$ 的值最大。

特别地，你可以选择 $0$ 个子序列，这时和式等于 $0$。

数据范围：$1 \le n, m\le 10 ^ 5$，$\vert a_i, val \vert \le 500$，$1\le k\le 20$，求 $k$ 个子序列和的操作不超过 $10^4$ 个。

「NOI 2005」维修数列

题目链接：BZOJ 1500

请写一个程序，要求维护一个数列。一共有 $m$ 个操作，支持以下 $6​$ 种操作：

数据范围：$1\le m\le 2\times 10 ^ 4$，任何时刻数列中最多含有 $5\times 10 ^ 5$，数列中任何一个数字均在 $[-10^3,10^3]$，插入的数字总数不超过 $4\times 10 ^ 6$ 个。