P2123
注意到重排，注意到 CCC 恰好依赖前面一项的 CCC 与前缀的 AAA，所以考虑邻项交换。
显然，我们需要最小化每一个 CCC。
推式子，Ci=max{Ci−1,∑j=1iAj}+Bi,Ci+1=max{max{Ci−1,∑j=1iAj}+Bi,∑j=1i+1Aj}+Bi+1C_i=\max\{C_{i-1},\sum_{j=1}^i A_j\}+B_i,C_{i+1}=\max\{\max\{C_{i-1},\sum_{j=1}^i A_j\}+B_i,\sum_{j=1}^{i+1} A_j\}+B_{i+1}Ci =max{Ci−1 ,∑j=1i Aj }+Bi ,Ci+1 =max{max{Ci−1 ,∑j=1i Aj }+Bi ,∑j=1i+1 Aj }+Bi+1 ；
不考虑第一项，展开：Ci+1=max{∑j=1iAj+Bi+Bi+1,∑j=1iAj+Ai+1+Bi+1}=∑j=1i−1Aj+Ai+Ai+1+Bi+1+Bi−min{Ai+1,Bi}C_{i+1}=\max\{\sum_{j=1}^i A_j+B_i+B_{i+1},\sum_{j=1}^i A_j+A_{i+1}+B_{i+1}\}=\sum_{j=1}^{i-1} A_j+A_i+A_{i+1}+B_{i+1}+B_i-\min\{A_{i+1},B_i\}Ci+1 =max{∑j=1i Aj +Bi +Bi+1 ,∑j=1i Aj +Ai+1 +Bi+1 }=∑j=1i−1 Aj
+Ai +Ai+1 +Bi+1 +Bi −min{Ai+1 ,Bi }。
假设交换 (i,i+1)(i,i+1)(i,i+1)，则前面那一坨值不变，变的只是 min\minmin。因此若满足 min{Ai+1,Bi}≥min{Ai,Bi+1}\min\{A_{i+1},B_i\}\ge \min\{A_i,B_{i+1}\}min{Ai+1 ,Bi }≥min{Ai ,Bi+1 }，则原方案一定不劣；否则交换 (i,i+1)(i,i+1)(i,i+1) 不劣。
那是不是按照这个排序就行了呢？注意到，这个不满足“不可比性的传递性”。
比如说 A={7,1,1},B={8,1,9}A=\{7,1,1\},B=\{8,1,9\}A={7,1,1},B={8,1,9}，这样就不符合传递性了。
那咋办？继续找性质吧。
我们又注意到，AAA 更小的放到前面一定不劣。现在，我们把 Ai<AjA_i\lt A_jAi <Aj 作为次要条件加进去，看看对不对。
::::info[证明满足非自反性、非对称性、传递性]
显然。
::::
然后不满足它交换一定不劣、满足它交换一定不优，所以可以大胆排了！
时间复杂度：O(nlogn)O(n\log n)O(nlogn)。
P2949
按截止时间排序。开个堆，维护当前价值最小值。如果大小超过了当前时间，弹出最小值。
诶这为啥是对的来着（
时间复杂度：O(nlogn)O(n\log n)O(nlogn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以下是数据结构题。
HDU-5603
考虑类似区间数颜色的方法。
按左端点扫描。如果某个点坐标小于左端点了，那就删除它，加入它那组后一个点。如果扫到了线段的左端点，那么将右端点前缀所有点 +1+1+1。
需要支持动态单点添加、单点删除、前缀 +x+x+x、单点查询的数据结构，平衡树或权值树状数组即可做到。这里使用树状数组实现。
时间复杂度：O(nlogV)O(n\log V)O(nlogV)。
CF2045E
首先考虑 O(n2)O(n^2)O(n2) 做法，也就是枚举每一个区间，计算它们的贡献。显然答案为 xxx 的区间 [l,r][l,r][l,r] 的贡献是 x×12n−(r−l+1)−[l≠1]−[r≠n]x\times \frac{1}{2}^{n-(r-l+1)-[l\not= 1]-[r\not= n]}x×21 n−(r−l+1)−[l=1]−[r=n]。
现在考虑如何快速求出这些区间。
有一个很好的方法是，注意到产生贡献的要求是 maxP1,i≠maxP2,i\max P_{1,i}\not= \max P_{2,i}maxP1,i =maxP2,i ，这个可以拆成 maxP1,i<maxP2,i\max P_{1,i}\lt \max P_{2,i}maxP1,i <maxP2,i 与 maxP2,i<maxP1,i\max P_{2,i}\lt \max P_{1,i}maxP2,i <maxP1,i ，分别枚举两行，看看每个区间是哪个数产生的贡献。
这里以第一行为例。
假设产生贡献的数为 P1,iP_{1,i}P1,i 。则区间需要满足：
* l≤i≤rl\le i\le rl≤i≤r。
* maxj=li−1P1,j≤P1,i\max_{j=l}^{i-1} P_{1,j}\le P_{1,i}maxj=li−1 P1,j ≤P1,i 。
* maxj=i+1rP1,j<P1,i\max_{j=i+1}^{r} P_{1,j}\red{\lt} P_{1,i}maxj=i+1r P1,j <P1,i 。这个小于号是为了不重复统计区间。
* maxj=lrP2,j>P1,i\max_{j=l}^{r} P_{2,j}\gt P_{1,i}maxj=lr P2,j >P1,i 。
对于上面两个情况，能取到的 l,rl,rl,r 应该满足形如 L≤l≤r≤RL\le l\le r\le RL≤l≤r≤R；对于下面的情况，能取到的 l,rl,rl,r 应该满足形如 l≤L′l\le L'l≤L′ 或 r≥R′r\ge R'r≥R′。算出 L,R,L′,R′L,R,L',R'L,R,L′,R′ 后取并集即可。
注意到这个其实就是要我们快速求出 iii 开始的前、后最大值，可以单调栈递推求出。
O(n)O(n)O(n)。
CF526F
做这题之前先尝试做一下这个“橙题”。
本来想找个以前的题解的，好像不知道为啥被删了，算了。
二维平面每个点都不在同一行同一列，考虑离散化转化为一维排列。
现在就看存在多少个子区间 [l,r][l,r][l,r] 满足 maxi=lrPi−mini=lrPi=r−l+1\max_{i=l}^r P_i-\min_{i=l}^r P_i=r-l+1maxi=lr Pi −mini=lr Pi =r−l+1。
首先，我们按 rrr 扫描线，单调栈+线段树处理出 rrr 为结尾后缀的极差 fff。
但是我们感觉直接统计 fi=r−i+1f_i=r-i+1fi =r−i+1 的数量，这个无疑也是困难的。考虑预先将每个 fif_ifi 加上 i−1i-1i−1，变成统计 fi=rf_i=rfi =r 的数量。但是无疑还是困难的……吗？
注意到，maxi=lrPi−mini=lrPi≥r−l+1\max_{i=l}^r P_i-\min_{i=l}^r P_i\ge r-l+1maxi=lr Pi −mini=lr Pi ≥r−l+1，也就是说，如果存在 fi=rf_i=rfi =r，那它一定是最小值！
现在问题就转化成了求全局最小值和最小值出现的次数了，线段树秒了。
O(nlogn)O(n\log n)O(nlogn)。
P4147
笛卡尔树大学习。
时间复杂度：O(n)O(n)O(n)。
P3960
注意到题目说的是全体同学都要判断，实际上真正移动的只有第 xxx 行第 (y,m](y,m](y,m] 列往左移一位，第 mmm 列第 (x,n](x,n](x,n] 个往上移一位，最后把 (x,y)(x,y)(x,y) 加到最后。
看上去很难，但是注意到移动前后位置都是连续的，所以我们可以看作单点增删、查询排名。
所以我们可以维护每一行前 m−1m-1m−1 个点，再单独维护最后一列，通过排名进行操作。
如果只是这样的话就能开 n+1n+1n+1 个 Treap 做了，但是注意到 n,m≤3×105n,m\le 3\times 10^5n,m≤3×105，如果真的开的话就有 9×10109\times 10^{10}9×1010 个点，显然开不下。
所以满足这题的最好的数据结构是动态开点线段树。
注意值域要多开至少 2q2q2q；long long 要开全。
时间复杂度：O(nlogn)O(n\log n)O(nlogn)，假设 n,m,qn,m,qn,m,q 同阶。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以下是 DP 题。
P1858
这有青？这有青？这有青？
就是记录下前 iii 个物品容量为 jjj 的前 kkk 优解。转移可以归并排序。做完了。
O(nmk)O(nmk)O(nmk)。
P2851
做法是显然的。对着 FJ 的钱跑多重背包，对着找的钱跑完全背包即可。假设枚举钱的上界为 LLL，则可做到 O(nLVilogCi)O(nLV_i\log C_i)O(nLVi logCi )。难的是上界应该怎么估算。其实对着时间空间限制极限卡即可
感性推测一下，LLL 应该不会离 ttt 太远。事实上，L≤t+2maxV2L\le t+2\max V^2L≤t+2maxV2。下面给出证明。
首先证明子问题：对于一个找零序列 SSS 满足 maxV∉S\max V\not\in SmaxV∈S，则 ∣S∣≥maxV|S|\ge \max V∣S∣≥maxV，或者存在找零序列 S′S'S′ 满足 maxV∈S′,∑S′=∑S,∣S′∣≤S\max V\in S',\sum S'=\sum S,|S'|\le SmaxV∈S′,∑S′=∑S,∣S′∣≤S，也就是一定有不劣的带 maxV\max VmaxV 的方案。
由抽屉原理可知，SSS 一定存在子序列为 maxV\max VmaxV 的倍数。具体证明是对 SSS 做个前缀和，至少有一对前缀和满足同余，差分回来这个子区间就一定是 maxV\max VmaxV 的倍数。这时，我们将这个替换成若干个 maxV\max VmaxV 一定不劣。
因此，一定存在一种情况，使得找零中 ≤maxV\le \max V≤maxV 的数量不超过 maxV\max VmaxV 个。
现在，我们看 maxV\max VmaxV 的数量。如果付钱时存在 maxV\max VmaxV，那可以两两消掉；否则一定存在一个付的数量超过 maxV\max VmaxV，根据上文也可以变成若干个 maxV\max VmaxV 消掉。
因此，maxV\max VmaxV 的数量也不超过 maxV\max VmaxV，也就是 L≤t+2maxV2L\le t+2\max V^2L≤t+2maxV2。
时间复杂度：O(n(t+maxV2)VilogCi)O(n(t+\max V^2)V_i\log C_i)O(n(t+maxV2)Vi logCi )。
P13957
神秘贪心题。
按价格排序。则有一个结论：免费拿的价格一定大于等于买的价格。如果知道这个结论，证明挺简单的，交换一下即可。
于是枚举价格跑背包即可。
O(nW)O(nW)O(nW)。
CF1442D
这道题的难点是注意到到序列有单调不减的性质。所以选一个数组一定会尽量拿完。
所以，这个就等价于选若干个整数组，再选一个数组的前缀。
我们枚举那个选前缀的数组，对其它数组跑一遍背包即可。这个显然是缺一分治板子。
O(nklogn)O(nk\log n)O(nklogn)。
P13323
回顾一下普通的 LCS。DP 的两维是选到第一个数组的位置和第二个数组的位置，然后看这两个位置是否相同来转移。
这个 DP 其实也类似，就是要处理不能完全匹配的情况。我们可以枚举 i,ji,ji,j 前面的区间，看看有多少个颜色相同的数，由它转移。
这样是 O(Tn2m2)O(Tn^2m^2)O(Tn2m2) 的，疑似能过，那我就不写优化了。
P7972
这个感觉非常困难，等理解了以后再写。
CF115E
定义 dp[i][j]dp[i][j]dp[i][j] 为前 iii 个点中，最后选的一段为 [j,i][j,i][j,i]。
显然有转移：dp[i][j]=dp[i−1][j]−Ai+∑Pi[j≤Li∧Ri=i]dp[i][j]=dp[i-1][j]-A_i+\sum P_i[j\le L_i\land R_i=i]dp[i][j]=dp[i−1][j]−Ai +∑Pi [j≤Li ∧Ri =i]；dp[i][i+1]=maxj=1idp[i−1][j]dp[i][i+1]=\max_{j=1}^i dp[i-1][j]dp[i][i+1]=maxj=1i dp[i−1][j]。
然后把第 iii 维删掉，就变成了区间加 xxx，前缀查询问题，直接上线段树。
O((n+m)logn)O((n+m)\log n)O((n+m)logn)。
P9691
定义 dp[i][j]dp[i][j]dp[i][j] 为……等等，这是道绿。
定义 dp[i]dp[i]dp[i] 为前 iii 个点中，恰好以 iii 结尾的。然后令 An+1=0A_{n+1}=0An+1 =0，答案为 dp[n+1]dp[n+1]dp[n+1]。
则有：dp[i]=minj=minRi<iLii−1dp[j]+Aidp[i]=\min_{j=\min_{R_i\lt i} L_i}^{i-1} dp[j]+A_idp[i]=minj=minRi <i Li i−1 dp[j]+Ai 。显然这个可以扫描线单调队列维护。
O(nlogn)O(n\log n)O(nlogn) 或 O(n)O(n)O(n)。
CF1129D
定义 dp[i]dp[i]dp[i] 为以 iii 结尾，右端点为 iii 的答案。
则有 dp[i]=∑j∈[i,j]中出现恰好一次的数的个数≤kdp[j−1]dp[i]=\sum_{j\in [i,j]中出现恰好一次的数的个数\le k} dp[j-1]dp[i]=∑j∈[i,j]中出现恰好一次的数的个数≤k dp[j−1]，非常抽象。如何维护？
令 lstilst_ilsti 为 iii 上一个颜色相同的下标。考虑开个 BBB，扫描 iii，然后将 Bi=1,Blsti=−1,Blsti2=0B_i=1,B_{lst_i}=-1,B_{lst^2_i}=0Bi =1,Blsti =−1,Blsti2 =0，然后就转化成了求 ∑∑k=jiBk≤kdp[j−1]\sum_{\sum_{k=j}^i B_k\le k} dp[j-1]∑∑k=ji Bk ≤k dp[j−1]，更加抽象了。
现在我们发现需要维护一个数据结构，支持加入 AiA_iAi ，BiB_iBi 前缀 +x+x+x，求全局 Bi≤kB_i\le kBi ≤k（kkk 为常数）的和。那咋办？
遇事不决，考虑分块。然后你就会发现有个 O(nnlogn)O(n\sqrt{n\log n})O(nnlogn ) 的做法。不想写了。
P14347
这题神了。无法比较这题和一般 CF Div2 B 的难度。
首先注意到先覆盖再取反是不劣的。然后考虑 DP。
我们会发现 DP 作用在一个点上，最多只有 666 种状态。然后暴力枚举状态转移即可。
O(nk2)O(nk^2)O(nk2)，其中 k=6k=6k=6。
P6239
注意到连边数是偶数，启发我们往异或角度思考。
定义 dp[i][j][mask]dp[i][j][mask]dp[i][j][mask] 为前 iii 条边，连了 jjj 个点，最后 kkk 个点连边数量为 maskmaskmask。然后枚举上一个的 maskmaskmask，长度取 popcount(mask⊕mask′)\text{popcount}(mask\oplus mask')popcount(mask⊕mask′)。然后注意到可以有重边，所以转移时得乘个组合数。这样可以实现 O(nm22k)O(nm2^{2k})O(nm22k)。
考虑多加一维 ttt 辅助转移，表示已经处理了第 iii 个点和后 ttt 个点的连边。这样，我们每次转移 ttt 只需要枚举 kkk 个点，看看是否连边即可。由于每次连边 jjj 那一维会 +1+1+1，所以直接“推”的方式转移没有后效性，还不用特殊处理重边，复杂度还更低。时间复杂度 O(nmk2k)O(nmk2^k)O(nmk2k)。
非常神秘啊，感觉不是人类能想到的。
期望 DP 式子 存档
对于一张图（可能有环），定义到达点 iii 的概率为 F(i)F(i)F(i)，第 ttt 次到达点 iii 的概率为 ft(i)f_t(i)ft (i)。这个 F(i)F(i)F(i) 相当于 ∑t=0∞ft(i)\sum_{t=0}^\infty f_t(i)∑t=0∞ ft (i)。
假设 iii 有 ppp 的概率到达 jjj。则 ft+1(j)f_{t+1}(j)ft+1 (j) 有 iii 贡献的 ft(i)f_t(i)ft (i)，所以总的 F(j)=∑t=0∞f(j)F(j)=\sum_{t=0}^\infty f(j)F(j)=∑t=0∞ f(j) 有 iii 贡献的 ∑t=0∞f(i)×p=F(i)×p\sum_{t=0}^\infty f(i)\times p=F(i)\times p∑t=0∞ f(i)×p=F(i)×p。
P3750
第一部分就是求出哪些需要按，哪些不需要按。这个很显然，从后往前扫，按所有 1 的即可。这是个调和级数，O(nlogn)O(n\log n)O(nlogn)。
第二部分就是求次数了。你注意到这玩意操作后有概率是错的，得多操作一次；有概率是对的，少操作一次。发现有环，感觉很难转移啊。
其实我们可以设 f(i)f(i)f(i) 为 iii 个需要按的操作一次后变为 i−1i-1i−1 个需要按的。则有 f(i)=in+n−in(1+f(i+1)+f(i))f(i)=\frac{i}{n}+\frac{n-i}{n}(1+f(i+1)+f(i))f(i)=ni +nn−i (1+f(i+1)+f(i))，移个项得 inf(i)=in+n−in(f(i+1)+1)\frac{i}{n}f(i)=\frac{i}{n}+\frac{n-i}{n}(f(i+1)+1)ni f(i)=ni +nn−i (f(i+1)+1)，即
f(i)=n−ii(f(i+1)+1)+1f(i)=\frac{n-i}{i}(f(i+1)+1)+1f(i)=in−i (f(i+1)+1)+1。
然后注意到 f(n)=1f(n)=1f(n)=1，所以从 nnn 开始递推即可。
时间复杂度：O(nlogn)O(n\log n)O(nlogn)，瓶颈在第一部分。
P3232
看到 m=O(n2)m=O(n^2)m=O(n2) 就说明复杂度一定不能带 mmm。
考虑求出经过每条边的期望次数，从小到大排序。
定义经过 iii 的期望次数为 f(i)f(i)f(i)，则有 f(i)=∑j∈vif(j)[j≠n]deg(j)f(i)=\sum_{j\in v_i} \frac{f(j)[j\not= n]}{\text{deg}(j)}f(i)=∑j∈vi deg(j)f(j)[j=n] 。
当然 f(1)f(1)f(1) 的值得额外加 111。
对于连接 x,yx,yx,y 的边，经过它期望概率为 f(x)[x≠n]degx+f(y)[y≠n]degy\frac{f(x)[x\not= n]}{\text{deg}_x}+\frac{f(y)[y\not= n]}{\text{deg}_y}degx f(x)[x=n] +degy f(y)[y=n] 。
然后呢？这个感觉不太好 DP 的样子啊。
考虑将 f(x)f(x)f(x) 当成未知数，高斯消元求线性方程组。由于这是由实际 DP 推出来的，所以显然唯一解。
时间复杂度：O(n3)O(n^3)O(n3)。
错排问题
UPD：原表述有误。
定义 f(i)f(i)f(i) 为钦定存在 iii 个下标满足 Ai=iA_i=iAi =i，剩下可选可不选（注意，同一种 AAA 的取值可能贡献不止 111 个方案）。显然它的数量为 (nk)(n−k)!{n\choose k}(n-k)!(kn )(n−k)!，容斥系数为 (−1)k(-1)^k(−1)k。所以答案为 ∑k=0n(nk)(n−k)!=∑k=0nn!k!\sum_{k=0}^n {n\choose k}(n-k)!=\sum_{k=0}^n \frac{n!}{k!}∑k=0n (kn )(n−k)!=∑k=0n k!n! 。
P1758
Ad-hoc 神题。
∑Ai2\sum A_i^2∑Ai2 转化成选两次相同的方案数，怎么想到的？
然后令第一次选到了 (i,j)(i,j)(i,j)，第二次选到了 (k,i+j−k)(k,i+j-k)(k,i+j−k)，就有了一个很显然的 DP。
毒瘤题还卡空间，记得滚动数组。
时间复杂度：O(n3)O(n^3)O(n3)。
CF1204E
为啥大家对我的风评都不太好，我线上是啥很爱说脏话的人吗？我不是始终贯彻良言一句三冬暖的思想吗？我为人彬彬有礼，对那些动不动就骂人的人特别反感！
为啥大家对我的风评都不太好，我线上是啥很爱说脏话的人吗？我不是始终贯彻良言一句三冬暖的思想吗？我为人彬彬有礼，对那些动不动就骂人的人特别反感！
为啥大家对我的风评都不太好，我线上是啥很爱说脏话的人吗？我不是始终贯彻良言一句三冬暖的思想吗？我为人彬彬有礼，对那些动不动就骂人的人特别反感！
考虑转化。注意到可以转化为一个二维网格，+1+1+1 往 yyy 轴一格，−1-1−1 往 xxx 轴一格。然后每个 iii 求的是说过程中到达并不越过 y=x+iy=x+iy=x+i 这条线的方案数。
虽然说求刚好到达要容斥，但是你注意到答案 ×i\times i×i，所以其实可以看成到达（可以越过）的方案数之和，不用容斥。
假设第一次到达的点为 (p,p+i)(p,p+i)(p,p+i)，然后我们按 y=x+iy=x+iy=x+i 对称一下，发现刚好会到达 (n−k,m+k)(n-k,m+k)(n−k,m+k)，而这个与到达 (m,n)(m,n)(m,n) 的点一一对应。所以就是求这个的方案数。注意，如果 (m,n)(m,n)(m,n) 本来就在另一边的话就不用对称了。
额我的代码好像 n,mn,mn,m 是反的，将就着看吧。
时间复杂度：O(n+m)O(n+m)O(n+m)。
