比赛：CF2151 Div.2
chenwenmo
·
·
题解
CF2151 Div.2
A. Incremental Subarray
如果有跨段的情况，答案为 1。否则子数组只在一段内，输出 n-a_{m}+1。
Code
B. Incremental Path
考虑继承上一个人的位置，如果上一个人的最后一个操作是 B，那么当前的人就在上一个人的终止位置进行一次 B 操作，然后再进行这个人的最后一次操作。暴力往后跳即可，跳的次数是 O(n) 的。
Code
C. Incremental Stay
- 对于两端的 $(1,n),(2,n-1),\cdots,(k-1,n-(k-1)+1)$ 匹配。
- 对于中间的 $(k,k+1),(k+2,k+3),\cdots,(n-(k-1)-1,n-(k-1))$。
[Code](https://codeforces.com/contest/2151/submission/340165100)
### [D. Grid Counting](https://codeforces.com/contest/2151/problem/D)
这题限制条件都很紧，从题目的条件一步步缩小计数范围即可。
[Code](https://codeforces.com/contest/2151/submission/340179485)
### [E. Limited Edition Shop](https://codeforces.com/contest/2151/problem/E)
赛时不知道为什么想那么久贪心。考虑 DP。
设 $f(i,j)$ 表示 Alice 拿完前 $i$ 个，Bob 拿完前 $j$ 个，之后 Alice 能获得的最大价值。边界是 $f(n,*)=0$，答案为 $f(0,0)$。
考虑 $O(n^2)$ 暴力转移：
- $f(i,j)\gets f(i+1,j) + [j<p_{a_{i+1}}]\cdot v_{a_{i+1}}$，其中 $p_i$ 表示 $i$ 在 $b_i$ 中的下标。
- $f(i,j)\gets f(i,j+1)$。
第一个转移是前缀加，第二个转移相当于要维护后缀 $\max$。
如果前缀加一个正数，后缀 $\max$ 不变。
如果前缀加一个负数，
- 假设当前是区间 $[1,p)$ 加 $v$，当前后缀 $\max$ 数组为 $f$。对于 $[1,p)$ 中所有满足 $f_i+v\le f_p$ 的位置，相当于要直接赋值为 $f_p$；否则，直接加上 $v$ 不会影响后缀 $\max$ 数组。
因此用线段树 区间加 + 区间赋值 维护即可，找位置可以用线段树二分做到 $O(\log n)$，直接写二分 $O(\log^2n)$ 也能过。
[Code](https://codeforces.com/contest/2151/submission/340212281)