题解：P10861 [HBCPC2024] MACARON Likes Happy Endings

· · 题解

社贡快掉没了来写篇题解/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)，得证。