退役III次后做题记录（扯淡）
CF607E Cross Sum
计算几何屎题
直接二分一下，算出每条线的位置然后算
注意相对位置这个不能先搞出坐标，直接算角度就行了，不然会卡精度/px
flag：计几题都不写了
CF611G New Year and Cake
真香
双指针扫可行的区间然后维护。
一个三角形的面积可以用\(|AB+BC+CA|\)算，其中\(A,B,C\)是向量\(OA,OB,OC\)，\(O\)在三角形外
然后推出的式子可以很好地化简然后维护（为啥我写这么慢啊
CF504E
巨大常数卡过去了 舒服
二分+哈希，然后哈希可以\(O(巨大常数)\)算，要长链剖分算一个\(x\)的\(k\)级祖先
https://codeforc.es/contest/504/submission/63411989
CF506C
二分，然后倒着做，变成一开始有\(n\)个高度为\(mid\)的，每个时刻开始高度全部减\(a_i\)，然后选择\(k\)个高度加\(p\)。
考虑限制是啥，正着做的时候一开始是\(h_i\)，中间会出现一些\(<0\)的时候很不爽，一开始先给\(h_i\)加上一个数就很爽了，条件就是高度始终\(\ge 0\)，倒着做的话另一个条件就是最后的高度满足\(\ge h_i\)
对每个东西维护：如果不再操作，最后的值\(fi\)。如果有\(fi<0\)，肯定先做\(fi<0\)，有多个先做更早会\(<0\)的
否则随便做一个\(fi_i<h_i\)的，然后可以check了
CF704B
对连通块dp。
AGC028C
答案一定是所有\(A,B\)中选\(n\)个，先拿出所有的升序排序，然后拿出最小的\(n\)个，看是否能取到，如果不能再分情况讨论
（懒得写了
CF521D
求个\(\ln\)后三操作就是加，1,2操作是凸的，可以用一个堆维护
CF536D
每个点到\(s,t\)最短距离后转化为一个坐标，在坐标轴上面dp，前缀和优化
CF547D
这提姆不就是704d吗= =
CF571D
先对每个询问求出最后一次清空的时间就可以忽略清空操作了
搞出重构树，直接在上面操作
CF576D
bitset优化01矩乘
毒瘤= =zbl
CF582D
这题先咕了
CF587D
屎题
抠出每种颜色，显然只能是很多链或者环，分情况讨论亿下，长度为奇数的链还要二分 2sat
CF643D
搞一堆set大模拟，修改点时只用修改父亲
CF521E
加边加到图不是仙人掌时可以找到端点，然后输出方案
CF576E
线段树分治 可以操作到叶子节点之后再放之后的操作
CF582E
设\(f_{i,j}\)表示树上点i，对于所有变量取值的答案压到\(j\)，方案数
转移用fwt
CF585E
直接莫反，不算\(1\)的话每对集合和数会算\(-1\)次
CF538H
显然图是个二分图，染色之后同一个连通块同一个颜色缩成一个区间
然后问题就是有很多对区间，取两个位置\(p1,p2\)对于每一对区间正好分别在一个区间内
然后直接枚举左端点，对一对区间可行的右端点还是个区间，线段树维护即可
CF575I
鸽子好神仙啊
先要维护三个东西：
以一个点为右上角的矩形
以一个点向左下的直线和向下的直线围成的图形（直角三角形）
以一个点向右下的直线和向下的直线围成的图形（直角三角形）
然后4个操作都可以用这三个东西容斥出来
CF626G
设\(t\)表示题面中\(l\)，\(s\)表示你的方案中每个箱子放的数量。有限制\(\sum s\leq T\)
那么你最终收益期望是\(\sum p_i-\sum \frac{t_ip_i}{t_i+s_i}\)
那么要最小化后面的东西，也就是最大化\(\frac{t_ip_i}{t_i+s_i}\)
一组询问可以用堆维护，然后修改一个\(t_i\)并不会影响其他选取方案的相对顺序
可以证明，给一个\(t_i\)修改\(1\)过后的\(s\)最多只会有一处增加和一处减少
先看给\(t_i\)加1，那么选这个箱子整体会变差，所以策略是可能会拿走一个给别的箱子
如果拿走两个是不可能的，因为原来选了这个箱子收益是\(\frac{t_ip_i}{t_i+s_i}\)，后来变成了\(\frac{(t_i+1)p_i}{t_i+s_i+1}\)，\(s_i\)减去\(1\)后变成\(\frac{(t_i+1)p_i}{t_i+s_i}\)，严格大于原来的收益，既然原来的选了这个肯定不会被换掉
给\(t_i\)减1类似，策略是如果超了先减1然后选这个箱子会变好，可能会从另一个箱子拿一个过来，不过类似上面可证明不会拿两个过来
然后用一个堆维护“插入箱子”和“从箱子拿出”的最大值就行了