「SHOI2015」超能粒子炮・改
题目描述
曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明：超能粒子炮・改——一种可以发射威力更加强大的粒子流的神秘装置。
超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。它有两个参数 nn、kk，它会向每个编号为 00 到 kk（包含两端）的位置 ii 发射威力为 \mathrm{C}_n^i \mathbin{\mathrm{mod}} 2333Cnimod2333 的粒子流。
现在 SHTSC 给出了他的超能粒子炮・改的参数，让你求出其发射的粒子流的威力之和除以 23332333 所得的余数。
输入格式
第一行一个整数 tt 表示数据组数。
之后 tt 行，每行两个整数 nn、kk，含义如题面描述。
输出格式
tt 行，每行一个整数，表示其粒子流的威力之和模 23332333 的值。
样例
样例输入
1 | 3 |
样例输出
1 | 32 |
数据范围与提示
对于 $100\%$的数据，$t = 100000$，$n, k \leq 10^{18}$。
题解
这道题是一道很好的数学题，昨天的推导已经放了（那就再放一次凑数吧）
值得一提的是这题计算的时候有很多细节。。
比如说千万不忘了那些细节，什么$k < 0$ , $k=0$ , $n=0$
这些细节值45分！（狗日的多组数据。。）
还有就是细节推导错误，虽然昨天我贴的题解是对的，但我并没有看而是自己推的，结果应该是$\frac{k}{p}-1$块整体处理我忘了减1，然后不完整的块我加了1.。。。
Code：
1 |
|
无语，今天是真的废，三维偏序我调了一天了。。。哪种数据错我都分析了，只要重复元素多并且n较大就立刻完蛋，否则怎么也拍不出错来。。
这可咋整。。
感觉我的想法很正确，但就是不对，10分。。
完全想不到问题在哪，有点虚。
可能真的得抄题解才能过活的感觉。
我TM就不想炒题解，一下午没弄出来这破玩意！
【模板】三维偏序（陌上花开）
题目背景
这是一道模板题
可以使用bitset，CDQ分治，K-DTree等方式解决。
题目描述
有 nn 个元素，第 ii 个元素有 a_iai、b_ibi、c_ici 三个属性，设 f(i)f(i) 表示满足 a_j \leq a_iaj≤ai 且 b_j \leq b_ibj≤bi 且 c_j \leq c_icj≤ci 的 jj 的数量。
对于 d \in [0, n)d∈[0,n)，求 f(i) = df(i)=d 的数量
输入输出格式
输入格式：
第一行两个整数 nn、kk，分别表示元素数量和最大属性值。
之后 nn 行，每行三个整数 a_iai、b_ibi、c_ici，分别表示三个属性值。
输出格式：
输出 nn 行，第 d + 1d+1 行表示 f(i) = df(i)=d 的 ii 的数量。
输入输出样例
输入样例#1：
复制
1 | 10 3 |
输出样例#1：
复制
1 | 3 |
说明
$1 \leq n \leq 100000, 1 \leq k \leq 200000$
题解
我就打这个错误的，能过除了一堆重复的外所有数据的CDQ。
这起码是我自己想的。
Code:
1 | // luogu-judger-enable-o2 |
明明按理说有了重复元素只需要把每组元素中找出一个代表并且算出数量，然后CDQ，然后再把其他元素加在答案上就行，可是就是过不了！
时间宝贵，告辞。
算了还是认真学一下题解的做法吧，毕竟三维偏序还是很重要的。
开始重构代码。。这次一定要思路清晰哪怕写长一点也不要弄得很难调。
这也是个教训，假设调试时间过长但是调试难度过大，不妨换个思路哪怕是换个更好的实现都是不错的选择。
成功用归并排序实现了一下小常数的三维偏序（中间归并一开始居然先归并了左边，注意细节）
Code：
1 |
|
莫队算法学习笔记
Mostly from Sengxian and other great posts. Thanks
先声明一下，所有代码区间均为左闭右开 $[l, r)$，点的下标均从 0 开始。
概述
莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。
形式
普通莫队
对于序列上的区间询问问题，如果从 $[l, r]$的答案能够 $O(1)$扩展到 $[l - 1, r], [l + 1, r],[l, r + 1],[l, r - 1] $的答案，那么可以在 $O(n\sqrt n)$ 的复杂度内求出所有询问的答案。
实现：离线后排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案。
排序方法：设定块的长度为 $S$，按照 ($\lfloor\frac l S\rfloor, r$) 二元组从小到大排序。
复杂度分析：设序列长度为 $n$，询问个数为 $m$。可以发现从 $(l_1, r_1)$ 转移到 $(l_2, r_2)$ 的代价为他们之间的曼哈顿距离。对于每一个询问序列中的每一个块（第一关键字相同），整个块内纵坐标最多变化 $n$ 长度（纵坐标必然单调不减），对于每个询问，横坐标最多变化 $S$。一共有 $\frac nS$ 个块，相邻块之间转移的复杂度为 $O(n)$，所以复杂度为 $O(\frac {n^2} S + mS + \frac {n^2} S)$，不妨$n, m$ 同阶，取 $S = \sqrt n$ 时可达到最优复杂度 $O(n\sqrt n)$。
伪代码
1 | int l = 0, r = 0, nowAns = 0; |
带修改莫队
考虑普通莫队加入修改操作，如果修改操作可以$O(1)$的应用以及撤销（同时也要维护当前区间的答案），那么可以在 $O(n^{\frac 5 3})$ 的复杂度内求出所有询问的答案。
实现：离线后排序，顺序遍历询问，先将时间转移到当前询问的时间，然后再像普通莫队一样转移区间。
排序方法：设定块的长度为 $S_1$ 和 $S_2$，按照 ($\lfloor\frac l {S_1}\rfloor, \lfloor\frac r {S_2}\rfloor, t$) 的三元组小到大排序，其中 $t $表示这个询问的时刻之前经历过了几次修改操作。
复杂度分析：考虑询问序列中的每个小块，小块内每个询问的一二关键字相同。在这个小块内，显然 $t$ 最多变化 $m$，对于每个询问，$l, r$ 最多变化 $S_1$ 和 $S_2$，一共有 $\frac {n^2} {S_1S_2}$ 个这样的块，相邻块之间转移的复杂度为 $O(n)$（这里指的三个指针的转移复杂度，不难理解吧？），总复杂度就是 $O(mS_1 + mS_2 + \frac {n^2m} {S_1S_2} + \frac {n^3}{S_1S_2})$，不妨设 $n, m$同阶，取 $S_1 = S_2 = n ^ {\frac 2 3}$ 时可达到最优复杂度 $O(n^{\frac 5 3})$
原作者Sengxian的分析好棒哦，让每个块组合（有$\frac{n^2}{S_1S_2}$个）的$l,r,t$的复杂度均达到最大。
我们还有一种简单些的。
考虑每个左端点的块，右端点必定单调不减，$t$每个询问最坏是$O(m)$
设块长$S$,有$n/S$块
因此右端点的复杂度是$2\frac{N^2}{S}$
左端点每次在块内最多变化$S$，所以复杂度是$O(mS)$
所以最后复杂度就是$O(mS+2\frac{N^2}{S}+m^2)$
恭喜喜提时间复杂度爆炸！
所以我们怎么优化$t$的复杂度呢？
我们需要将$r$也分块，可以证明最后块长和左端点一样（主要是懒得再写一个字母了qwq）
我终于体会到什么叫做平衡了，我们在普通莫队之所以不把第一维严格升序，是因为第二维复杂度会爆炸。
因此我们让一二维的指针每次都保持在一个可以接受的复杂度，化乘法为加法。尽量优化了询问间的曼哈顿距离。
我居然用了这么久才想明白这个问题。显然上面的推导十分的高明。
不过既然块之间的复杂度转移是$O(n)$,那最后的复杂度应该是
$O(mS_1 + mS_2 + \frac {n^2m} {S_1S_2} + \frac {n^3} {S_1S_2})$
反正最后确实算的都对。
我个sb又花了2018.12.24的一晚上搞明白这东西。。。。。
啊，这位作者居然告诉我真是写错了，那我这个应该是对的。
突然挺高兴。
Code:
1 | int l = 0, r = 0, t = 0, nowAns = 0; |
树上莫队
对于树上的路径询问问题，如果能够在 $O(1)$ 的时间内加入、删除一个点的贡献，那么就可在 $O(n\sqrt n)$ 的复杂度内求出所有询问的答案。
实现：离线后排序，顺序遍历询问，暴力转移路径。
如何转移路径？设 $T_u$ 为 $u$ 到根的路径上边的集合，那么 $u$ 到 $v$ 的路径上边的集合就是 $T_u \bigtriangleup T_v$（$\bigtriangleup$ 是对称差）。我们要从$ u\rightarrow v$ 转移到 $u’\rightarrow v’$，等价于这样的转移：
$T_u \bigtriangleup T_v \rightarrow T_{u’} \bigtriangleup T_{v’}$
根据对称差的性质，有 $T_u \bigtriangleup T_u \bigtriangleup T_{u’} = T_{u’}$，所以只需要如下变换即可：
$T_u \bigtriangleup T_v \bigtriangleup (T_u \bigtriangleup T_{u’}) \bigtriangleup (T_v \bigtriangleup T_{v’}) = T_{u’}\bigtriangleup T_{v’}$
落实到程序上面，用 $\mathrm{in}[u]$ 记录点 $u$ 到父亲的边有没有被算进集合，从 $u\rightarrow v$ 转移到 $u’\rightarrow v’$ 的时候，暴力遍历路径 $u \rightarrow u’$ 和路径 $v \rightarrow v’$ 上的边，如果一条边已经加入，那么删掉它，如果没有加入，就加入它。这样就实现了对称差运算。
排序方法：按照 BZOJ 1086 的方法将树分块，设定块的大小为 $S$。按照 $(\mathrm{blockID}(u), \mathrm{dfn}(v))$ 的二元组从小到大排序。
复杂度分析：有两种块，一个是树上的块，一个是询问序列中的块（第一关键字相同）。我们单独考虑询问序列中的每个块。每个询问中的 $u$ 属于同一个树上的块。先考虑对于 $u$ 的移动，由于树上的块内任意两个点之间的路径长度是 $O(S)$ 的，所以每个询问，$u$ 点移动的路径长度为 $O(S)$。对于 $v$ 的移动，块内每个询问的 $\mathrm{dfn}(v)$ 是递增的，我们知道，顺序走一边 DFS 序上的每个点，相当于每条边都被走了 2 次，所以每个块中 $v$ 移动的路径长度是 $O(n)$ 的。一共有 $O(\frac n S)$) 个块，相邻块之间转移的复杂度为 $O(n)$，总复杂度：$O(mS + \frac {n^2} S + \frac {n^2} S)$，不妨设 $n, m$ 同阶，取 $S = \sqrt n$ 可达到最优复杂度 $O(n\sqrt n)$。
Code:
1 | int u = 0, v = 0, nowAns = 0; |
树上带修改莫队
考虑树上莫队带修改，如果能$O(1)$ 的应用以及撤销修改，那么可以在 $O(n^{\frac 5 3})$ 的复杂度内求出所有询问的答案。思路与普通带修改莫队是类似的。
实现：离线后排序，顺序遍历询问，先将时间转移到当前询问的时间，接着暴力转移路径。
排序方法：将树分块，设定块的大小为$S$。按照 $(\mathrm{blockID}(u), \mathrm{blockID}(v), t)$ 的三元组从小到大排序。
复杂度分析：我们考虑询问序列中的每个块（一二关键字相同），每个询问 $u $和 $v$ 移动的距离都是 $O(S)$ 的，整个块时间最多变化 $m$。一共有 $O(\frac {n^2} {s^2})$ 个块，相邻块之间转移的复杂度为 $O(n)$，总复杂度：$O(mS + mS + \frac {n^2m} {s^2} + \frac {n^2m} {s^2})$，不妨设 $n, m$同阶，取 $S = n ^ {\frac 2 3}$ 时可达到最优复杂度 $O(n^{\frac 5 3})$。
Code:
1 | int u = 0, v = 0, t = 0, nowAns = 0; |
还有四道例题尽在：https://blog.sengxian.com/algorithms/mo-s-algorithm
好吧说实话我好像只看懂了第一个，明天做道莫队的题。。