自动搬运

查看原文

来自洛谷，原作者为

	Wind_Leaves_ShaDow 别摆了。

搬运于2025-08-24 23:01:57，当前版本为作者最后更新于2025-02-05 16:00:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

社贡快掉没了来写篇题解/kk。

题意

你需要把一个序列分成至多 $k$ 段，定义每一段 $[l,r]$ 的花费为其中数对 $(x,y)$ 的个数，满足 $x\le y$ 且 $\bigoplus_{i=x}^y a_i=d$。其中 $d$ 是给定的常数。

问最小花费。$n\le10^5,d,a_i\le10^6,k\le20$。

题解

设 $f_{i,j}$ 表示前 $i$ 个数分成 $j$ 段最小花费。转移为 $f_{i,j}=min\{f_{k-1,j-1}+w(k,i)\}$。其中 $w(k,i)$ 即为 $[k,i]$ 分为一段的花费。

观察发现这个式子很能够决策单调性优化，可以证明其 $w(k,i)$ 满足四边形不等式。如果需要的话证明在代码后面。

然后很好做了，分治每一层得到答案，这里不多赘述。

思考一下没有什么数据结构支持快速得到 $w$ 的值，于是自然而然地想到类似莫队移动指针的维护方式。移动指针的复杂度是 $O(n\log n)$ 的，证明考虑刻画指针移动路径，每一层指针只会在候选区间进行线性次数的移动，而分治一共是 $\log$ 层。

考虑令位置 $i$ 的前缀异或和为 $s_i$，则一次查询变成询问 $l\le x\le y\le r$ 且 $s_{x-1}\oplus s_y=d$ 的 $(x,y)$ 个数。这个很容易统计出来，开两个桶记录 $s_{x-1}$ 的集合和 $s_y$ 的集合。注意移动指针时的删除添加顺序。

于是做完了，一共有 $k$ 层每层做一次分治，复杂度 $O(kn\log n)$。

没有仔细想，但是感觉如果 $k$ 大一点是不是可以套上 wqs 二分做到 $O(n\log n\log V)$？

注意到 $d\le 10^6$ 不代表桶的上界是 $10^6$。

代码

#include <bits/stdc++.h>
#define lint __int128
#define int long long
#define fi first 
#define se second
#define Rg register
#define Ri Rg int
#define Il inline
#define vec vector
#define pb push_back
#define IT ::iterator
#define p_que priority_queue

using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=1e5,M=(1<<20),Inf=1e18;
const db eps=1e-9,pi=acos(-1.0);

Il int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}

Il void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
    return;
}

int n,m,K,a[N+5],dp[N+5][25],lp=1,rp=0,ans=0,gl[M+5],gr[M+5];

Il void adl(int p){gr[a[p]]++;ans+=gr[K^a[p-1]];gl[a[p-1]]++;return;}

Il void del(int p){ans-=gr[K^a[p-1]];gr[a[p]]--;gl[a[p-1]]--;return;}

Il void adr(int p){gl[a[p-1]]++;ans+=gl[K^a[p]];gr[a[p]]++;return;}

Il void der(int p){ans-=gl[K^a[p]];gl[a[p-1]]--;gr[a[p]]--;return;}

Il int qur(int l,int r){
	while(lp>l)adl(--lp);
	while(lp<l)del(lp++);
	while(rp<r)adr(++rp);
	while(rp>r)der(rp--);
	return ans;
}

Il void solve(int l,int r,int zl,int zr,int ly){
	int mid=(l+r)>>1,p=zl;if(l>r||zl>zr)return;
	dp[mid][ly]=Inf;
	for(Ri i=zl;i<=min(mid,zr);i++){
		int tmp=dp[i-1][ly-1]+qur(i,mid);
		if(tmp<dp[mid][ly])dp[mid][ly]=tmp,p=i;
	}
	solve(l,mid-1,zl,p,ly),solve(mid+1,r,p,zr,ly); 
	return;
}

signed main(){
    n=read(),m=read(),K=read();for(Ri i=1;i<=n;i++)a[i]=read();
    for(Ri i=1;i<=n;i++)a[i]^=a[i-1],dp[i][0]=Inf;
    for(Ri i=1;i<=m;i++)solve(1,n,1,n,i);
    ans=Inf;for(Ri i=1;i<=m;i++)ans=min(ans,dp[n][i]);
    cout<<ans;
	return 0;
}

证明满足四边形不等式

设有 $a<b<c<d$。

我们的权值函数统计的是类似一种合法点对的答案，考虑对应到坐标系中，$w(a,b)$ 统计的实际上就是以 $(a,a),(b,b)$ 为对角线的矩形中合法点对数（这里除对角线上每个点对会被算两次，但是并不影响证明）。

于是将 $w(a,d)+w(b,c),w(a,c)+w(b,d)$ 对应到坐标系，发现前者比后者多覆盖了以 $(a,c),(b,d)$ 和 $(c,a),(d,b)$ 为对角线的两个小矩形。

显然就有 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$，得证。