雅礼集训Day2T3 操作operation

长度为n的01串,m次询问,每次问一个区间,你选择P个长度为K的子区间,每个子区间的数会被取反一次,被多个子区间覆盖会被取反多次,要将这个子区间变为全是0,求P的最小值,无解输出-1.

n,m<=2000000


这题神就在它利用了区间取反的性质,将01串相邻的位置异或起来,可以发现选择一个区间i,j时只有(i-1,i),(j,j+1)的之间的异或值会改变,要让区间内都为0即都一样,那么盯着异或为1的消就行。O(n)

本文链接:https://my.lmcjl.com/post/19996.html

展开阅读全文

4 评论

留下您的评论.