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(n^2log \ 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)

暂缺