一道只有标题和东方有关系的大分块。
题意简述
维护一个长为 n 的序列,要求支持查询距离某个数 ax 距离最近的相等的数与这个数的距离,区间加一,区间左移一位(即 ai←ai+1(l≤i≤r),ar←al )。
1≤n,m,ai≤105 。
主要思路
所以平衡树怎么做这个玩意?
分块,设每块长度为 K 。每个块内记录:
- beg :这个块第一个数的下标减一
- cnt :这个块的长度
- tag :这个块的加标记
- ⟨num⟩ :块中元素(存储的值为真实值减去 tag ,存储的数对应原序列中的 [beg+1,beg+cnt] )
- ⟨fix⟩ : fixval 表示块内值为 val (真实值为 val+tag )的数的数量
查询
查询时,寻找这个位置 x 所在的块 Bx ,先在这个块内找有没有相同数;再分别遍历 Bx 后面与前面的块,找到后面与前面分别第一次出现 ax 的块(由于存储了 ⟨fix⟩ ,可以 O(1) 判断一个块内有没有 ax),在块内暴力寻找 ax 出现的位置更新答案。
这样得到三组结果,取最优即可。一次时间复杂度 O(K+nK) 。
区间加
经典操作。散块暴力整块打 tag 即可。一次时间复杂度 O(K+nK) 。
区间左移
设区间左移 [l,r] 时,最前和最后的要修改的块分别为 Bl 与 Br 。
官方题解中,每个块的大小是定的。这样使用块状数组,每次左移即对于 [Bl,Br] 中的每个块,将弹出一个数字和插入一个数字,块大小仍然不变,只需处理修改块的 beg 即可。发现散块是在中间插入与弹出,可以暴力处理;整块是在两端插入与弹出,可以 O(1) 搞。一次时间复杂度是 O(K+nK) 。
这样写比较方便,代码也比较短。
然而本人将此题当作块状链表的例题来做。即完全按照题意,每次左移将块 Bl 中对应序列中下标为 l 的数弹出,其他块不变,然后插入到块 Br 中对应序列中下标为 r 的数后面。
由于一个块大小减少 1 ,一个块大小增加 1 ,所以当一个块大小过大 ( cnt>2×K ) 或过小 ( cnt≤K2 ) 时,将这个块分裂成两个块或与后一个块合并(若合并后 cnt>2×K ,也不应合并,应将后一个块前端部分移至该块后端使这两个块的大小较为平衡)。
最后也能推出单次时间复杂度为 O(K+nK) 。
所以 K 取 √n 时,时间复杂度取到最优为 O(n√n) 。这题不卡空间所以 K 开 √n 空间上也不会有问题。
参考代码
然而我真就把这题当作块状链表的例题来做了,各种不熟练导致调了一下午。
一些细节详见代码与注释。
1 | #include<bits/stdc++.h> |
所以我第一题块状链表是不是还是写个「POJ 2887」Big String 啥的合适啊……
结果为什么写了这题之后马上又拿分块链表过了「SCOI 2013」多项式的运算呢……