总榜 rk6，但是发现只需要改 3s 的 T1 就可以拿到 rk2，但是没有如果。
赛时
T1 怎么像是原啊，算了反正不记得。
总结关键词：斜率为非负整数，直线在某区间内的高度有限制。
想了想，发现斜率最大值是 \(m\over n\) 级的，所以后面显然可以再乘上一个 \(n\)。
于是有思路：枚举斜率 \(k\)，对每个元素计算想让直线经过它时所需要的 \(b\) 值，找到出现次数最多的那个 \(b\) 值，就得到答案了。
umap 担心会炸空间，所以我用正常数组存 \(b\)，每次清空就行了。
写写写，大样例过了，好了不管了。
T2 只会暴力啊。
继续想，发现我可以预处理正常删除到某个状态时剩余元素的个数。
发现每次可以 \(\mathcal{O}(n^2)\) DP 啊，我只需要一个 \(dp_{i,j}=\max(\min(dp_{i-1,j},dp_{i,j-1}),c_{i,j})\) 就行了，这样总复杂度是 \(\mathcal{O}(n^3)\) 的，有一个优秀的 50pts。
写写写，大样例过了（因为没给 \(5000\) 的样例）。
继续想，每次对 DP 数组的修改是不是有限的状态啊？然后就想到了 DDP，所以我不想了。
看 T3，发现我会 \(\mathcal{O}(n^4)\) 暴力。
写写写，小样例过了。
是不是只有颜色相同的那些点才是有用的啊？不对，随便一个颜色全相同的数据就能卡掉我。
看着可以用 LC 优化，但是我忘了怎么写 LC 了，跳了跳了。
看 T4，我会一个复杂度 \(\mathcal{O}(nk\log (nk)+mk\log(nk))\) 的算法。
写完以后发现不过样例。
打表，哎我的 size 怎么删除一次减少了 \(3\) 啊，我用的是 multiset 啊？
难道删一次会全删了么？好像还真是。
怎么办呢？我可以存结构体，哈希一下，就可以了。
写写写，怎么又挂了？
我突然想起来了 \(\color{red}血淋淋的教训\)，哦还真是这问题，改完就可以了。
比赛还剩 10min，摆了。
赛后
吃饭的时候发现 T1 我的桶里面会有负数，希望不会挂太多吧。
评测，看榜，HDS 用手法多拿了一堆分。
我 T1 水到了 55pts（小L：这都能 55pts？
最终是总榜 rk6。
T1 下发代码，加上偏移量，提交，通过，然后我就有 200pts 了，唉。
T4 告诉我们一定要记住 \(\color{red}血淋淋的教训\)。
但其实也不用，删除的时候我们去删迭代器就可以了，比如 se.erase(se.find(k))。
听讲评，T2 抽象模型以后类似网格图，每次修改确实是有限的，但是我那个思路不好走下去。
T3 如果把两步分开的话就有一个很简单的 \(\mathcal{O}(n^3)\) 算法了，加上 LC 就能过了啊。
T4 听懂了，大致就是每 \(k\) 个元素分块，发现块内随便做，块与块之间有最大值的性质，也能用线段树做，单点修改也能改。
只能说还行吧。
标签：25,2024.11,例过,NOIP,T4,T1,写写,mathcal,dp From： https://www.cnblogs.com/Lydic/p/18567515