galaxy plan 8.2 A. 小怪兽（monster）
你说得对但是决策单调性状物代价相等的都包含进去分治可以 ac，正确性不知道，至少复杂度是假的。不过下述做法考场也想到了。
首先做一个比较小的转化，\(Ans=n-\frac{1}{n}\sum_i\sum_j[a_i\leq p_j]\)，这样就不用管一些乱七八糟的东西了谢谢喵 >w<
感觉看着有一点点 slope trick 的味道，虽然不可能是但是我们还是想想两个函数怎么合并嘛，首先每一个 \(p_i\) 代价独立，不妨设 \(sub(x)\) 表示选择一个能力为 \(x\) 能杀死的人数。设 \(f(x)\) 表示总和为 \(x\) 的时候最好的代价，然后我们把 \(sub\) 合并进 \(f\) 得到 \(f'\)，此时 \(f'\) 的允许分段数就比 \(f\) 多 \(1\) 了，具体而言 \(f'(x)=\max\{f(x-\alpha)+sub(\alpha)\}\)，这种东西 \(O(m^2)\) 可以跑一次加法卷积，容易想到合并 \(f,f\) 得到 \(f''\)，此时 \(f''\) 的允许分段上限是 \(f\) 的两倍，然后做法不就出来了，用这两种卷积方式让分段数上线 \(\times 2/+1\) 得到 \(n\)，复杂度 \(O(m^2\log n)\)。
galaxy plan 8.2 B. 完美主义（path）/ 轻微修改了数据范围 & 加入强制在线的 CF864F
题面对做法暗示非常明显，\(n,m\) 小 \(q\) 大强制在线，查询除了倍增还能干什么，那么设 \(f[i][j][k]\) 表示在 \(i\to j\) 的完美路径中 \(i\) 前进 \(2^k\) 步所到达的节点，没有此节点则令其为 \(0\)。然后无解很好判断了，根据定义，如果 \(f[i][j][\log_2n+1]\) 不为 \(0\) 就是会死循环，\(f[i][j][0]\) 为 \(0\) 就是不连通嘛。
这个 \(f\) 显然可以递推也就是 \(f[i][j][k]=f[f[i][j][k-1]][j][k-1]\)，那么现在问题只剩下怎么求这个 \(f[i][j][0]\) 了，我们发现这个也很好求，\(i\) 有出边相连的且能到达 \(j\) 的最小的节点就是了，这么东西直接枚举 \(j\)，反图上搜出能到达 \(j\) 的节点，然后所有的 \(i\) 可以计算出 \(f[i][j]\)，注意 \(f[j][j]=0\)，于是我们做完了，然后常数方面的话，显然超多 \(-1\)，先判断无解能快不少，我没有先判断在 mx OJ 上 tle 了嘻嘻。
galaxy plan C. 摘苹果（apple）
首先自己手玩一下，必须剃掉 \(l,\dots,r\) 上面每位一个 \(1\) 是一个初始的贡献，发现来回走的区间长度为 \(2\) 的话是额外一个 \(1,1\) 状物，来回走是额外一段 \(1,2,2,\dots,2,2,1\) 状物，然后发现后面那个可以被前面那个 \(1,1\) 表示完，所以问题就变成给定一个区间，在区间上的 \(a_i\geq 1\) 的时候 \(a_i\gets a_i-1\) 然后判断可不可以通过 \(a_p\gets a_p-1,a_{p+1}\gets a_{p+1}-1(l\leq p<r)\) 这样的操作把整个区间置 \(0\)。
非常显然的从左到右操作可以直接固定操作次数，\(a_i\) 的垃圾只能 \(a_{i+1}\) 来解决，\(a_l\) 上面剩下 \(a_l\) 个，\(a_{l+1}\) 上面剩下 \(a_{l+1}-a_l\) 个，\(a_{l+2}\) 上面剩下 \(a_{l+2}-a_{l-1}+a_l\) 个，以此类推，设 \(i\) 上面的这个贡献为 \(sum_i\)，要求就是 \(sum_r=0,sum_i\geq 0\) 这样子。
一看就是个有点恶心但不多的分类讨论状物，首先这个奇数 \(i\) 和偶数 \(j\) 的贡献方式都相反了，我们翻转所有偶数位的 \(sum\) 得到 \(sum'\)，这样的序列是好看的，奇数位写下 \(a'_i=a_i\)，偶数位写下 \(a'_i=-a_i\)，然后 \(sum'[i]=\sum_{j=1}^i a'_j\)，奇数位 \(sum[i]=sum'[i]\)，偶数位 \(sum[i]=-sum'[i]\)。
查询只要知道 \(\min_{i 是奇数}\{sum'_i\},\max_{i 是偶数}\{sum'_i\}\)，我们分开两个线段树维护，空着的位置防止干扰放置 \(\infty/-\infty\) 就可以了，而修改要考虑的可就多了，我们对 \(l,r\) 的奇偶性分类讨论一下，因为 lsy 要回宿舍【】就不细说了，况且这部分是平凡且简单的。
标签：奇数,2024.8,sum,记录,然后,偶数,节点,galaxy From： https://www.cnblogs.com/chelsyqwq/p/18339646