小清新决策单调性 [ABC289G]

· · 题解

Part1 题意简述

### Part2 问题转化 将客人按 $B_i$ 从大到小排序，若一个客人会买，那么期望值比他大（比他靠前）的都会购买，考虑一件商品 $y$，恰好让第 $x$ 位客人购买，那么销售额就为（不考虑 $x$ 后面与 $x$ 期望值相等的人，因为他们更优，会算到）$w(x,y)=x(B_x+C_y)$。 ### Part3 解决问题 以上是一个一次函数，你已经可以用 Li-Chao Tree 解决了，不过我觉得推出四边形不等式用分治更好写一些，所以： 将商品按 $C_i$ 从小到大排序，对于任意的 $a<b,c<d$，都有 $w(a,c)+w(b,d)-w(a,d)-w(b,c) =a(B_a+C_c)+b(B_b+C_d)-a(B_a+C_d)-b(B_b+C_c) =(a-b)(C_c-C_d)\ge 0

即 w(a,c)+w(b,d)\ge w(a,d)+w(b,c)，相交优于包含，满足四边形不等式，具有决策单调性，然后分治解决。

时间复杂度 O((n+m)\log(n+m))，空间 O(n+m)：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
using ll=long long;
int T,n,m,c[N],b[N],p[N];
ll ans[N];
ll W(int l,int r){
    return ll(b[l]+c[p[r]])*l;
}
void solve(int l,int r,int L,int R){
    if(l>r||L>R)return;
    int md=L+R>>1,i,nl=l;ll mx=W(l,md),nw;
    for(i=r;i>l;--i)if((nw=W(i,md))>mx)mx=nw,nl=i;
    ans[p[md]]=mx;
    if(L<md)solve(l,nl,L,md-1);
    if(md<R)solve(nl,r,md+1,R);
}
int main(){
    ios::sync_with_stdio(false);
    int i,x,y,l,r;
    cin>>m>>n;
    for(i=1;i<=m;++i)cin>>b[i];
    for(i=1;i<=n;++i)cin>>c[i],p[i]=i;
    sort(b+1,b+m+1,greater<int>());
    sort(p+1,p+n+1,[&](int x,int y){return c[x]<c[y];});
    solve(1,m,1,n);
    for(i=1;i<=n;++i)printf("%lld%c",ans[i]," \n"[i==n]);
    return 0;
}