NFLSPC #2 雪 题解

2019-11-28 22:46:56 By wzy

显然 所有操作和顺序无关 并且连续2次相同操作等于没有操作

称将第x个数开始的k个数改变状态"操作x"

考虑操作x和操作y(x<y) 做操作x和操作y等价于做所有的操作i和操作i+1(x<=i<y) 而做操作i和操作i+1 等价于将第i个数和第i+k个数改变状态

于是所有可能的场面为:

第一类 每次改变第i个数和第i+k个数的状态 最后得到的场面

第二类 先改变前k个数的状态 然后每次改变第i个数和第i+k个数的状态 最后得到的场面

第二类和第一类类似 我们只需要搞清楚第一类是怎么回事

把ai按模k余数分成k组(每组内按原顺序)每次的操作相当于改变某组内相邻两个数的状态

于是一个场面能被达到 当且仅当每组内有偶数个数被改了状态

我们每组独立考虑

假如组内有n个数 k个正数

如果k为偶数 肯定改变最大的k个数最优

如果k为奇数 有至多2种情况:改变最大的k-1个数 改变最大的k+1个数(要求k<n)

现在考虑如何维护修改 对每组数我们维护正数个数及正数和 并用一个数据结构维护每组数中正数的最小值和非正数的最大值

一个简单的数据结构选择是priority_queue 时间复杂度O(nlogn+qlogn)

$by\ \text{skyline}$

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。