整除分块

例：求解

由于\(\lfloor\frac{n}{i}\rfloor\)的取值最多有\(2\sqrt{n}\)种可能，只需要对每个取值考虑符合要求的i的区间。

若当前考虑到\(k=\lfloor\frac{n}{l}\rfloor\)，则需要找最大的r=l+d使得\(k=\lfloor\frac{n}{l+d}\rfloor\)

通过计算得出\(r=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor\)

线性基

若干数的线性基是一组数（这组数的个数不超过 \(log_2max\{a_i\}\) ）

线性基中元素 \(xor\) 出的数的值域与原来的数 \(xor\) 出的数的值域相同，故可以将原数组压缩为线性基来高效的解决一些与异或和相关的问题。并且，线性基的任一非空子集异或和不为 0 。如果线性基的大小和原数组一样，则 0 不能被异或出来，否则可以。（？）

线性基的构造法：对每一个数 \(p\) 从高位到低位扫，扫到其第 \(x\) 位为 1 时，若线性基 \(A\) 第 x 位为空，则将线性基该位赋值为 \(p\) ；否则令 $p=p\ xor\ A_x $，然后重复以上步骤。

两个线性基合并只需要将一个线性基中的元素加入到另一个线性基里即可。

注意：线性基的大小是一定的（？

例题：

【模板】线性基：求异或和最大值

从线性基高位往低位枚举，如果能使答案更大就异或。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
#define MAXN 55
ll a[MAXN];

ll c[MAXN];

inline ll P(ll A,int k) { return (A>>k)&1; }

int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (int i=1;i<=n;i++)
	{
		for (int x=50;x>=0;x--)
		{
			if (P(a[i],x)==1)
			{
				if (c[x]==0)
				{
					c[x]=a[i];
					break;
				}
				else a[i]^=c[x];
			}
		}
	}
	for (int i=50;i>=0;i--)
	{
		for (int x=i-1;x>=0;x--)
		{
			if (P(c[i],x)==1&&c[x]!=0) c[i]^=c[x];
		}
	}
	ll ans=0;
	for (int i=50;i>=0;i--) ans^=c[i];
	printf("%lld\n",ans);
	return 0;
}

求第k小异或和

（好像线性基可以直接这样构造？）
首先按上面的方法初步构造一个线性基，然后对于每个 \(A_i\) 从高位到低位枚举，如果枚举到第 \(j\) 位为 1 ，并且 \(A_j\) 不为空，就将 \(A_i=A_i\ xor\ A_j\)。这样得出来的线性基对于每个非空的 \(A_i\)，只有 \(A_i\) 的第 \(i\) 位为 1，根据这个优美的性质又可以解决很多问题x

对于这道题，只需要忽略 \(A\) 的空位，对 \(k\) 二进制拆分即可。

在无向连通图上求1到n最大异或和路径（不要求是简单路径）

先找出一条1到n的路径，然后BFS出附在这条路径上1到n的所有简单环，求出每条简单弧的异或和和第一条路径的异或和的线性基即可。

给定 S ,将 S 的所有子集（包括空集）的异或和按顺序排成一列，求 x 在数列中最早出现的位置

首先构造出线性基，容易求出 x 在去重后的异或和列中的位置。

然后还需要考虑每个数在异或和列中出现的次数。首先，列中的每个数都可以在线性基中被唯一表示，那么重复的部分就来源于线性基在 S 中的补集。

可以先将 x 用线性基唯一表示，然后考虑异或上 S 中任意一个异或和为 0 的子集。S 的异或和为 0 的子集异或上 x 的线性基表示，与合法方案一一对应（冗余一点讲就是包含了只在线性基中出现的元素的异或和、不在线性基中出现的元素的异或和、部分在线性基内，部分不在线性基内的元素的异或和）。

由于线性基在 S 中的补集的任意子集异或和都能被线性基唯一表示，所以 S 异或和为 0 的子集数量也即每个元素重复出现的次数为 \(2^{|S|-|B|}\)（其中 \(B\) 表示线性基的大小）

上树：查询链的子集最大异或和

子题：查询区间子集最大异或和

因为线性基是可以合并的，既然有结合律了那么就倍增吧

那么自然也可以上树倍增了

又因为线性基是可以合并的，既然有结合律了那么也可以线段树对吧

那么又可以上树树剖了XD

给一系列（ \(a_i\) , \(b_i\) ）求 \(1-n\) 的子集中 \(b_i\) 的和最大且其任意子集 \(a_i\) 异或和不为 0

贪心，按照价值 \(b\) 从大到小排序，将 \(a\) 依次加入线性基并统计答案即可。

正确性好像不够显然呀...owo

莫队

太久没写过了已经忘了所以稍微复习一下思想。

可以用来处理一个序列上多个区间的静态信息查询问题。经典例子是可以在很小的复杂度内完成区间端点指针的一次移动后的答案变化计算。

将区间分成 \(\sqrt{n}\) 块。把各个区间按照左端点所属的块为第一关键字，右端点的位置为第二关键字排序，这样处理后的区间按顺序处理可以达到 \(O(u(n)n\sqrt{n})\) 的优秀时间复杂度，此处 \(u(n)\) 代表一次指针移动计算的复杂度。

这里以一道大板题【小B的询问】为代码例：

len=sqrt(nlenth);
bool opreator < (const qwq &A,const qwq &B) { return (A.l/len==B.l/len) ? A.r<B.r : A.l<B.l; }
for (int i=1;i<=querynum;i++)
	{
		while (r<q[i].r) { r++; ans+=(2*cnt[a[r]]+1);cnt[a[r]]++; }
		while (r>q[i].r) { ans-=(2*cnt[a[r]]-1); cnt[a[r]]--; r--; }
		while (l<q[i].l) { ans-=(2*cnt[a[l]]-1); cnt[a[l]]--; l++; }
		while (l>q[i].l) { l--; ans+=(2*cnt[a[l]]+1); cnt[a[l]]++; }
		answ[q[i].id]=ans;
	}

树上莫队和欧拉序相关。