题解：P12624 [ICPC 2025 NAC] Humans vs AI

· · 题解

blog

一个序列计数问题，把题意转化一下，发现如果没有 AI 操作，就是要求有多少个区间的 \sum_{i=l}^r(h_i-a_i)\ge0，其中负数的权值要乘上 k ，为求简便，之后的区间不加说明则为 h_i-a_i 所构成的序列中的区间。

考虑 AI 的操作，如果区间修改前为人类胜利，发现 AI 的最优决策一定是选中区间中最大的数交换，这样获得的收益最大，否则 AI 不需要修改操作。

这个启发我们根据最值分治，选取当前分治区间的最大值作为分治中心，这样跨越中心的区间 AI 一定会选择分治中心作为操作对象，我们成功地固定了式子中的一项。

容易计算出操作后的变化量 \Delta=Mx\times(k+1) ，问题转化为有多少区间满足 \sum_{i=l}^r(h_i-a_i)-\Delta\ge0 ,考虑启发式分治，枚举区间长度较小的一边，当枚举左区间时，问题转化为以下形式，询问有多少 R 满足

R\in(mid,r],S_R\ge\Delta+S_{i-1}

其中 S 为前缀和数组。右区间同理。

显然的一个二维数点问题，可以离线下来扫描线，也可以在线主席树维护，注意一下整形的溢出和边界的处理即可。


#include<bits/stdc++.h>
#define int long long
typedef long long ll; 
using namespace std;
const int M=5e6+10;
long long a[(int)5e6],h[(int)5e6];
int len,rt;
ll b[(int)5e6],tot;
int id(int x){return lower_bound(b+1,b+len+1,x)-b;}
struct ST{
    int f[(int)5e5][30],lg[(int)5e6];
    void build(int n){
        lg[1]=0;
        for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1,f[i][0]=i;
        f[1][0]=1;
        for(int i=1;(1<<i)<=n;i++){
            for(int j=1;j+(1<<i)-1<=n;j++){
                int lp=f[j][i-1],rp=f[j+(1<<(i-1))][i-1];
                f[j][i]=(h[lp]>h[rp]?lp:rp);
            }
        }   
    }
    int query(int l,int r){
        int k=lg[r-l+1],lp=f[l][k],rp=f[r-(1<<k)+1][k];
        return h[lp]>h[rp]?lp:rp;
    }
}s;
struct pre_sum{
    ll s[(int)5e6];
    void build(int n){for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];}
    int query(int l,int r){return s[r]-s[l-1];}
}t;
struct qry{ll v;int opt;};
vector<qry>q1[(int)5e6],q2[(int)5e6];
int n,k;long long ans;
void solve(int l,int r){
    if(l>r)return ; if(l==r)return ans+=h[l]==0,void();
    int mid=s.query(l,r);
    solve(l,mid-1),solve(mid+1,r);
    if(h[mid]<0)return ;
    if(mid-l+1<=r-mid){
        for(int i=mid;i>=l;i--){
            ll val=h[mid]*(k+1)+t.s[i-1];
            q1[r].push_back({val,1}),q1[mid-1].push_back({val,-1});
            b[++tot]=val;
        }
    }
    else {
        for(int i=mid;i<=r;i++){
            ll val=t.s[i]-h[mid]*(k+1);
            q2[mid].push_back({val,1}),q2[l-1].push_back({val,-1});     
            b[++tot]=val;
        }
    }
}
struct SEG{
    int cnt=0;
    int siz[(int)5e6],ls[(int)5e6],rs[(int)5e6];
    void add(int &i,int l,int r,int x){
        if(!i)i=++cnt;siz[i]++;if(l==r)return ;int mid=(l+r)>>1;
        x<=mid?add(ls[i],l,mid,x):add(rs[i],mid+1,r,x);
    }
    int query(int i,int l,int r,int x,int opt){
        if(l==r)return siz[i]*opt;int mid=(l+r)>>1;
        return x<=mid?query(ls[i],l,mid,x,opt):(query(rs[i],mid+1,r,x,opt)+siz[ls[i]]);
    }
}T;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>h[i];
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i],h[i]-=a[i];
    }
    for(int i=1;i<=n;i++)if(h[i]<0)h[i]*=k;
    s.build(n),t.build(n);
    solve(1,n);
    for(int i=0;i<=n;i++)b[++tot]=t.s[i];
    sort(b+1,b+tot+1);len=unique(b+1,b+tot+1)-b-1;
    for(int i=0;i<=n;i++){
        for(auto x:q2[i])ans+=T.query(rt,1,M,id(x.v)+1,1)*x.opt;
        T.add(rt,1,M,id(t.s[i])+1);
        for(auto x:q1[i])ans+=(i-T.query(rt,1,M,id(x.v)+1,0))*x.opt;
    }
    cout<<ans<<endl;
}