1845d

[原题](https://codeforces.com/contest/1845/problem/D) [翻译](https://www.luogu.com.cn/problem/CF1845D) 我写了个线段树233 我们发现对于一个固定的$k$，我们可以把原序列分为三段： * 上升到$k$以上 ......

## 题面 给定一个长度为 $n$ 数列 $a$，保证每项都不为 $0$。初始时 $x=0$，然后对于 $1\le i\le n$，按顺序进行如下操作： - 如果 $x\ge k$，则 $x\rightarrow \max(k, x+a_i)$，否则 $x\rightarrow x+a_i$。 你需 ......

易于发现的是，假设设置的保护分为k，且k是为了避免某一项负值ai。令s=sum(a0, ai-1)，则将k设置为s一定更优于介于[s-ai,s)中的任何值。 那么就需要研究什么情况下，我们选择当前的前缀和作为k，以使得最终值最大。应该是为了避免最小的一段递减。 因而可以研究最小子数列，类kadane ......

Problem - 1845D - Codeforces Rating System - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题意可以去洛谷看一下。 没带苏菲狗，鼠标手画。属实抱歉 我们可以看到这个最后的等级是这样计算的，直到它第一次到k只是一个前缀和，在达到k之后，出现一 ......