《考 场 魔 怔 人》

· · 个人记录

以下内容节选自鄙人考场 T4 部分代码

//D - ODT
//使用ODT维护区间是否排序，排序就是区间推平操作，
//排序的时候把若干已排序好的子段直接合并，复杂度 O(nk)，其中k为子段数

//好像可以，只不过ODT我不会，屮
//如果我拿分块维护区间推平的话（分块怎么这么万能）
//那就是小常数带根号
//排序的话好像也不是直接推平，是赋颜色，颜色就是操作编号，
//但是这样给定一个乱序的初始数列然后直接全局排序就炸了，
//所以设置一个边界值，如果 k 过大就直接 sort，
//但是这样最优也是 O(nmk)，只是把 logn 搞小了点，寄

//这玩意排序肯定不是真排序，要不然不会只问一个位置的值，所以说他肯定要离线逆推
//把答案从 1 枚举到 n，每次排序可以筛掉一些值，比如样例
//最后一次排序 2->4升序，那么第 3 个值就不可能是1，好，然后呢？好，换思路。

//对于每个值可以求出一个“偏移量”，就是值 - 下标，升排就是在降低这个偏移量的 总和 
//降排就是搅和这个偏移量，让他更大。
//整个数列总的偏移量的和一定为 0 ，有点像势能，
//所以升排是降低势能差，降排是升高势能差。
//求证：每次升排势能为0的不动，其余的势能取平均，无法平均，我也不知道。
//好，不错，好，换思路。

//这玩意应该是数据结构题吧，，，
//如果是数据结构的话，那么数据结构里维护的是什么，

//哦T1好像是卡特兰数，但是那玩意我公式忘了，悲
//组合数取模我也忘了，不错，更释然了

//T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 T4 
//嗯我会主席树，我可以区间排名，嗯嗯嗯嗯
//T4是个什么玩意，，， 
//继续筛的思路，也许可以逆序处理出在排序前这个值是那个区间的区间第K小值，
//然后DFS？，他不是数据结构题吗？？
//这玩意6秒，10^5，感觉是 O(nlog^2n)，树套树倒是可以处理二维点对
//但是排序怎么搞啊，排序要更改O(n)个点对，TTTTTTT。
//所以不更改点对，逆序处理，每次 O(log^2n) 的时间追踪排序前的位置。
//好，好，好，不会，输，输，输