BZOJ3339&3585 mex 莫队+树状数组 数据结构

BZOJ3339&3585 mex 莫队+树状数组

一开始想用动态开点线段树来维护最小未出现自然数,然而瞄了一眼题解告诉我会T掉,因为莫队算法(基本上)只适用于转移的复杂度为O(1)的操作,也就是说强行加个log2n比较难卡过去,所以考虑换用更高效的转移。 首先,即使是在极限情况下,我们最多只需要记录O(n)的出现信息,而不用考虑更大的数,因为最小未···
BZOJ2120&2453 数颜色 带修改莫队 数据结构

BZOJ2120&2453 数颜色 带修改莫队

带修改的莫队,在普通莫队的基础上增加了在时间轴上的滚动,将询问和修改分别记录,保存每个询问的左右端点,以及在当前询问之前进行了多少次修改,将块长设置为n^(2/3),保证理论时间复杂度是O(n^(5/3)),再将询问按照(左端点所在块,右端点所在块,时间),进行三元组排序,可以感性理解一下查询区间移···
BZOJ3289 Mato的文件管理 莫队+树状数组 数据结构

BZOJ3289 Mato的文件管理 莫队+树状数组

用的是莫队做法,考虑到这道题不带修改,所以将询问按照(左端点所在块,右端点)二元组排序,将块长设置为sqrt(n),可保证理论时间复杂度在O(n^1.5)左右。 再来想具体查询逆序对的方法:考虑到每次扩展或者缩减区间时都是在区间的两端进行,如果是逆序对,那只要查区间中比当前端点大/小的数的个数即可,···