首先这是个傻子卡常题，反正我出着玩的。
题面：https://www.luogu.com.cn/problem/U669230
U669230 [Eloi Easy Round 2026] 与你相恋直到生命尽头
题目背景
我常常追忆过去。
我该在哪里停留？我问我自己。
冥思苦想终是没有答案，果然还是看百合吧。
百合牛逼。
题目描述
美美给席娜一个长为 \(n\) 的非负整数序列 \(a\)，并进行 \(q\) 次操作：
操作 \(1\)：给定 \(p,v\)，修改\(a_p=v\)。
操作 \(2\)：给定 \(k\)，询问这个序列的第 \(k\) 大的数，强制在线。
席娜忙着做饼干呢，所以把这个简单的问题抛给你啦。
为了小两口的幸福，请加油吧！
请注意非常抽象的时间空间限制以及数据分配。
由于没数据所以没有时空限制的地方，就写这里了。
时间限制：1000ms
空间限制：128MB
我不知道我的做法能不能卡过去这个时间，总之你 \(O(nlogn)\) 预处理的算法一定会被我想办法抬走（）
输入格式
第一行输入 \(n\) 和 \(seed\)，表示序列元素的个数和随机种子，我们给定一个伪随机函数 \(rand()\) 根据随机种子生成 \(a_i\)。
由于我连标程都还没写，反正你知道这是随机分布且压缩输入的就行，我暂时懒得提供随机函数。
第二行输入 \(q\)，表示操作个数。
接下来的 \(q\) 行，每行一个操作，见题目描述。强制在线，设上一次询问答案为 \(last\_ans\)，如果没有则为 \(0\)，\(p'=(p\oplus last\_ans\mod n)+1\)，\(v'=v\oplus last\_ans\mod 10^9\)，\(k'=(k\oplus last\_ans\mod n)+1\)。
输出格式
对每个操作 \(2\)，输出答案，一行一个整数。
输入输出样例 #1
输入 #1
依旧懒得写
输出 #1
依旧懒得写
说明/提示
对于所有数据，保证 $$1\leq k,p\leq n\leq 1.2\times 10^7,0\leq a_i,v< 10^9,1\leq q\leq 10^5$$。
同时保证修改操作也是完全随机生成的。
题解
下面设 \(M=10^9\)。
考虑不带修只有一组询问
如果带多组询问带修了快速选择算法显然没前途，我们选择值域分块。
先统计每个块有几个元素，然后找到 \(k\) 所在块，再开这个块的桶，\(O(n)\) 加入元素暴力扫描这个散块，\(O(max(n,sqrt(M)))\)。
考虑不带修多组询问强制在线
麻烦主要在于上一个做法已知 \(k\) 后还要 \(O(n)\) 加入元素，因为 \(10^9\) 的桶是不可接受的，有 \(\frac{M}{B}\) 个块，开个大数组存每个块的块内元素，可以通过统计每个块内元素个数找到块在数组左端点位置实现，空间和时间都是 \(O(n)\) 的。这个数组只是为了卡空间，你用 multiset 就给你卡飞。求出块间前缀和，然后 \(q\) 次查询二分 \(k\) 在哪个块，减去前缀得出在这个块内的排名，对这个块的元素倒出来桶排，由于值域均匀，一个块内期望 \(O(\frac{nB}{M})\) 个元素，时间复杂度 \(O(n+q(\log\frac{M}{B}+\frac{nB}{M}+B))\)。
考虑带修
显然的做法是把前缀和改成树状数组，预处理的时候树状数组是可以 \(O(n)\) 建树的。
还有个麻烦是修改，我们考虑懒标记，就是对每个块开两个链式前向星存删掉和新增的元素，到这个块之后再处理，由于均摊性质这个链式前向星每个块打的标记非常少，询问也是随机的所以完全不用管修改保留懒标记即可，于是我们就解决了这题，所以总复杂度依旧 \(O(n+q(\log\frac{M}{B}+\frac{nB}{M}+B))\)。
计算空间
这是个卡空间题，我们来算一下所占空间。
- 修改需要原始数组，\(\frac{1.2\times 10^7\times 4B}{1024^2}=46MB\)。
- 一维数组存块内元素，\(\frac{1.2\times 10^7\times 4B}{1024^2}=46MB\)。
- 块间树状数组，\(\frac{10^9\times 4B}{B\times 1024^2}=\frac{3814}{B}MB\)。
- 统计块内元素个数作为在大一维数组里的右端点，\(\frac{10^9\times 4B}{B\times 1024^2}=\frac{3814}{B}MB\)。
- 链式前向星懒标记，\((\frac{2\times 10^5+\frac{10^9}{B})\times 4B}{1024^2}=(0.4+\frac{3814}{B})MB\)。
- 桶排序的桶，\(\frac{10^9\times 4B}{B\times 1024^2}=\frac{3814}{B}MB\)。
可知可取 \(B=550\)。
计算时间
- 预处理扫两遍原始数组存入一维大数组再初始化树状数组，\(3n=3.6\times 10^7\)。
- \(q\)次询问主要开销在查询的桶排，懒标记处理以及构建桶几乎不计入时间，\(qB=5.5\times 10^7\)。
可知不怎么卡时间常数，我很善良的。