lxl分块糊做

[Ynoi2017] 由乃打扑克

me

想到了二分这个值+分块去找\(\leq\)这个数的数的数量，复杂度\(O(Q\log^2 N\sqrt N)\)，然后块内可能用\(multiset\)或者啥来维护

tj

更优的做法是块内维护一个排好序的序列，不过硬要说和\(multiset\)本质确实一样，但是这样常数和写法上会优的多

CodeChef Chef and Churu

me

对函数的下标分块，然后对每个块内维护两个序列，一个以\(l\)从小到大排序，一个以\(r\)从大到小排序

然后修改时，可以把所有函数都\(+y-a_x\)，然后再把那些\(r<x\)或\(l>x\)的函数的值\(+a_x-y\)，有个很好的点就是这两个条件只会至多满足一个，这个就可以对于每个块算出块的答案，然后给两个序列的最后一个满足条件的挂上一个\(tag\)

查询的时候整块直接用存的那个值即可，散块就可以遍历块对应的两个序列，然后算\(tag\)的贡献

\(O(Q\sqrt N\log N)\)

tj

对下标分块，然后数组和函数都分块

函数查询\([l,r]\)可以变成查询\([l,n]-[r+1,n]\)，于是可以给\([l,n]\)的数的\(tag+1\)，\([r+1,n]\)的\(tag-1\)，这个\(tag\)表示一个数的值被计算的次数

然后函数的块要维护整块的答案，查询到整块就用函数的块

查询到散块的时候，可以用数组的块来\(O(1)\)的查询

复杂度\(O(Q\sqrt N)\)

Luogu3863 序列

me

不会喵

tj

以下标为一个轴，时间为另一个轴，然后值为此时间下此下标上的值

可以发现修改是修改的一个矩形，查询的是一个区间

于是可以扫描线+分块维护

\(O(Q\sqrt N\log N)\)

「BZOJ2038」小 Z 的袜子

me

一开始一直在想分块，然后感觉分块不可做，突然想到为啥不离线呢，于是就是莫队板子

\(O(Q\sqrt N)\)

[AHOI2013]作业

me

莫队，然后再用个树状数组来记录答案

\(O(Q\sqrt N\log N)\)

tj

对值域也分块，就可以去掉\(log\)了

[Ynoi2016]这是我自己的发明

me

首先可以用\(dfn\)序把子树变成区间，然后一开始钦定\(1\)是根，如果后面根变成\(x\)的孩子\(y\)的子树中的一个点，对于\(x\)，它的新子树区间就是整个区间除去\(y\)子树的区间

那么现在就相当于查询两个区间\([a,b]\)和\([l,r]\)的\(\sum c_{[a,b]}(i)\times c_{[l,r]}(i)\)，于是可以类似于Luogu3863 序列，以一个查询为\(x\)轴，另一个为\(y\)轴，得到一个\(n\times n\)的矩阵，然后\(a_{i,j}=[col_i==col_j]\)，查询即询问左下角为\((a,l)\)，右上角\((b,r)\)的矩形的权值和

然后矩形的权值和可以用二维前缀和拆分成四个左下角\((1,1)\)，右上角为\((x,y)\)的查询，那么原问题就被拆分成了许多个这样的查询，这个可以莫队维护

\(O(Q\sqrt N)\)

bzoj3920 Yuuna的礼物

me

区间查询可以莫队维护，然后\(k1\)可以数状数组/分块维护，\(k2\)可以\(set\)维护。。。？写的时候突然发现不行，幽默

tj

很牛！考虑用点来表示权值为\(v\)的点出现了\(k\)次，那么共有\(n\)个点，将这些点按照出现次数为第一关键字，权值为第二关键字排序，然后对这些点进行分块即可

\(O(Q\sqrt N)\)

[JOI2014] 历史研究（歴史の研究）

me

回滚莫队，\(O((N+Q)\sqrt N)\)

tj

回滚莫队是其中一个做法，还有普通莫队的做法

和bzoj3920 Yuuna的礼物类似，用点来表示权值为\(v\)的点出现了\(k\)次，那么共有\(n\)个点，将这些点按照\(v\times k\)排序，对这些点分块，那么用莫队维护区间，此时答案就是这\(n\)个点中，最靠后的存在的点

HNOI2016大数

me

就求区间内前缀余数相同的对数即可，莫队，\(O(Q\sqrt N)\)

tj

\(p=2/5\)的情况比较特殊，因为它们和\(10\)不互质

[IOI2009]regions

me

这怎么分块，都不让离线

tj

原来是根号分治，你说这个我就懂了嘛，幽默，根号分治算分块吗\(/fn\)

考虑当\(r_1\)或\(r_2\)中的某一个大小大于\(B\)时，因为最多只存在\(\frac nB\)个这样的地区，所以考虑预处理

预处理\(r_1\)时，若为地区\(V\)，可以直接\(dfs\)，然后\(cnt\)记录\(x\)的祖先中有几个属于地区\(V\)的，然后记录进\((V,a_x)\)

预处理\(r_2\)时，若为地区\(V\)，依旧\(dfs\)，记\(cnt\)为\(x\)的子树中有几个属于地区\(V\)的，然后记录进\((a_x,V)\)

这部分复杂度\(O(\frac{n^2}B)\)

然后若两个都大小小于\(B\)，则考虑\(dfn\)序，若\(y\)是\(x\)的孩子当且仅当\(dfn_y\in[dfn_x,dfn_x+sz_x-1]\)，那么考虑对地区\(r_1\)维护两个序列，一个以\(dfn_x\)排序，一个以\(dfn_x+sz_x-1\)排序，\(r_2\)维护一个以\(dfn_y\)排序的序列，那么对于\(r_1\)中的点\(x\)，在\(r_2\)中合法的\(y\)的范围为第\(l\)个到第\(r\)个，那么\(x\)的贡献为\(r-l+1\)，拆开成\(r+1\)和\(-l\)，\(r+1\)由\(r_1\)的第二个序列负责，\(-l\)由第一个序列负责，然后双指针即可

复杂度\(O(QB)\)

因为\(N\)和\(Q\)同阶，所以\(B=\sqrt N\)，总复杂度\(O(N\sqrt N)\)

SHOI2006 Homework

me

感觉对\(Y\)分块，然后通过什么性质每次\(X\)去更新\(Y\)的答案没啥出路，考虑每次对\(Y\)去找\(X\)

首先\(Y\leq B\)的，只有\(B\)个，这个可以每次用\(X\)去更新\(Y\)的答案

对于\(Y>B\)的，设\(X=k\times Y+r\)，则只有\(\frac VB\)个\(k\)，那么考虑对\(Y\)去找\(X\)，枚举\(k\)，找到\(\geq k\times Y\)的最小的\(X'\)，然后答案取\(min(ans,X'-k\times Y)\)，可以用分块做到\(O(1)\)查询，\(O(\sqrt V)\)维护

\(B\)取\(\sqrt V\)，复杂度\(O(N\sqrt V)\)

[Ynoi2015] 此时此刻的光辉

me

对于\(c\leq B\)的，只有\(B\)个，预处理

对于\(c>B\)的，最多走\(\frac nB\)步，直接跳

\(O(N\sqrt N\log N)\)

tj

可以长链剖分做到\(O(1)\)求\(k\)级祖先，于是\(O(N\log N+N\sqrt N)\)

具体的大概就是对于每条长链，记录链顶向上的第\(k\)个点与链上第\(k\)个点，\(k\leq\)这条长链的长度

题解 P5903 【【模板】树上 k 级祖先

「Ynoi2015」 盼君勿忘

me

莫队维护区间，\(ans=\sum c_i\times(2^{len}-2^{cnt_i})\)

把\(cnt_i\leq B\)的放到一起，然后算答案的时候枚举\(cnt_i\)算即可

\(cnt_i>B\)的最多\(\frac nB\)个，这个单独算即可

\(O(Q\sqrt N\log N)\)

tj

优化了快速幂，用了光速幂，具体就是预处理出\(pw_i\)，\(i\in[1,B]\)，以及\(pw_{i\times B}\)

\(O(Q\sqrt N)\)