各种小技巧

指数级搜索（exponetial search）

这是一种用于处理 $\operatorname{check}(l,mid)$ 时间复杂度为 $O(mid-l+1)$ 即时间复杂度和序列长度相关的搜索算法。

一般用于需要在序列上不断二分划分出一段段互不相交的合法区间的题目中。

发现二分的问题在于从 $i$ 出发找以 $i$ 开头的合法区间的右端点 $r$ 的时候时间复杂度为 $O((n-i)\log(n-i))$，总时间复杂度最坏为 $O(n^2\log n)$，无法接受。

不难发现问题在于二分的区间太大了，不妨先从小到大枚举 $j$，找到第一个满足 $\operatorname{check}(i,i+2^j-1)=true$ 的 $j$，然后在 $[i,i+2^j-1]$ 里二分，这样二分的时间复杂度就是 $O((r-i+1)\log(r-i+1))$ 也就是只和当前区间的长度有关，均摊时间复杂度即为 $O(n\log n)$。

for(int i=1;i<=n;i++)
{
    int rb=-1;
    for(int j=0;j<=20;j++)
    {
        int pre=min(i+(1<<j)-1,n);
        if(chk(i,pre))
        {
            rb=pre;
            break;
        }
    }
    if(rb==-1) break;
    int lb=i,nxt=0;
    while(lb<=rb)
    {
        int mid=lb+rb>>1;
        if(chk(i,mid)) nxt=mid,rb=mid-1;
        else lb=mid+1;
    }
    ans[++anscnt]=nxt;
    i=nxt;
}

$\gcd(a^x-1,a^y-1)=a^{\gcd(x,y)}-1$

证明：

$x\ge y\\\begin{aligned}&\gcd(a^x-1,a^y-1)\\&=\gcd(a^x-1-a^{x-y}\times(a^y-1),a^y-1)\\&=\gcd(a^{x-y}-1,a^y-1)\\&...\\&=a^{\gcd(x,y)}-1\end{aligned}$

大小 $\le k$ 的点覆盖的爆搜

每次找到还没被删掉的度数最大的点 $u$，若其度数 $\le 2$，则图为若干环和链，可以直接处理。

否则枚举 $u$ 删还是不删，若 $u$ 不删则其所有邻居都要被删，故有关于点覆盖大小限制 $k$ 的时间复杂度递推式 $T(k)=T(k-1)+T(k-3)+O(n)$，这个在 $k=30$ 时大约是 $10^5O(n)$。

把 $<x$ 的看作 $0$，$\ge x$ 的看作 $1$

这个技巧通常搭配二分 $x$ 来使用，或者直接考虑 $01$ 序列然后通过这个套路证明某些东西。

例题 1：Magic Breeding

例题 2：【2025NOI模拟赛20】排列

例题 2：A Serious Referee

曼哈顿距离和切比雪夫距离互转

曼哈顿距离：$|x1-x2|+|y1-y2|$

切比雪夫距离：$\max(|x1-x2|,|y1-y2|)$

把所有点 $(x,y)$ 变成 $(x+y,x-y)$ 后两点之间的切比雪夫距离就等于原来的曼哈顿距离，把所有点 $(x,y)$ 变成 $(\frac{x+y}{2},\frac{x-y}{2})$ 后两点的曼哈顿距离就等于原来的切比雪夫距离。

bzoj3170 松鼠聚会 AT_code_festival_2017_quala_d P3439 P2906 P5098 P4648 P7561

网格空间连通性容斥（便便容斥）

是否矩形

网格空间中的黑块形成矩形，当且仅当所有 $2\times 2$ 小正方形（可超出边界）中：

• 恰好有 $4$ 个小正方形包含恰好一个黑块（限制外围拐点数）；
• 没有小正方形包含恰好三个黑块（限制没有洞）；

相当于包含一个黑块的小正方形个数加上包含三个黑块的小正方形个数 $=4$。

连通块个数

在二维网格图中数中间没有洞的四向连通块个数可以这样容斥：

可以通过做四次扫描线来解决。

八连通也是类似的：

并且这还可以拓展到高维空间，相当于是高维面积乘上 $-1^{\text{砍掉一面的维度的个数}}$ 的容斥系数然后加起来。

$\sum\limits_{d|n}O(\sqrt d)=O(n^{\frac{3}{4}})$

不会证，感性理解一下就是 $\sum\limits_{d=1}^{\sqrt n}\sqrt d+\sqrt{\frac{n}{d}}$ 是 $O(n^{\frac{3}{4}})$ 级别的。

以后可以大胆写整除分块套整除分块。

Jerry Wen 定理

解的一些必要/充分条件的并，很有可能就是解的充要条件。

一些博弈论、图论、构造题可以尝试找必要/充分条件刻画解的充要条件。

按 $r$ 分块

某些题目中 $|i-j|\le r$ 的无序点对 $(i,j)$ 才有贡献，此时可以按 $r$ 分块（$[1,r]$、$[r+1,2r]$ 等等为一块）。这样做的好处：

• 令 $i>j$，考虑固定 $i$ 后有贡献的点对 $(i,j)$ 的集合 $S$；
• 贡献可以分为块内贡献和块间（$i$ 所在块和上一块）贡献；
• 块内贡献：正着扫，$S$ 中只会加入新元素；
• 块间贡献：倒着扫，$S$ 中同样只会加入新元素；

注意要先处理块间贡献。

例题：【2023成都集训模拟赛04】op

同余最短路

当模 $p$ 同余的所有状态等价，要求 $d_i$ 表示模 $p$ 为 $i$ 的状态中最小的那个时，一般建出 $p$ 个点代表状态等价类，把状态间的转移映射成这些点间的边，跑最短路求 $d_i$。

典型应用：

• 给一些数，求至少要拼几次才能拼出模 $p$ 为 $i$ 的数；
• 给一些数，求这些数完全背包后能表示的数的个数；
• 给一些数，求这些数完全背包后不能表示的最小/最大数；

例题：

• ARC084D Small Multiple
• 【2023NOIP模拟赛09】补幺梨

贡献为函数时考虑拆开再算新增贡献

例题：

• 【2023NOI模拟赛36】A
• AGC065A Shuffle and mod K

各种组合意义

排列

• 考虑建立一个 $n\times n$ 的网格，只有 $(i,p_i)$ 有标记；
  • CF1909F2
• 考虑连有向边 $(i,p_i)$，形成若干个置换环；

$O(k\log k+mk)$ 求 $k$ 次多项式 $n$ 次幂的前 $m$ 项

假设要求 $[x^{[0,m-1]}]f(x)^n$，设 $g(x)=f(x)^n$，对 $g(x)$ 求导，则：

$\begin{aligned} g(x)'&=f'(x)\times n\times f(x)^{n-1}\\ g(x)'f(x)&=nf'(x)g(x) \end{aligned}$

那么将 $g(x)$ 展开成幂级数即可根据 $f(x)$ 得到 $g_{[i-k,i-1]}\to g_i$ 的递推关系，多项式快速幂预处理 $g_{[0,k-1]}$ 然后递推即可。

倍增并查集

用于快速维护两个区间内元素对应相等（$A_{l1}=B_{l2},A_{l1+1}=B_{l2+1},\dots,A_{r1}=B_{r2}$）。

类似倍增，建 $\log$ 层点，然后并查集。

新增相等关系的时候类似倍增拆成两对区间分别向等，最后从上到下遍历每一层下放相等关系。

具体的，若第 $i$ 层时 $[l,l+2^i-1]$ 所在集合的根为 $[p,p+2^i-1]$，那么下放相等关系 $[l,l+2^{i-1}-1]=[p,p+2^{i-1}-1]$，$[l+2^{i-1},l+2^{i}-1]=[p+2^{i-1},p+2^{i}-1]$。

而当维护的相等关系在同一个序列上时，可以在线做，每次暴力下放。这样由于每一层只会合并 $O(n)$ 次，所以总复杂度是 $O(nm\log n)$ 的，其中 $m$ 是并查集复杂度。

例题：

• P3295 [SCOI2016] 萌萌哒
• 【2025NOI模拟赛10】简单题

判断无向图 $G$ 的某个边集 $S$ 是否为割

即判断割掉 $S$ 中的边后 $G$ 是否不连通。

考虑 dfs 树，为每条返祖边赋一个随机权值，每条树边的权值则是所有跨过它的返祖边权值的 xor 和。

那么 $S$ 为割当且仅当存在 $S$ 的一个非空子集 $T$ 满足 $T$ 中边权值 xor 和为 $0$（线性基包含 $0$）。

证明考虑若 $T$ 非空且其中边权值 xor 和为 $0$，则显然每个包含一条非树边的简单环都会是以下两种情况之一：

• 未被割掉边
• 被割掉至少两条边

并且所有边中至少割掉了两条边。

理解一下就容易发现满足这些条件的边集一定是 $G$ 的一个割。

这个做法还可以解决二分割（割掉边后是否是二分图）的题目：

• QOJ1351 Koosaga's Problem

扣掉一个物品的 01 背包

劲题。

可以做到 $O(nk\log n)$。

具体的，考虑类似线段树一样分治，处理区间 $[l,r]$ 的时候先加入 $[l,mid]$ 中的物品，递归右半边；再撤销掉 $[l,mid]$ 中的物品（通过开桶记录加入前的状态实现），递归左半边。这样递归到单点的时候就求出了答案。

时间复杂度是 $T(n)=O(nk)+2T(\frac{n}{2})=O(nk\log n)$ 的。

一个 log 求两个单调序列的第 $k$ 小

其实可以拓展到求 $m$ 个单调序列的第 $k$ 小，不过 log 的底数会变，常数有点大。

假设要求两个单调不降序列 $a,b$ 的第 $k$ 小，那么若 $a_{\lfloor k/2\rfloor}<b_{\lfloor k/2\rfloor}$ 则可以删去 $a$ 的前 $\lfloor k/2\rfloor$ 个数，并将 $k$ 减去 $\lfloor k/2\rfloor$。正确性考虑前 $k$ 小肯定是 $a_{[1,x]}$ 和 $b_{[1,y]}$（$x+y=k$），那么 $x$ 和 $y$ 一定有至少一个大于等于 $\lfloor k/2\rfloor$。

某些题目中 $a$ 和 $b$ 是非负序列的前缀和，且非负序列带单点修。那么可以考虑对于 $a$ 和 $b$ 都建出线段树，然后在线段树上二分，维护 $x$ 所在的区间 $[lx,rx]$ 和 $y$ 所在的区间 $[ly,ry]$，不难发现每次肯定能砍掉某个区间的一半（$k$ 较小的时候砍掉后一半，否则砍掉前一半）。

#include "mitsuha.h"
#include <vector>
#include <cstdio>
#include <map>

using namespace std;

namespace Exber
{
	const int S=20005;
	
	struct data
	{
		Data x;
		int id;
	};
	int cnt;
	map<pair<int,int>,bool> cmp;
	map<pair<int,int>,data> add;
	inline data operator+(data x,data y)
	{
		int ix=x.id,iy=y.id;
		if(ix>iy) swap(ix,iy);
		auto u=make_pair(ix,iy);
		if(add.find(u)!=add.end()) return add[u];
		return add[u]=data{x.x+y.x,++cnt};
	}
	inline bool operator<(data x,data y)
	{
		auto u=make_pair(x.id,y.id);
		if(cmp.find(u)!=cmp.end()) return cmp[u]; 
		return cmp[u]=(x.x<y.x);
	}
	inline bool operator>(data x,data y){return !(x<y);}
	
	int n;
	data a[S],b[S];
	data ta[S<<2],tb[S<<2];
	inline void upda(data tr[],int u){tr[u]=tr[u<<1]+tr[u<<1|1];}
	void build(data tr[],data a[],int u,int l,int r)
	{
		if(l==r) return tr[u]=a[l],void();
		int mid=l+r>>1;
		build(tr,a,u<<1,l,mid),build(tr,a,u<<1|1,mid+1,r);
		upda(tr,u);
	}
	void updp(data tr[],data a[],int u,int l,int r,int p)
	{
		if(l==r) return tr[u]=a[l],void();
		int mid=l+r>>1;
		if(p<=mid) updp(tr,a,u<<1,l,mid,p);
		else updp(tr,a,u<<1|1,mid+1,r,p);
		upda(tr,u);
	}
	inline void init(int N,int Q,vector<Data> A,vector<Data> B)
	{
		n=N;
		cnt=0;
		for(int i=1;i<=n;i++) a[i]=data{A[i-1],++cnt},b[i]=data{B[i-1],++cnt};
		build(ta,a,1,1,n),build(tb,b,1,1,n);
	}
	inline void update(int op,int x,Data y)
	{
		if(op==1)
		{
			a[x]=data{y,++cnt};
			updp(ta,a,1,1,n,x);
		}
		else
		{
			b[x]=data{y,++cnt};
			updp(tb,b,1,1,n,x);
		}
	}
	Data que(int ua,int la,int ra,int ub,int lb,int rb,int k,data sma,data smb)
	{
//		printf("[%d %d] [%d %d] %d %d %d\n",la,ra,lb,rb,k,sma.a,smb.a);
		if(la!=ra&&lb!=rb)
		{
			int mida=la+ra>>1;
			int midb=lb+rb>>1;
			int lsa=mida-la+1;
			int lsb=midb-lb+1;
			if(lsa>=k) return que(ua<<1,la,mida,ub,lb,rb,k,sma,smb);
			if(lsb>=k) return que(ua,la,ra,ub<<1,lb,midb,k,sma,smb);
			if(lsa+lsb<k)
			{
				data sa=sma+ta[ua<<1];
				data sb=smb+tb[ub<<1];
				if(sa<sb) return que(ua<<1|1,mida+1,ra,ub,lb,rb,k-lsa,sa,smb);
				else 	  return que(ua,la,ra,ub<<1|1,midb+1,rb,k-lsb,sma,sb);
			}
			else
			{
				data sa=sma+ta[ua<<1]+a[mida+1];
				data sb=smb+tb[ub<<1]+b[midb+1];
				if(sa>sb) return que(ua<<1,la,mida,ub,lb,rb,k,sma,smb);
				else	  return que(ua,la,ra,ub<<1,lb,midb,k,sma,smb);
			}
		}
		else if(la!=ra)
		{
			int mida=la+ra>>1;
			int lsa=mida-la+1;
			data sa=sma+ta[ua<<1];
			data sb=smb+b[lb];
			if(lsa+(sa>sb)>=k) return que(ua<<1,la,mida,ub,lb,rb,k,sma,smb);
			else			   return que(ua<<1|1,mida+1,ra,ub,lb,rb,k-lsa,sa,smb);
		}
		else if(lb!=rb)
		{
			int midb=lb+rb>>1;
			int lsb=midb-lb+1;
			data sb=smb+tb[ub<<1];
			data sa=sma+a[la];
			if(lsb+(sb>sa)>=k) return que(ua,la,ra,ub<<1,lb,midb,k,sma,smb);
			else	   		   return que(ua,la,ra,ub<<1|1,midb+1,rb,k-lsb,sma,sb);
		}
		else
		{
			data sa=sma+a[la];
			data sb=smb+b[lb];
			if(sa>sb) swap(sa,sb);
			return k==1?sa.x:sb.x;
		}
	}
	inline Data query(int k)
	{
//		puts("------");
		return que(1,1,n,1,1,n,k,data{emptyData,0},data{emptyData,0});
	}
}

void init(int N, int Q, vector<Data> A, vector<Data> B){Exber::init(N,Q,A,B);}
void update(int op, int x, Data y){Exber::update(op,x,y);}
Data query(int k){return Exber::query(k);}