「Comet#13F」「蓬莱的弹枝 -七色的弹幕-」

一道只有标题和东方有关系的大分块。

[CometOJ contest#13 F]

题意简述

维护一个长为 n 的序列,要求支持查询距离某个数 ax 距离最近的相等的数与这个数的距离,区间加一,区间左移一位(即 aiai+1(lir),aral )。

1n,m,ai105

主要思路

所以平衡树怎么做这个玩意?

分块,设每块长度为 K 。每个块内记录:

  • beg :这个块第一个数的下标减一
  • cnt :这个块的长度
  • tag :这个块的加标记
  • num :块中元素(存储的值为真实值减去 tag ,存储的数对应原序列中的 [beg+1,beg+cnt]
  • fixfixval 表示块内值为 val (真实值为 val+tag )的数的数量

查询

查询时,寻找这个位置 x 所在的块 Bx ,先在这个块内找有没有相同数;再分别遍历 Bx 后面与前面的块,找到后面与前面分别第一次出现 ax 的块(由于存储了 fix ,可以 O(1) 判断一个块内有没有 ax),在块内暴力寻找 ax 出现的位置更新答案。

这样得到三组结果,取最优即可。一次时间复杂度 O(K+nK)

区间加

经典操作。散块暴力整块打 tag 即可。一次时间复杂度 O(K+nK)

区间左移

设区间左移 [l,r] 时,最前和最后的要修改的块分别为 BlBr

官方题解中,每个块的大小是定的。这样使用块状数组,每次左移即对于 [Bl,Br] 中的每个块,将弹出一个数字和插入一个数字,块大小仍然不变,只需处理修改块的 beg 即可。发现散块是在中间插入与弹出,可以暴力处理;整块是在两端插入与弹出,可以 O(1) 搞。一次时间复杂度是 O(K+nK)

这样写比较方便,代码也比较短。

然而本人将此题当作块状链表的例题来做。即完全按照题意,每次左移将块 Bl 中对应序列中下标为 l 的数弹出,其他块不变,然后插入到块 Br 中对应序列中下标为 r 的数后面。

由于一个块大小减少 1 ,一个块大小增加 1 ,所以当一个块大小过大 ( cnt>2×K ) 或过小 ( cntK2 ) 时,将这个块分裂成两个块与后一个块合并(若合并后 cnt>2×K ,也不应合并,应将后一个块前端部分移至该块后端使这两个块的大小较为平衡)。

最后也能推出单次时间复杂度为 O(K+nK)

所以 Kn 时,时间复杂度取到最优为 O(nn) 。这题不卡空间所以 Kn 空间上也不会有问题。

参考代码

然而我真就把这题当作块状链表的例题来做了,各种不熟练导致调了一下午。

一些细节详见代码与注释。

大量指针注意。

所以我第一题块状链表是不是还是写个「POJ 2887」Big String 啥的合适啊……

结果为什么写了这题之后马上又拿分块链表过了「SCOI 2013」多项式的运算呢……

Related Issues not found

Please contact @OkazakiYumemi to initialize the comment