一个随机更新的笔记（last update on 2026.1.23）

CF1746F Kazaee

给定长度为 $n$ 的序列 $a$，

$q$ 次操作，每次操作是以下两种之一：

• 1 x y：将 $a_x$ 修改为 $y$。
• 2 l r k：问 $[l,r]$ 中的所有正整数在 $[l,r]$ 中的出现次数是不是均为 $k$ 的倍数，若是则输出 YES，否则输出 NO。

$1\le n,q\le 3\times 10^5$。

首先对于询问直接扫一遍就可以做到 $\mathcal{O}(qn)$，然后直接做的话是带修莫队，显然不可接受。

我们考虑随机化，尝试放宽条件，判定区间长度是否为 $k$ 的倍数。

发现这个条件太过宽松，

考虑对于每个数 $a_i$，我们把它随机映射到一个数 $b_i$ 上，对于 $a_i=a_j\Rightarrow b_i=b_j$，

我们令 $\displaystyle S=\sum_{i=l}^r b_i$，显然 $k|S$ 是询问为 YES 的必要但不充分条件。

错判 NO 为 YES 的概率（感觉比较有道理的证明）：

$S=\displaystyle\sum_{x \text{ }\mathrm{exist}\text{ }\mathrm{in} \text{ }[l,r]}cnt_x\times y$，其中 $y$ 是完全随机的，那么我们可以认为 $S$ 也是随机的，那么存在一个随机的 $S$ 满足 $k|S$ 的概率大概是 $\frac1k$。

那我们把询问离线下来多随机几次即可通过本题。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;
const ll MAXN = 3e5 + 10;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll n,q;
ll a[MAXN],t[MAXN],val[MAXN<<1];
ll b[MAXN<<1],cnt=0;
ll op[MAXN],l[MAXN],r[MAXN],k[MAXN];
bool ans[MAXN];

struct BIT{
	#define lowbit(x) (x&(-x))
	ll c[MAXN];
	void clear(){
		memset(c,0,sizeof(c));
	}
	void update(ll x,ll k){
		while(x<MAXN){
			c[x]+=k;
			x+=lowbit(x);
		}
	}
	ll query(ll x){
		ll res=0;
		while(x){
			res+=c[x];
			x-=lowbit(x);
		}
		return res;
	}
}T;

signed main(){
	scanf("%lld%lld",&n,&q);
	FL(i,1,n) scanf("%lld",&a[i]),b[++cnt]=a[i];
	FL(i,1,q){
		scanf("%lld%lld%lld",&op[i],&l[i],&r[i]),ans[i]=1;
		if(op[i]==2) scanf("%lld",&k[i]);
		else b[++cnt]=r[i];
	}
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	FL(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	FL(i,1,q) if(op[i]==1) r[i]=lower_bound(b+1,b+cnt+1,r[i])-b;
	ll Tim=30;
	while(Tim--){
		T.clear();
		FL(i,1,cnt) val[i]=rnd();
		FL(i,1,n) t[i]=a[i];
		FL(i,1,n) T.update(i,val[t[i]]);
		FL(i,1,q){
			if(op[i]==1) T.update(l[i],val[r[i]]-val[t[l[i]]]),t[l[i]]=r[i];
			else ans[i]&=!((T.query(r[i])-T.query(l[i]-1))%k[i]);	
		}
	}
	FL(i,1,q) if(op[i]==2) puts(ans[i]?"YES":"NO");
}

B.P10102 [GDKOI2023 提高组] 矩阵

$T$ 组数据，每次给定 $3$ 个 $n\times n$ 的矩阵 $A,B,C$。

问 $A\times B$ 在模 $998244353$ 意义下是不是等于 $C$。

$1\le T,n\le 3000,\sum n\le 3000$。

因为要求的复杂度显然是 $\mathcal{O}(n^2)$ 的，所以想到向量乘矩阵。

然后你只需要想到多次随机一个 $1\times n$ 的向量 $D$ 并把两边同时乘上这个向量判断是否相等即可。

$A\times B=C \Leftrightarrow D\times A\times B=D\times C$。

分析正确率：该做法本质是判定 $D\times (AB-C)=0$，类似 Hash，错误率大概是 $\frac{1}{mod}$ 的。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 3e3 + 10;
const int mod = 998244353;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n;
bool fg=1;
struct Matrix{
	int a[MAXN][MAXN];
}A,B,C;
struct Vector{
	int a[MAXN];
	void clear(){
		memset(a,0,sizeof(a));
	}
}D;

Vector operator*(const Vector &A,const Matrix &B){
	Vector res;
	res.clear();
	FL(k,1,n)
		FL(j,1,n)
			res.a[j]=(res.a[j]+1ll*A.a[k]*B.a[k][j]%mod)%mod; 
	return res;
}

bool operator==(Vector A,Vector B){
	FL(i,1,n) if(A.a[i]!=B.a[i]) return 0;
	return 1;
}

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d",&n),fg=1;
		FL(i,1,n) FL(j,1,n) scanf("%d",&A.a[i][j]);
		FL(i,1,n) FL(j,1,n) scanf("%d",&B.a[i][j]);
		FL(i,1,n) FL(j,1,n) scanf("%d",&C.a[i][j]);
		int Tim=30;
		while(Tim--){
			FL(i,1,n) D.a[i]=rnd()%mod;
			fg&=((D*A)*B==D*C); 
		}
		puts(fg?"Yes":"No");
	}
} 

P1224 [NOI2013] 向量内积

对于两个 $d$ 维向量 $A=[a_1,a_2,\dots ,a_d]$ 和 $B=[b_1,b_2,\dots,b_n]$，定义它们的内积 $(A,B)=\displaystyle\sum_{i=1}^d a_ib_i$。

现在给定 $n$ 个 $d$ 维向量问有没有两个向量的内积为 $k$ 的倍数，若存在输出任意一组的编号，否则输出 $-1\text{ }-1$。

$n\le 10^5,d\le 100,k\le 3,x_{i,j}\le 3\times 10^6$。

显然你可以通过暴枚获得 60pts，

不存在合法向量等价于 $\forall i\not =j,a_i\cdot a_j=1$

然后考虑随机化，

我们枚举向量 $i$，我们尝试计算这个向量和所有向量 $j(j<i)$ 的乘积的平方之和（显然 $k=2$ 时向量只有 $0/1$，$k=3$ 时 $1,2$ 的平方在模 $3$ 意义下都为 $1$）。

即计算 $res=\displaystyle\sum_{j=1}^{i-1}(a_i\cdot a_j)^2$。

我们拆一下式子：

$$res=\sum_{j=1}^{i-1}(a_i\cdot a_j)^2\\ =\sum_{j=1}^{i-1}\sum_{p_1=1}^m\sum_{p_2=1}^m a_{i,p_1}\times a_{j,p_1}\times a_{i,p_2}\times a_{j,p_2}\\ =\sum_{p_1=1}^m\sum_{p_2=1}^m a_{i,p_1}\times a_{i,p_2}\big(\sum_{j=1}^{i-1}(a_{j,p_1}\times a_{j,p_2})\big)\\$$

于是令 $s_{p_1,p_2}=\displaystyle\sum_{j=1}^{i-1}(a_{j,p_1}\times a_{j,p_2})$，在遍历的时候累加。

显然如果不存在 $(j,i)$ 这样的合法对那么乘积的结果会是 $(i-1)\bmod k$（因为 $i-1$ 对内积都是 $1$），显然这个是不存在 $(j,i)$ 的必要不充分条件，正确率至少为 $\frac{1}{2}$。

所以应该将向量的顺序随机打乱几次（random_shuffle）分别进行遍历。

遍历 $1\sim n$，对于每个向量 $\mathcal{O}(d^2)$ 判断有没有合法对，若有那么 $\mathcal{O}(n)$ 枚举答案（显然只会枚举一次）。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;
const int MR = 1e2 + 10;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,d,K;
int a[MAXN][MR],id[MAXN];
int s[MR][MR];

int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(int)(c-'0'),c=getchar();
	return x*f;
}

int Get(int x){
	int res=0;
	FL(i,1,d){
		FL(j,1,d){
			res+=a[x][i]*a[x][j]*s[i][j]%K;
			s[i][j]+=a[x][i]*a[x][j];
		}
	}
	return res%K;
}

int check(int x,int y){
	int res=0;
	FL(i,1,d) res+=a[x][i]*a[y][i]%K;
	return res%K;
}

int main(){
	srand(time(0));
	n=read(),d=read(),K=read();
	FL(i,1,n) FL(j,1,d) a[i][j]=read()%K;
	FL(i,1,n) id[i]=i;
	int Tim=7; 
	while(Tim--){
		memset(s,0,sizeof(s));
		random_shuffle(id+1,id+n+1);
		FL(i,1,n){
			int pre=Get(id[i]);
			if(pre==((i-1)%K)) continue;
			FL(j,1,i-1){
				if(!check(id[i],id[j]))
					printf("%d %d\n",min(id[i],id[j]),max(id[i],id[j])),exit(0);
			}
		}
	}
	puts("-1 -1");
} 

P7962 [NOIP2021] 方差

给定长度为 $n$ 的单调不降的序列 $a$。

你每次可以选择一个 $i\in (1,n),a_i\to a_{i-1}+a_{i+1}-a_i$。

问若干次操作后该序列的方差最小值，输出这个值 $\times n^2$ 的结果。

方差的定义式 $D=\frac1n\sum_{i=1}^n(a_i-\overline a)^2,\overline{a}=\frac1n\sum_{i=1}^n a_i$。

$1\le n\le 10^4,1\le a_i\le 600$。

我一直以为这道题是模拟退火模板来着？居然还有正经做法？

方差的定义式显然可以化简：

$$n^2\times D=n\sum_{i=1}^n(a_i-\overline{a})^2\\ =n\sum_{i=1}^n(a_i^2+\overline{a}^2-2a_i\overline{a})\\ =n\times (\sum a_i^2)+(\sum a_i)^2-2(\sum a_i)^2\\ =n\times (\sum a_i^2)-(\sum a_i)^2$$

我们考虑我们每次进行的操作的实质，

原数组 $a,b,c,d\to a,a+c-b,c,d$

差分数组 $b-a,c-b,d-c\to c-b,b-a,d-c$

所以相当于交换差分数组。

我们不妨令 $d_i=a_{i+1}-a_i$（因为保证 $a_i$ 单调不降，所以 $d_i\ge 0$），我们对方差的式子做转换：

$$n\times \sum_{i=1}^n(a_i-a_1)^2+n^2\times a_1^2-2na_1\sum_{i=1}^na_i-\Big(\sum_{i=1}^n(a_i-a_1)\Big)^2-(na_1)^2+2na_1\sum_{i=1}^na_i\\ =n\sum_{i=1}^{n-1}(\sum_{j=1}^i d_j)^2-(\sum_{i=1}^{n-1}\sum_{j=1}^id_j)^2\\ =n\sum_{i=1}^n\Big(\sum_{j=1}^i d_j^2+2\sum_{j=1}^i\sum_{k=1}^{i-1}d_jd_k\Big)-\Big(\sum_{i=1}^{n-1}(n-i)d_i\Big)^2\\ =n\sum_{i=1}^{n}\sum_{j=1}^i\sum_{k=1}^id_jd_k-\Big(\sum_{i=1}^{n-1}(n-i)d_i\Big)^2\\ =n\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}(n-\max\{j,k\})-\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}(n-j)\cdot (n-k)\cdot d_j\cdot d_k\\ =\sum_{j=1}^{n-1}\sum_{k=1}^{n-1} d_j\cdot d_k \cdot \Big(n(n-\max\{j,k\})-\big(n^2-n(j+k)+j\times k\big)\Big)\\ =\sum_{j=1}^{n-1}\sum_{k=1}^{n-1} d_j\cdot d_k \cdot \big(-n\cdot \max\{j,k\}+n(j+k)-j\times k\big)\\ =\sum_{j=1}^{n-1}\sum_{k=1}^{n-1} d_j\cdot d_k \cdot \big(n\cdot \min\{j,k\}-j\times k\big)\\ =\sum_{i=1}^{n-1} d_i^2\times i\times (n-i)+2\sum_{j=1}^{n-1}\sum_{k=j+1}^{n-1} d_j \cdot d_k \cdot (n-k)\cdot j$$

首先第一个式子是定值，显然 $(n-k)\cdot j$ 在 $j,k$ 接近且为最中间的时候取到最大值，此时要求 $d_j,d_k$ 最小使得第二个式子最小。

所以可以证明答案最小时差分呈现单谷。

我们回到方差的式子：

$$n\times (\sum_{i=1}^na_i^2)-(\sum_{i=1}^na_i)^2$$

对于这个式子进行 dp，

我们把 $d_i$ 从小到大排序（重要！！后面的性质保证和优化都基于此）。

我们设 $f_{i,x}$ 表示考虑完前 $i-1$ 个差分值（这里是 $i-1$！！！），此时的 $a_i$ 的和为 $x$ 时最小的平方和（即式子里的第一项），令 $s_i=\displaystyle\sum_{j=1}^id_i$。

我们考虑 $d_i$ 放在单谷的左边还是右边（之前放的 $d_j$ 都比当前的 $d_i$ 小，显然这样放满足单谷的性质）。

放在左边（那此时所有先前放入的 $d_j$ 都在 $d_i$ 后面，所以对于 $i$ 个 $a$ 的实际值都加上了 $d_i$）：

$$f_{i,x}+2x\cdot d_i+i\cdot d_i^2\to f_{i+1,x+i\times d_i}$$

放在右边（那么相当于新加入的 $a_i$ 是之前所有 $d_j$ 和 $d_i$ 的和）：

$$f_{i,x}+s_i^2\to f_{i+1,x+s_i}$$

边界是 $f_{1,0}=0$。

所以答案为：

$$ans=\min_{x=0}^{Mx}\{n\cdot f_{n,x}-x^2\}$$

$Mx$ 是 $n\cdot mx\approx 6\times 10^6$ 量级的，$mx=\max\{a_i\}$。

显然这个 dp 的第一位可以压掉，然后因为 $d_i\ge0$ 所以类似背包转移就行，甚至不用滚动数组，空间复杂度 $\mathcal{O}(Mx)$。

此时时间复杂度是 $\mathcal{O}(n\cdot Mx)$ 的，显然过不了，但我们发现 $n$ 是 $10^4$ 量级的，而 $a_i$ 的值域只有 $600$，并且保证 $d_i\ge0$，所以 $d_i$ 只有不超过 $600$ 个值 $\not = 0$，

当 $d_i=0$ 的时候此时显然 $s_i=0$（因为我们从小到大排序了），所以不会发生任何转移，我们直接跳过即可。

于是时间复杂度优化为 $\mathcal{O}(mx\cdot Mx)$，可以通过本题。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e4 + 10;
const int MR = 600 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n,mx=0,Mx=0;
ll ans=inf;
int a[MAXN],d[MAXN],s[MAXN];
ll f[MAXN*MR];

int main(){
	scanf("%d",&n);
	FL(i,1,n) scanf("%d",&a[i]),mx=max(mx,a[i]);
	FL(i,1,n-1) d[i]=a[i+1]-a[i];
	sort(d+1,d+n);
	memset(f,0x3f,sizeof(f));
	f[0]=s[0]=0;
	FL(i,1,n) s[i]=s[i-1]+d[i];
	FL(i,1,n){
		if(!d[i]) continue;
		FR(j,Mx,0){
			if(f[j]==inf) continue;
			f[j+i*d[i]]=min(f[j+i*d[i]],f[j]+2ll*j*d[i]+1ll*i*d[i]*d[i]);
			f[j+s[i]]=min(f[j+s[i]],f[j]+1ll*s[i]*s[i]);
			f[j]=inf,Mx=max({Mx,j+i*d[i],j+s[i]});
		}
	}
	FL(i,0,Mx) if(f[i]!=inf) ans=min(ans,n*f[i]-1ll*i*i);
	printf("%lld\n",ans);
} 

---

关于模拟退火：

还是有结论操作相当于交换差分数组，然后退火确定每个数在单谷的哪一侧。

但是正确性和初始选择的序列关系比较大，所以可以进行多次。

UOJ455 雪灾与外卖

数轴上，有 $n$ 个老鼠和 $m$ 个洞。第 i 个洞最多容纳 $w_i$ 只老鼠，且每容纳一只会产生 $c_i$ 的代价；一只老鼠移动 $1$ 的距离会产生 $1$ 的代价。给定初始时老鼠和洞的位置，最小化每只老鼠都进洞的代价。 $2\le n,m\le 10^5,0\le x_i,y_i,c_i,w_i\le 10^9$。

关于模拟费用流：

个人理解模拟费用流是作为理解反悔贪心正确性的方法，我们用简单的费用流思想去做反悔贪心。

思考有哪几种显然的增广路并用简单的数据结构进行维护。

---

我们把 $X,Y$ 按坐标从小到大归并。

假设当前遇到一只老鼠，坐标为 $x$：

我们尝试匹配左边最优的一个洞，匹配代价为 $y$（若左边没有洞则代价为 $\infty$），然后在 $X$ 堆中插入 $-(x+y)+(-x)$，即如果它不匹配左边的洞改为匹配右边的洞，会减少 $x+y$ 的代价，增加 $-x$ 的代价。

假设当前遇到一个洞，坐标为 $y$，额度为 $c$，代价为 $w$：

我们尝试匹配左边最优的一只老鼠，匹配代价为 $x$，假设 $x+y+w<0$（即代价小于 $0$），那么这个匹配能使得答案更优于是我们进行返回，然后在 $Y$ 堆中插入 $-(x+y+w)+(-y+w)$，即如果它不匹配左边的老鼠改为匹配右边的老鼠，会减少 $x+y+w$ 的代价，增加 $-y+w$ 的代价。

然后假设有 $rem$ 个额度无法匹配左边老鼠那么我们在 $Y$ 堆中插入 $rem$ 个 $(-y+w)$ 供以后右边的老鼠匹配。

那么对于 $c-rem$ 个匹配的老鼠，我们在 $X$ 堆中加入 $-w+(-y)$，即选择反悔，走到了 $y$ 但不匹配 $y$，于是减少 $w$ 的代价，选择匹配更右边的洞于是增加 $-y$ 的代价。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;
const ll MAXN = 1e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;

ll n,m,sum=0;
ll ans=0;
ll X[MAXN],Y[MAXN],w[MAXN],c[MAXN];
priority_queue<PII,vector<PII>,greater<PII> >q1,q2;

void Upd1(ll x){
	ll y=inf;
	if(!q2.empty()){
		PII t=q2.top();
		q2.pop();
		y=min(y,t.first),t.second--;
		if(t.second) q2.push(t); 
	}
	ans+=(x+y);
	q1.push({-(x+y)+(-x),1});
}
void Upd2(ll y,ll w,ll c){
	ll rem=c,x,v;
	while(rem&&!q1.empty()&&y+w+q1.top().first<0){
		PII t=q1.top();
		q1.pop();
		x=t.first,v=min(rem,t.second);
		t.second-=v,rem-=v;
		ans+=(y+w+x)*v;
		if(t.second) q1.push(t);
		q2.push({-(y+w+x)+(-y+w),v});
	}
	if(rem) q2.push({(-y+w),rem});
	if(c-rem) q1.push({-(y+w),c-rem});
}

signed main(){
	scanf("%lld%lld",&n,&m);
	FL(i,1,n) scanf("%lld",&X[i]);
	FL(i,1,m) scanf("%lld%lld%lld",&Y[i],&w[i],&c[i]),sum+=c[i];
	if(sum<n) puts("-1"),exit(0);
	ll px=1,py=1;
	while(px<=n||py<=m){
		if(py>m||(px<=n&&X[px]<Y[py])) Upd1(X[px]),px++;
		else Upd2(Y[py],w[py],c[py]),py++;
	} 
	printf("%lld\n",ans);
} 

P6943 [ICPC 2018 WF] Conquer The World

给定一棵 $n$ 的节点的树，每条边有边权 $w$，

初始时第 $i$ 个节点的权值为 $x_i$，要求在终态，节点权值 $\ge y_i$。

你可以进行若干次操作，选定一条边 $(u,v,w)$，花费 $w$ 的代价使得 $x_u\to x_u-1,x_v\to x_v+1$ 或 $x_u\to x_u+1,x_v\to x_v-1$。

问使得终态合法的最小代价。

$1\le n\le 2.5\times 10^5,\sum y_i\le \sum x_i\le 10^6$。

首先我们令每个点的权值 $c_u=x_u-y_u$。

• $c_u>0$ 表示 $u$ 有多余的权值。
• $c_u<0$ 表示 $u$ 需要多余的权值。

显然很容易设计费用流算法，设源点、汇点分别为 $S,T$：

• 若 $c_u>0,c(S,u)=c_u,w(S,u)=0$。
• 若 $c_u<0,c(u,T)=-c_u,w(u,T)=0$。
• 对于一条树边 $(u,v)$，$c(u,v)=c(v,u)=+\infty,w(u,v)=w(v,u)=c$。

但显然我们不能直接跑。

对于树上的两点 $(u,v)$，它们之间的距离是：

$dis(u,v)=dep_u+dep_v-2\times dep_{lca(u,v)}$。

我们维护可并堆 $A$ 表示需求，可并堆 $B$ 表示供应。

我们从下到上 dfs，对于节点 $u$，我们查看以 $u$ 为根的子树中，有没有尚未匹配的正权点和负权点。

如果有，那我们尝试在 $u$ 点将代价最小的两个 $A_u,B_u$匹配。

若 $val_{A_u}+val_{B_u}-2dep_{u}<0$，即匹配代价 $<0$，方案更优，那我们匹配这一对点。

然后我们设置反悔机制，

假如此时我们不匹配 $A_u$ 了，那我们会减少 $x+y-2dep_u$ 的代价，增加 $x$ 的代价（重新匹配），把 $A_u$ 重新插入需求堆。

$B_u$ 同理，假如此时我们不匹配 $B_u$ 了，那我们会减少 $x+y-2dep_u$ 的代价，增加 $y$ 的代价（重新匹配），把 $B_u$ 重新插入供应堆。

显然我们不会匹配同时匹配两个反悔的 $A_u,B_u$，因为一定严格不优。

因为题目要求必须满足所有 $y_i$，所以这是“最小费用可行流”，我们给每个负权点的初始代价减去 $\infty$，这样任何一对匹配的代价都会变成一个巨大的负数，显然此时贪心地匹配，匹配的对数越多越好，一定能匹配所有负权点。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;

const ll MAXN = 2.5e5 + 10;
const ll MR = 1e7 + 10;
const ll inf = 2e12;

ll n,tot=0,ans=0;
ll a[MAXN],b[MAXN],dep[MAXN];
vector<PII>G[MAXN];
ll A[MR],B[MR],val[MR],dis[MR],Ls[MR],Rs[MR];

ll Get(ll v){
	val[++tot]=v;
	dis[tot]=Ls[tot]=Rs[tot]=0;
	return tot;
}

ll merge(ll x,ll y){
	if(!x||!y) return x|y;
	if(val[x]>val[y]) swap(x,y);
	Rs[x]=merge(Rs[x],y);
	if(dis[Rs[x]]>dis[Ls[x]]) swap(Ls[x],Rs[x]);
	dis[x]=dis[Rs[x]]+1;
	return x;
}

void dfs(ll u,ll fa){
	FL(i,a[u]+1,b[u]) A[u]=merge(A[u],Get(dep[u]-inf)),ans+=inf;
	FL(i,b[u]+1,a[u]) B[u]=merge(B[u],Get(dep[u]));
	for(auto i:G[u]){
		ll v=i.first,w=i.second;
		if(v==fa) continue;
		dep[v]=dep[u]+w;
		dfs(v,u);
		A[u]=merge(A[u],A[v]);
		B[u]=merge(B[u],B[v]);
	}
	while(A[u]&&B[u]&&val[A[u]]+val[B[u]]-(dep[u]<<1)<0){
		ll x=val[A[u]],y=val[B[u]];
		ans+=x+y-(dep[u]<<1);
		ll tx=A[u],ty=B[u];
		A[u]=merge(Ls[A[u]],Rs[A[u]]);
		B[u]=merge(Ls[B[u]],Rs[B[u]]);
		val[tx]=-(x+y-(dep[u]<<1))+x;
		val[ty]=-(x+y-(dep[u]<<1))+y;
		dis[tx]=dis[ty]=Ls[tx]=Ls[ty]=Rs[tx]=Rs[ty]=0;
		A[u]=merge(A[u],tx);
		B[u]=merge(B[u],ty);
	}
}

signed main(){
	scanf("%lld",&n);
	FL(i,2,n){
		ll u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	} 
	FL(i,1,n) scanf("%lld%lld",&a[i],&b[i]);
	dfs(1,0);
	printf("%lld\n",ans);
} 

AT_agc045_f [AGC045F] Division into Multiples

$T$ 组数据，每次给定 $X$ 个整数 $A$ 和 $Y$ 个整数 $B$（$A\not =B$），

将这些数划分为若干个不为空的组，问最多有多少个组满足组内的数的和为 $C$ 的倍数。

$1\le T\le 2\times 10^4,1\le A,X,B,Y,C\le 10^9$。

首先有结论，我们可以通过一些变换使得 $A,B,C$ 两两互质。

令 $D_{AB}=\gcd(A,B)$，若 $D_{AB}\not = 1$，显然 $(A,X,B,Y,C)$ 和 $(\frac{A}{D_{AB}},X,\frac{B}{D_{AB}},Y,\frac{C}{\gcd(C,D_{AB})})$ 等价。

令 $D_{AC}=\gcd(A,C)$，若 $D_{AC}\not = 1 \land D_{AB}=1$，那此时 $B$ 一定不含有 $D_{AC}$ 及其因子，显然此时若想要组内和为 $C$ 的倍数，每组内 $B$ 的数量必须为 $D_{AC}$ 的倍数，所以 $(A,X,B,Y,C)$ 和 $(\frac{A}{D_{AC}},X,B,\lfloor\frac{Y}{D_{AC}}\rfloor,\frac{C}{D_{AC}})$ 等价。

令 $D_{BC}=\gcd(B,C)$，若 $D_{BC}\not = 1 \land D_{AB}=1$，同理，每组内 $A$ 的数量必须为 $D_{BC}$ 的倍数，所以 $(A,X,B,Y,C)$ 和 $(A,\lfloor\frac{X}{D_{BC}}\rfloor,\frac{B}{D_{BC}},Y,\frac{C}{D_{AC}})$ 等价。

我们假设一组内有 $x$ 个 $A$，$y$ 个 $B$，那么显然有 $Ax+By\equiv 0\pmod C$，于是有 $y\equiv -\frac{A}{B}x\pmod C$。

我们令 $K=A\times B^{-1}\pmod C$，那么满足条件的二元对 $(x,y)$ 就是： $(0,C),(1,(-K)\bmod C),(2,(-2K)\bmod C)\cdots$。

显然如果对于二元组 $(x,y)$ 存在 $(x_0,y_0)$ 满足 $x_0<x\land y_0\le y$，那么 $(x,y)$ 一定严格不优，一定不会被用到，

换句话说，可用的二元组 $(x,y)$ 满足随着 $x$ 增大，$y$ 严格下降，即 $y$ 是 $[0,x]$ 中 $y$ 的前缀最小值。

我们考虑 $(0,C)\sim (\lfloor\frac{C}{K}\rfloor,C-\lfloor\frac{C}{K}\rfloor \cdot K)$，显然此时没有出现加 $C$ 的操作所以 $y$ 是呈等差数列严格下降的，均为前缀最小值，所以均可用。

然后我们令 $C'=C\bmod K$，显然接下来只有 $y\in [0,C')$ 的二元组是可用的。

我们考虑 $K$ 在模 $C'$ 下的意义，显然 $K|(C-C')$，所以有 $K$ 和 $K'=K\bmod C'$ 在模 $C'$ 意义下等价。

所以相当于变成了一个子问题 $C\to C',K\to K'$，可用的 $y$ 为 $C',C-K ,\cdots ,C'-\lfloor\frac{C'}{K’}\rfloor\cdot K'$，然后继续递归。

然后可以发现这个相当于求 $\gcd$ 的辗转相除法，复杂度 $\mathcal{O}(\log C)$。所以所有点被划分成了 $O(\log C)$ 个等差数列（显然 $x$ 坐标也呈等差数列）。

令等差序列的第 $t$ 项为 $(sx+(t-1)dx,sy-(t-1)dy)$，则 $x$ 的公差为 $dx$，$y$ 的公差为 $dy$，显然 $dx$ 会不断增大而 $dy$ 不断减小。

关于 $sx,dx$ 的计算，我们可以用 $sy,dy$ 反推，我们令 $invK=\frac{1}{K}\pmod C$，则 $sx=-\frac{sy}{K}\pmod C\Rightarrow sx=(-sy\times invK)\bmod C$，同理有 $dx=(dy\times invK)\bmod C$，注意 $dy$ 是减少量所以式子不需要负号。

我们可以证明所有答案中的二元组在同一个等差数列上。

考虑若不在同一个等差数列上，那么我们设 $(x_1,y_1),(x_2,y_2)$ 分别在第 $i,j(i<j)$ 个等差数列上（不妨假设都不在边界上），我们可以选择把 $(x_1,y_1)$ 往后移动一位，把 $(x_2,y_2)$ 往前移动一位，$\Delta x=dx_i-dx_j<0,\Delta y=dy_j-dy_i< 0$，显然是更优的，所以我们继续移动直到它们属于同一个等差数列一定是最优的。

（小D的题解说这个是下凸壳，所以相向移动一定最优，感觉根据几何意义肯定是下凸壳，但是为什么斜率递减啊？？？）

然后对于这个等差数列，我们设它有 $len$ 项。

我们二分二元组的个数 $mid$，看是否存在 $sum\in [0,mid\cdot len]$，满足 $mid\cdot sx+sum\cdot dx\le X\land mid\cdot sy-sum\cdot dy\le Y$ 即可，显然如果存在一个这样的 $sum$ 我们一定能构造出一个合法的包含 $mid$ 个二元组的方案。

把条件拆一下就能得到 $sum$ 的范围 $[0,mid\cdot len]\cap [\lceil\frac{mid\cdot sy-Y}{dy}\rceil,\lfloor\frac{X-mid\cdot sx}{dx}\rfloor]$。

时间复杂度 $\mathcal{O}(T\log^2 V),V=10^9$。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;

ll A,X,B,Y,C,D,K,invK,ans=0;

void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1,y=0;
		return ;
	}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
ll inv(ll x,ll mod){
	ll p,q;
	exgcd(x,mod,p,q);
	return (p%mod+mod)%mod;
}
ll Ceil(ll x,ll y){
	return (x<=0?0:(x+y-1)/y);
}
ll Floor(ll x,ll y){
	return (x<0?-1:x/y);
}

void Calc(ll sy,ll dy,ll cnt){
	ll sx=(-sy*invK%C+C)%C;
	ll dx=dy*invK%C;
	ll l=0,r=X+Y;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(Ceil(sy*mid-Y,dy)<=min(Floor(X-sx*mid,dx),cnt*mid)) ans=max(ans,mid),l=mid+1;
		else r=mid-1;
	} 
	return ;
}

signed main(){
	ll Num;
	scanf("%lld",&Num);
	while(Num--){
		scanf("%lld%lld%lld%lld%lld",&A,&X,&B,&Y,&C),ans=0;
		D=__gcd(A,B),A/=D,B/=D,C/=__gcd(C,D);
		D=__gcd(A,C),A/=D,C/=D,Y/=D;
		D=__gcd(B,C),B/=D,C/=D,X/=D;
		if(C==1){
			printf("%lld\n",X+Y);
			continue;
		}
		K=A*inv(B,C)%C,invK=inv(K,C);
		ll a=C,b=K;
		while(1){
			Calc(a,b,a/b),a%=b;
			if(!a) break;
			b=(b%a?b%a:a); 
		}
		printf("%lld\n",ans);
	}
} 

H.P5470 [NOI2019] 序列

给定长度为 $n$ 的序列 $a,b$，你需要选择两个长度为 $K$ 的序列 $c,d$，

满足 $1\le c_1<c_2<\cdots <c_K\le n,1\le d_1<d_2<\cdots<d_K\le n$ 且 $|\set{c_1,c_2,\cdots ,c_K}\cap \set{d_1,d_2,\cdots d_k}|\ge L$。

求 $\displaystyle\sum_{i=1}^K a_{c_i}+\sum_{i=1}^K b_{d_i}$ 的最大值。

$T\le 10,1\le L,K\le n\le 2\times 10^5,1\le \sum n \le 10^6,1\le a_i,b_i\le 10^9$

可以用模拟费用流做，但我没有搞懂所以我们直接反悔贪心（虽然本质是一样的）。

首先我们直接贪心，把最大的 $K$ 个 $a_i,b_i$ 取出来。

接着我们考虑用最小的代价把它调整为至少选了 $L$ 个同一个 $i$ 的 $a_i,b_i$（不妨称为匹配 $L$ 对）。

反悔操作有以下四种：

• 找一个 $a,b$ 都被选择的 $i$，然后找 $a$ 被选择的 $j$ 和 $b$ 被选择的 $k$，用 $b_j+a_k$ 替换 $a_i+b_i$，代价 $(b_j+a_k)+[-(a_i+b_i)]$，此时 $j,k$ 均为一对。
• 找一个 $a$ 被选择的 $i$，然后找 $b$ 被选择的 $j$，用 $a_j$ 替换 $a_i$，代价 $a_j+(-a_i)$，此时 $j$ 为一对。
• 找一个 $b$ 被选择的 $i$，然后找 $a$ 被选择的 $j$，用 $b_j$ 替换 $b_i$，代价 $b_j+(-b_i)$，此时 $i$ 为一对。
• 找一个 $a,b$ 都未被选择的 $i$，然后找 $a$ 被选择的 $j$ 和 $b$ 被选择的 $k$，用 $a_i+b_i$ 替换 $a_j+b_k$，代价 $(a_i+b_i)+(-a_j)+(-b_k)$，此时 $i$ 为一对。

显然每种操作都会让匹配次数 $+1$，所以只会做 $\mathcal{O}(L)$ 次。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;
const ll MAXN = 1e6 + 10;
const ll inf = 0x3f3f3f3f;

ll n,K,L,tot=0;
ll ans=0;
ll a[MAXN],b[MAXN],ch[MAXN];
ll pa[MAXN],pb[MAXN];
bool visa[MAXN],visb[MAXN];
priority_queue<PII>q[7];

bool cmpa(ll p,ll q){
	return a[p]>a[q];
} 
bool cmpb(ll p,ll q){
	return b[p]>b[q];
}

signed main(){
	ll Num;
	scanf("%lld",&Num);
	while(Num--){
		scanf("%lld%lld%lld",&n,&K,&L),ans=tot=0;
		FL(i,1,6) while(!q[i].empty()) q[i].pop();
		FL(i,1,n) scanf("%lld",&a[i]),pa[i]=i;
		FL(i,1,n) scanf("%lld",&b[i]),pb[i]=i;
		sort(pa+1,pa+n+1,cmpa);
		sort(pb+1,pb+n+1,cmpb);
		FL(i,1,n) visa[i]=visb[i]=0;
		FL(i,1,K) visa[pa[i]]=visb[pb[i]]=1;
		FL(i,1,n){
			if(visa[i]) ans+=a[i];
			if(visb[i]) ans+=b[i];
			ch[i]=2*visa[i]+visb[i];
			if(ch[i]==3) q[1].push({-a[i]-b[i],i}),tot++;
			else if(ch[i]==2) q[2].push({-a[i],i}),q[3].push({b[i],i});
			else if(ch[i]==1) q[4].push({a[i],i}),q[5].push({-b[i],i});
			else q[6].push({a[i]+b[i],i});
		} 
		while(tot<L){
			ll now=-inf,op=0,id1,id2,id3;
			while(!q[1].empty()&&ch[q[1].top().second]!=3) q[1].pop();
			while(!q[2].empty()&&ch[q[2].top().second]!=2) q[2].pop();
			while(!q[3].empty()&&ch[q[3].top().second]!=2) q[3].pop();
			while(!q[4].empty()&&ch[q[4].top().second]!=1) q[4].pop();
			while(!q[5].empty()&&ch[q[5].top().second]!=1) q[5].pop();
			while(!q[6].empty()&&ch[q[6].top().second]!=0) q[6].pop();
			if(!q[1].empty()&&!q[3].empty()&&!q[4].empty()&&
			q[1].top().first+q[3].top().first+q[4].top().first>now)
				now=q[1].top().first+q[3].top().first+q[4].top().first,
				op=1,id1=q[1].top().second,id2=q[3].top().second,id3=q[4].top().second;
			if(!q[2].empty()&&!q[4].empty()&&q[2].top().first+q[4].top().first>now)
				now=q[2].top().first+q[4].top().first,
				op=2,id1=q[2].top().second,id2=q[4].top().second;
			if(!q[3].empty()&&!q[5].empty()&&q[3].top().first+q[5].top().first>now)
				now=q[3].top().first+q[5].top().first,
				op=3,id1=q[3].top().second,id2=q[5].top().second;
			if(!q[6].empty()&&!q[2].empty()&&!q[5].empty()&&
			q[6].top().first+q[2].top().first+q[5].top().first>now)
				now=q[6].top().first+q[2].top().first+q[5].top().first,
				op=4,id1=q[6].top().second,id2=q[2].top().second,id3=q[5].top().second;
			if(op==1)
				ch[id1]=0,q[6].push({a[id1]+b[id1],id1}),
				ch[id2]=3,q[1].push({-a[id2]-b[id2],id2}),
				ch[id3]=3,q[1].push({-a[id3]-b[id3],id3});
			else if(op==2)
				ch[id1]=0,q[6].push({a[id1]+b[id1],id1}),
				ch[id2]=3,q[1].push({-a[id2]-b[id2],id2});
			else if(op==3)
				ch[id1]=3,q[1].push({-a[id1]-b[id1],id1}),
				ch[id2]=0,q[6].push({a[id2]+b[id2],id2});
			else if(op==4)
				ch[id1]=3,q[1].push({-a[id1]-b[id1],id1}),
				ch[id2]=0,q[6].push({a[id2]+b[id2],id2}),
				ch[id3]=0,q[6].push({a[id3]+b[id3],id3});
			tot++,ans+=now;
		}
		printf("%lld\n",ans);
	}
} 

P2619 [国家集训队] Tree I

给定一个 $n$ 个点 $m$ 条边的无向带权连通图，每条边的颜色是 $0/1$。

求恰好包含 $X$ 条 $0$ 边的最小生成树的大小。

$n\le 5\times 10^4,m\le 10^5,w_i\le [1,100]$。

应该也算是 wqs 二分的入门题？

wqs 二分是解决一类“恰好选 $K$ 个”求最值问题的方法。

使用 wqs 二分的条件是原问题具有凸性质所以我们可以基于二分查找出凸包切在哪里。

对于本题，我们先直接跑 kruskal，显然会有三种情况：

• 正好包含 $X$ 条 $0$ 边。
• 包含 $>X$ 条 $0$ 边。
• 包含 $<X$ 条 $0$ 边。

显然包含 $>X$ 条 $0$ 边的原因是 $0$ 边的边权较小，程序贪心地选择了 $>X$ 条 $0$ 边，$<X$ 同理，原因是 $0$ 边的边权偏大。

那我们对 $0$ 边的权值相应地进行一些加减操作就可以达成目标了。

考虑二分，我们二分对 $0$ 边的边权的偏移量 $\Delta w\in [-100,100]$。

我们将所有 $0$ 边的边权加上 $\Delta w$ 再跑 kruskal。判断当前选的边数是不是 $\ge X$，若是那么更新答案为 $ans=num-X\cdot mid$（其实就是更新可以使得恰好选 $X$ 条 $0$ 边的偏移量 $pos$ 为 $mid$，但是直接计算 $ans$ 并赋值也是等价的）。

最后输出答案即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 5e4 + 10;
const int MAXM = 1e5 + 10;
const int inf = 0x3f3f3f3f;

int n,m,X;
int num=0,cnt=0,ans=-1;
int fa[MAXN];
struct Edge{
	int u,v,w,c;
}e[MAXM];

bool cmp(Edge p,Edge q){
	if(p.w==q.w) return p.c<q.c;
	return p.w<q.w;
}

int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

void kruskal(){
	FL(i,1,n) fa[i]=i;
	sort(e+1,e+m+1,cmp); 
	FL(i,1,m){
		int u=e[i].u,v=e[i].v,w=e[i].w,c=e[i].c;
		if(find(u)==find(v)) continue;
		fa[find(u)]=find(v);
		num+=w,cnt+=!c;
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&X);
	FL(i,1,m) 
		scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].w,&e[i].c),e[i].u++,e[i].v++;
	int l=-110,r=110;
	while(l<=r){
		int mid=(l+r)>>1;
		FL(i,1,m) if(!e[i].c) e[i].w+=mid;
		num=0,cnt=0,kruskal();
		FL(i,1,m) if(!e[i].c) e[i].w-=mid;
		if(cnt>=X) ans=num-X*mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
}