10.4 - ?? 改题纪要
10.4 - ?? 改题纪要
还是决定写一起。
等写完了就会把问号改了
冲刺CSP联训模拟2
以后见了计数先想容斥！！！
-
挤压
按位拆开，每两位一块考虑，枚举每个数是否选，\(O(nlog^2n)\) 的。
-
工地难题
考虑恰好比较难做，先前缀和变成至少。
发现 \(0\) 个数一定，其将序列分成若干小段，每段有若干 \(1\)。
相当于是 \(\sum x_i = k(x_i<k)\) 的形式，直接容斥即可。
-
星空遗迹
首先发现点显然的性质。
- 连续一段的长度无意义。
- 如果一段中两端（如果只有一端就是一端）都是能赢他的，就可以删掉这一段。
- 依次删掉后一定只剩下一段相同的。
由此可以有单调栈写法，保证任意一个非栈顶元素一定会输给其下一个（也可写逆天并查集，但好像不太好扩展到正解）。
考虑修改。
对于每个元素，维护栈在加入它后的大小，设其为 \(f_i\)：
\[f_i=\begin{cases} f_i+1 & s_i<s_{i-1}\vee i=1\\f_i & s_i=s_{i-1}\\\max(f_i-1,1) & s_i>s_{i-1}\end{cases} \]最后的答案就是最后一个为 \(1\) 的位置
发现这个 \(max\) 很难整，考虑直接去掉，发现其相当于是连续下降，容易证明有一个好的性质：只有最小值和最后一个 \(1\) 一一对应。
但其实也不用特意找最后一个，考虑升降是对称的，所以栈大小相同的元素一定是一样的。
维护单点改，前缀和的区间 \(min\)，可以直接上线段树上二分，也可以前缀和变成区间加，区间 \(min\)。
-
纽带
析合树上 \(dp\)，这是我现在能改的？？？
——————————————————————————————————————————————————————————————————————————————————————————————————————————