T1 Promotion Counting

algorithm: segtree, BIT

水题，树状数组差分即可。

T2 rabbit

algorithm: network-flow, greedy

乱搞。 将数据用桶装起来，枚举胡萝卜或干草，与另一个分别相减。

网络流？不会（好像是最小割）。

T3 【2024年SD省队集训 day2】反转了 (flip)

algorithm: PST, divide-and-conquer

先考虑朴素算法，若当前前缀和右端点为 i，则反转的肯定为 [1, i] 间最小的 k 个数，用主席树计算，时间复杂度 O(n2log n)。

发现有决策单调性，第 k + 1 次反转的最优右端点 一定大于 等于第 k 次反转的右端点。

证明：https://lnw143.github.io/blog/gmoj/p8081/#%E5%8D%95%E8%B0%83%E6%80%A7%E8%AF%81%E6%98%8E

考虑分治，设函数 solve(l,r,L,R)。

每次把求 $k = \frac{l+r}{2}$ 的答案，暴力跑 [L, R] 区间，求出答案。

T4 【GDOI2020模拟】 亚特兰大 (atoranta)

暂缺