五一集训Day5

五一集训Day5

day3是讲课。
昨天dls的题只改了t2，有点自闭...就不写总结了。

A

给出ab数组，a值域m，b值域1e9

q个询问，求(max _{i=v_{l}}^{v_{r}}left(sum_{j=l}^{r} b_{j} cdotleft[a_{j}=i ight] ight))

按照lr排序+莫队有80，很好想。（然而我对着不存在的分一直卡时间，最后交了个带freopen的成功爆0）

记录一下思考过程，考虑优化这个东西。我们知道莫队修改n根号n次，查询n次，考虑值域分块。可是单独的值域分块加减求最大值不好求，一直想到了考完。

这之间想到了模仿线段树，值域的每块开个set来修改，可是由于巨大常数，本地跑了20s+，就去颓了

然后去问van u群，粉兔说我知道你在说什么（zr可能存疑？），并给出了一个名词回滚莫队。之前只做过几道例题，并不知道实际用法。这个东西就是把删除操作不好做的莫队搞一个简单的可持久化，使得只有添加操作和回溯操作（记录一下之前的状态或者操作方向相反，但是不维护结果）。算法过程是对于左右端点同块的直接算，不同块的询问一起算左端点的块相同的，右端点单增，左端点只在块内移动，一块的总复杂度为(O(n))，总复杂度就为(O(nsqrt n))这个级别的（nm同阶），就做完了。

姿势水平还是不够高啊

B

根本没看

看了估计也不会

给一个序列p，每次把一些数提出来放到后面，相对顺序不变，求排成1,2,...n的最小次数

考虑(q=p^{-1})（映射？），发现一次操作即是把极长上升连续段的合并。然后通过讨论不同段的位置关系即可发现不同块的数之间操作序列一定不同（感性理解猜结论也可）

然后一共有ans次操作，左右两种情况，总操作序列方案数(2^{ans})。令k为初始段数，则(2^{ans}ge k)，即(ansge left lceillog_2 k ight ceil)。考虑构造出这个理论下界，能构造出来它就是严格下界。

一共要排log次，每次的段数一定减半。考虑把奇数段的数字放到偶数段之前（奇偶相同按照原本的顺序），那么每次相邻的奇偶段在q上就会合并。而且q下标是p的值，那么较小的数字为奇数，最后一定是从大到小。这样就构造完了。

C

70送分~

正解大概是考虑把限制放宽，然后除开全黑有单调不降的性质，双指针统计。细节有丶复杂，不写了。