是的，我真开了这个坑。
分散层叠
给定 \(k\) 个长 \(n\) 的单调不降序列，\(q\) 次询问，每次给定 \(x\)，求所有序列中 \(x\) 的非严格后继的异或和，强制在线。
\(1 \leq k \leq 100,1 \leq n \leq 10^4,1 \leq q \leq 10^5\)。
写一个东西吧，感觉后面会有用。
这东西的暴力很简单，但是复杂度是 \(O(nk + qk \log n)\) 的，按理来说跑不过去，而分散层叠，能使这个复杂度优化到 \(O(nk + q(k+\log n))\)，能够通过这个题。
此处学习的是 cyffff的题解，我们考虑对这 \(k\) 个序列建线段树，每个叶子是一个完整序列。
一个很巧的方法，我们确定一个常数 \(K\)，在 pushup 的时候在两个儿子 \(K\) 个中只选一个，也就是每 \(k-1\) 个选一个，然后把两个新数组归并上来，并记录他们的来源和所在儿子中的位置，可以记为颜色 + 位置，左儿子为红色，右儿子为蓝色。
当 \(K=2\) 时，我们可以发现这样做的空间复杂度是 \(O(nk)\)，因为每次空间减少一半，加起来也就二倍左右，忽略不计。
考虑如何查询，我们可以在根节点的数组内二分先找 \(x\) 的后继，然后看在左右儿子内是否也有后继，具体来讲，假设我们在根节点二分到的节点是 \(p\)，且它为红色，那么它在左儿子中的后继位置一定在 \((p-K,p]\) 中，同理，如果为蓝色，那么一定在右儿子的 \((p-K,p]\) 的区间内，但是注意，因为我们是归并合并，每次可能会合并掉相同数，所以一个点可能既在左儿子中出现，也同时存在于右儿子中，这样归并下去就做完了。
代码一些点：
-
C++ 是由内置的归并函数的，
merge(l,l+cnt1,r,r+cnt1,a[rt])，这个合并减少了很多码量。 -
从左右儿子取点下来时要倒着拿，保证点的后置一定存在。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar('\n')
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define pdi pair<ll,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(register ll i = a ; i <= b ; ++ i )
#define Fo(a,i,b) for(register ll i = a ; i >= b ; -- i )
#define pb push_back
//#pragma GCC optimize(2)
using namespace std;
typedef int ll;
//typedef long long ll;
//typedef __int128 ll;
typedef double db;
inline void read(ll &opp){ll x=0,t=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){t=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}opp=x*t;return; }
inline void wr(ll x){if(x<0){putchar('-');x=-x;}if(x>9){wr(x/10);}putchar(x%10+'0');}
const ll N=105,L=1e4+5,K=2;
ll n,k,q,d,s[N][L];
struct Seg_Tree{#define ls (root<<1)#define rs (root<<1|1)struct node{ll val,pos,col,xp;node(ll v=0,ll p=0,ll c=0){val=v,pos=p,col=c,xp=-1;}inline friend bool operator <(const node &a,const node &b){return a.val<b.val;}};node pol[N*L*2],*now=pol;node *a[N<<2];ll siz[N<<2],ans;inline void pushup(ll root){static node l[L],r[L];ll cnt1=0,cnt2=0;for(ll i=siz[ls]-1;i>=0;i-=K) l[cnt1++]=node(a[ls][i].val,i,0);for(ll i=siz[rs]-1;i>=0;i-=K) r[cnt2++]=node(a[rs][i].val,i,1);reverse(l,l+cnt1),reverse(r,r+cnt2);siz[root]=cnt1+cnt2;a[root]=now,now+=siz[root];merge(l,l+cnt1,r,r+cnt2,a[root]);for(ll ls1=-1,rs1=-1,i=siz[root]-1;i>=0;--i)if(!a[root][i].col) ls1=i,a[root][i].xp=rs1;else rs1=i,a[root][i].xp=ls1;}inline void build(ll root,ll l,ll r){if(l==r){siz[root]=n;a[root]=now,now+=n;fo(0,i,n-1) a[root][i]=node(s[l][i],i); return;}ll mid=l+r>>1;build(ls,l,mid),build(rs,mid+1,r);pushup(root);}inline void ask(ll root,ll l,ll r,ll p,ll x){while(p&&a[root][p-1].val>=x) p--;if(l==r) return ans^=a[root][p].val,void();ll mid=l+r>>1;if(!a[root][p].col){ask(ls,l,mid,a[root][p].pos,x);if(a[root][p].xp!=-1) ask(rs,mid+1,r,a[root][a[root][p].xp].pos,x);}else{if(a[root][p].xp!=-1) ask(ls,l,mid,a[root][a[root][p].xp].pos,x);ask(rs,mid+1,r,a[root][p].pos,x);}}inline ll Ask(ll x){ans=0;ll p=lower_bound(a[1],a[1]+siz[1],node(x))-a[1];ask(1,1,k,p,x);return ans;}
}T;
signed main(){read(n),read(k),read(q),read(d);fo(1,i,k) fo(0,j,n-1) read(s[i][j]);T.build(1,1,k);ll las=0;fo(1,i,q){ll x;read(x);las=T.Ask(x^las);if(i%d==0) wr(las),pr;}return 0;
}
P9993 [Ynoi Easy Round 2024] TEST_133
序列，支持两个操作:
l r v对区间 \([l,r]\) 的所有数加 \(v\)。l r x对区间 \(a_i < x\) 的 \(i\) 位置查询历史最大和。
\(1 \leq n,m \leq 5\times 10^5 , |a| \leq 10^9\)，时限 40s。
发现这东西不同于线段树 3，而且给了 40s 的时限，所以直接考虑分块。
我们可以类比吉司机树， his_i 表示 \(i\) 点的历史和，histag 表示第 \(i\) 个块的历史最大 tag，其实一开始想再开一个笔记写吉司机树的，但感觉确实没啥可写的，如果有必要就放到之后再写吧。
由于是查询 \(a_i < x\) 的历史最大和，我们类比教主的魔法，对块内排序，然后维护 prehis 表示块内前缀历史和，每次查询时二分即可。
这题很好写，分块将每个部分的功能分开写会很简单并且逻辑很好串起来。
时间复杂度 \(O(n \sqrt n \log n)\)，最慢点跑了 23s。
code
P9994 [Ynoi Easy Round 2024] TEST_132
给定二维平面上 \(n\) 个点，点互不相同，点带权，支持两个操作:
v对 \(x=v\) 的所有点权值平方。v求 \(y=v\) 的所有点的权值和。
\(1 \leq n,m \leq 1.2 \times 10^6，1 \leq x,y \leq n\)。
正解好像是光速幂不带 \(\log\)，但是快速幂卡过去了。
考虑根号分治，按照 \(x_i\) 的数量 \(siz\) 分类，对于 \(siz \leq V\) 的，操作一暴力修改，操作二直接查询，复杂度 \(O(nV)\)，对于 \(siz > V\) 的，操作一打标记，操作二挨个查询，因为同 \(y\) 中最多只有 \(V\) 个 $x_i $ 数量 $ > V$ 的，因此复杂度是 \(O(\frac{n^2}{V} \log 10^9)\)，当 \(V = 3100\) 左右时能够通过。
注意模指数时用到费马小定理，模 \(mod-1\) 即可，以及一些什么乱七八糟的常数处理，比如减少数组调用，改用 vector 之类的。
卡了一下午常数，复杂度大概 \(O(n\sqrt{n \log V})\)。
code
P9989 [Ynoi Easy Round 2023] TEST_69
给定一个序列，支持两个操作：
l r x对 \([l,r]\) 中每一个 \(a_i \gets \gcd(a_i,x)\)。l r查询 \([l,r]\) 区间和。
\(1 \le n \le 2\times 10^5,1 \le x,V \le 10^{18}\)
沫队推荐 /bx/bx
显然是势能树均摊，拆质因子什么的都不太像，于是考虑记录 \(\operatorname{lcm}\)。
显然，\(\operatorname{lcm}\) 在线段树上很多时候会爆 long long，而因为 \(x \le 10^{18}\)，所以此时这个区间肯定不全是 \(x\) 的因数，继续向下递归即可。
反之，如果 \(\operatorname{lcm} \le 10^{18}\) 那么我们直接做 \(\gcd\) 即可，如果为 \(1\)，打上标记，否则继续下传，就类似这样一个过程，直到走完或走到叶子。
code
P9992 [Ynoi Easy Round 2024] TEST_130
给定一棵 \(n\) 个节点的有根树，定义 \(N(w,d)\)（\(w\) 为树的顶点，\(d\) 为非负整数） 为以 \(w\) 为根的子树中，到 \(w\) 距离不超过 \(d\) 的点构成的集合。
共 \(m\) 次询问，每次给出 \(w,d\) 查询 \(\{N(w',d')\mid N(w',d')\subseteq N(w,d)\}\) 的大小。
\(1 \le n,m \le 10^6\)。
简单题，由于是离线子树问题，我们就有很多解决方法。
下文用 \(D\) 替换原题面中的 \(d\)。
不妨分类讨论，对于当前点 \(u\)，能对其产生贡献的节点 \(v\) 首先满足 \(d_v \geq d_u\)，其次，能够发现从 \(u\) 向下走每次 \(D\) 的上限都 \(-1\)，于是我们对 \(md_v\) 讨论，即 \(v\) 子树内的最大深度。
有 \(md_v \leq d_u + D\) 时，那么这个点的贡献是 \(md_v -d_v + 1\)，否则，则贡献 \(d_u + D - d_v +1\)。
然后转成一个数点问题，这个很简单，先对 \(d_v \geq d_u\) 的限制差分，按照 dfn 序扫描线，然后 BIT 维护上述式子即可，将贡献以相反数的方式分别挂在 \(md_i\) 和 \(d_i\) 上，就能自动判断两者关于 \(d_u + D\) 的大小关系了。
本题卡常，可以合并一下 BIT 的修改操作，将存图换为前向星之类的方式通过。
code
P7880 [Ynoi2006] rldcot
给定一棵 \(n\) 个点的有权树，\(q\) 次询问，每次给定
l r，求：
集合 \(\{ dep(lca(i,j))| l \le i,j \le r \}\) 的大小。
\(1 \le n \le 1\times 10^5,1 \le m \le 5\times 10^5\)。
NOIP2024 T4 的前置题，扔到这里来了，题挺好。
考虑对每一个 \(lca\) 数点对数，考虑两个点对 \((a,b),(c,d)\) 且 \(a < c < d < b\)，那么称 \((a,b)\) 是被 \((c,d)\) 支配的，而被支配的点对显然是无用的，我们只要输出所有不被支配的点对即可。
回到操作，考虑 dsu on tree，我们每一次要取两个不在同一子树的点，假设当前取点 \(x\)，那么我们只要它的前驱和后继点即可，同 dsu on tree 的复杂度证明，每一个点最多被加入 \(O(\log n)\) 次，所以点对数是 \(O(n \log n)\)。
然后就是一个二维数点，扫描线 BIT 数数就好了。
卡常很烦，扫描线时可以倒着做，减少一次 BIT 的 ask，不建议把操作排序后指针扫，直接扔到 vector 里面按序列扫就能少两次 \(O(n\log n)\) 的排序。
复杂度 \(O(n \log^2 n + m \log n)\),500 ms 通过！
code
P3674 小清新人渣的本愿
给定长 \(n\) 的序列，\(q\) 次询问区间 \([l,r]\) 内能否选出两个数加/减/乘等于 \(x\)。
\(1 \le n,q,V \le 10^5\)。
怎么跑回来更这个了，lxl 出的就是 Ynoi。
bitset 配合莫队，首先这个问题我们做不到 \(\text{polylog}\)，于是考虑莫队，分别拆一下式子看看。
对于加法，即找出 \(a_i + a_j = x\)，即 \(a_j = x - a_i\)，我们不妨对值域开 bitset，那么这个操作相当于将 \(-a_i\) 的 bitset 左移 \(x\)，但是我们不好存负数，存 \(N-a_i\) 的 bitset 再右移 \(N-x\) 位就好了。
对于减法，找出 \(a_i - a_j = x\)，即 \(a_j = x + a_i\)，这个直接左移 \(x\) 位即可。
对于乘法，我们直接看因数，就可以做到 \(O(\sqrt V)\) 处理单组询问。
那么，再套上莫队维护区间 bitset，就可以做到 \(O(n\sqrt m + \frac{n^2}{w} + n\sqrt V)\)。
Submission
P4688 [Ynoi Easy Round 2016] 掉进兔子洞
给定长 \(n\) 的序列，每次询问给定三个区间，求三个依次去掉三个区间中都有的数后剩余的数的个数，注意不是直接去重。
\(1 \le n,q \le 10^5,1 \le V \le 10^9\)。
bitset 三部曲，这算带权 bitset 板子吧。
由于值域很大，我们需要离散化，但是因为是每次删数而非去重，我们不能简单的对相同数编号为同样的数。
其实这里很简单，我们离散化时不去重就好了，然后莫队加点的时候只需要将其依次放到这个数的末端即可。
然后我们只需要找出三个区间都有的数，bitset 直接做与就行了。
注意不能直接开 \(10^5\) 个 \(10^5\) 的 bitset，对询问分一下块就行了。
复杂度 \(O(n\sqrt m + \frac{n^2}{w})\)。
Submission
P5355 [Ynoi Easy Round 2017] 由乃的玉米田
同上上题，只多了除的询问。
也写一下吧，乘除法这类的自然往根号分治想。
对于 \(x \ge B\)，我们直接暴力看就行了，复杂度 \(O(\frac{n}{B})\)。
对于 \(x < B\)，我们考虑离线处理，不妨记 \(ls_i\) 表示 \(ls_i\) 是 \(a_i\) 与 \(a_{ls_i}\) 的商为 \(x\) 的最大位置，未确定顺序，这个很好处理，再做一下前缀 \(\max\) 就可以 \(O(1)\) 回答询问了，复杂度 \(O(nB)\)。
其实根本卡不满，\(B\) 取到 \(5\) 左右跑的最快。
Submission