T1
仔细思考一番，发现 \(s\) 点的答案是
\[\begin{aligned} &\max_{P_i>P_s}(P_i-\sum_{j\in S_{P_i-1}} P_j)\\ &=\max_{p\ge P_s}(p+1-\sum_{j\in S_p}P_j) \end{aligned} \]其中 \(S_k\) 表示只保留 \(P\le k\) 的点后 \(s\) 所在的连通块。
所以可以按照 \(P\) 的大小一个一个加点，需要数据结构维护：
- 两个集合快速合并
- 对一个集合快速操作
一开始傻傻地写了一个 treap 调了 1h，其实可以用链表+并查集维护。
T2
首先利用 NOIP2023T4 的思路扫描线变成区间历史最大值，线段树上每个坐标 \(x\) 维护 \([x,i]\) 的答案，则新加入一个点 \(i\)，考虑其作为最小值最小能延伸至 \(j\)，则 \([j,i]\) 区间覆盖一个等差数列；对于 \([1,j)\) 有区间长度加一，用 KTT 维护；同时动态维护区间历史最大值。
貌似很难搞，所以分块建凸包！根号算法最高！考虑单点 \(j\) 的贡献为 \((i-j+1)\times min(j,i)=(-j+1)\times min(j,i)+i\times min(j,i)\)
就是建一个点 \((-min(j,i),(-j+1)min(j,i))\) 然后就是对每个块建凸包，整块查询用一个斜率为 \(i\) 的直线切一下，散块查询暴力做。考虑更新，形如把一段后缀覆盖为 \((-a,(-j+1)a)\)。如果整个凸包都被覆盖，则显然其凸包只有一个点，那就是 \((-a,(-l+1)a)\)。否则直接暴力重构一下就可以了。因为是历史最大值，所以可以用一个凸包取 max，然后上面那个凸包覆盖就是动态插入。
结果要动态凸包……嘛，毕竟是省选模拟赛
动态凸包的模板题躺在 TODO LIST 里面至今没打完 QAQ
T3
\[f(A,B,k)=\min_{S\subseteq[1,n],|S|=k}\min_{p是[1,k]的一个排列}\max_{i=1}^k(\sum_{j=1}^iA_{S_{p_j}}+B_{S_{p_i}}) \]对于每个 \(k\)，求所有的 \(1\le A_i\le V\) 的 \(f(A,B,k)\) 之和
题目提示复杂度是 \(O(2^VN)\) 的。
标签：13,12,min,max,sum,凸包,2024,le,times From： https://www.cnblogs.com/kodoku/p/18605326