MaxSquare

给定一个长度为 \(n\) 的序列 \(B_1, B_2,\dots, B_n\)，在此基础上构造了一个矩阵 \(A\)，满足 \(A_{i,j}= b_i+ b_j\)。求 \(A\) 权值和最大的子正方形。

\(n ≤ 10^5\)。

推式子

既然 \(A\) 的构造方式很独特，那么我们先把答案式暴力展开。

\[ ans=\max_{c=1}^n \max_{x,y} \sum_{i=x}^{x+c-1}\sum_{i=y}^{y+c-1} A_{i,j}\=\max_{c=1}^n \max_{x,y} \sum_{i=x}^{x+c-1}\sum_{i=y}^{y+c-1} (B_i+B_j)\=\max_{c=1}^n c \max_{x,y} \left(\sum_{i=x}^{x+c-1}B_i+\sum_{i=y}^{y+c-1} B_j\right)\\]

\(x,y\) 的枚举是等价的，两者最终的结果一定是一样的，所以改成两倍。

\[ ans=2\max_{c=1}^n c \max_x \sum_{i=x}^{x+c-1}B_i\=2\max_{c=1}^n c \max_x (S_{x+c-1}-S_{x-1}) \]

将 \(c\) 的枚举转化为差计算。

\[ ans=2 \max_{j < i} (i-j)(S_i-S_j) \]

分治套路

将 \((i,S_i)\) 看成点，那么我们要找的就是两个点构成的矩形面积的最大值。

注意到若 \(j_1 < j_2,S_{j_1} < S_{j_2}\)，那么选 \(j_2\) 做左下角一定不优；若 \(i_1 < i_2,S_{i_1} < S_{i_2}\)，那么选 \(i_1\) 做右上角一定不优。

我们可以用单调栈预处理出哪些点可以做左下角，哪些点可以做右上角。左下角一定是下凸壳的形式，右上角一定是上凸壳的形式。

若左下角有决策点 \(y < x\)，右上角有决策点 \(i < j\)，并且 \(i\) 的最优方案是 \(x\)，那么有

\[ (i-x)(S_i-S_x) > (i-y)(S_i-S_y)\xS_x-yS_y-(x-y)S_i-i(S_x-S_y) > 0 \]

因为 \(-(x-y) < 0,-(S_x-S_y)>0\) 而 \(j>i,S_j<S_i\)，所以把 \(i\) 换成 \(j\)，把 \(S_i\) 换成 \(S_j\) 之后该不等式依然成立。也就是说

\[ (j-x)(S_j-S_x) > (j-y)(S_j-S_y) \]

所以这个最优方案具有决策单调性。那么写一个值域分治就好了。

时间复杂度大概一个log？

vector<int> lef,rig;
vector<int> a;
vector<int64> pre;
int64 ans=0;

IN int64 calc(int l,int r){
    return (rig[r]-lef[l])*(pre[rig[r]]-pre[lef[l]]);
}
void solve(int l,int r,int L,int R){
    if(l>r) return;
    int mid=(l+r)>>1;
    int mark=L;
    int64 ans=calc(mid,L);
    for(int i=L+1;i<=R;++i)if(ans<calc(mid,i))
        ans=calc(mid,i),mark=i;
    ::ans=max(::ans,ans);
    solve(l,mid-1,L,mark),solve(mid+1,r,mark,R);
}

class MaxSquare{
public:
    int64 getMaxSum(int n,int64 s,int q,int o,vector<int> x,vector<int> y){
        a.resize(n);
        CO int64 mod=1LL<<51;
        for(int i=0;i<n;++i){
            a[i]=(s>>20)%q+o;
            int64 s0=s*621%mod;
            int64 s1=s*825%mod;
            int64 s2=s*494%mod;
            s=s*23%mod;
            s=((s<<10)+s2)%mod;
            s=((s<<10)+s1)%mod;
            s=((s<<10)+s0+11)%mod;
        }
        for(int i=0;i<(int)x.size();++i) a[x[i]]=y[i];
        pre.resize(n+1),pre[0]=0;
        for(int i=0;i<n;++i) pre[i+1]=pre[i]+a[i];
        for(int i=0;i<=n;++i)
            if(lef.empty() or pre[lef.back()]>pre[i]) lef.push_back(i);
        for(int i=n;i>=0;--i)
            if(rig.empty() or pre[i]>pre[rig.back()]) rig.push_back(i);
        reverse(rig.begin(),rig.end());
        solve(0,lef.size()-1,0,rig.size()-1);
        if(ans==0){
            ans=a[0]; // edit 1: must choose
            for(int i=1;i<n;++i)
                ans=max(ans,(int64)a[i]);
        }
        return 2*ans;
    }
};

//int main(){
//  MaxSquare tmp;
//  int64 ans=tmp.getMaxSum(10,42,40,-5,{},{});
//  printf("%lld\n",ans);
//  return 0;
//}

Mowing Mischief

5 20
19 1
2 6
9 15
10 3
13 11

117

B君的讲课

那个割草其实就是两个点之间的矩形面积，所以说这题求的就是找出极大纵坐标最长上升子序列，并使得相邻两点之间构成的矩形面积和最小，坐标没有重复的，出题人很良心。

发现在最长上升子序列中每个点的排名是固定的，所以可以按照排名把点分层，每层之间转移。

考虑每层之间如何转移，每层的点一定是从左上到右下的，并且这个转移具有单调性，即后一层的点后移的时候，前一层的要最优必须前移才行。而这种单调性可以使用整体二分解决，即先找后一层中间的点的最优转移在前一层的那个点，更新答案后左右递归分治，时间复杂度\(O(n \log n)\)。

但是相邻两层之间并不是每个点都可以互相转移到的，所以要维护前一层哪些点能转移到后一层的哪些点。显然后一层的每个点一定能被前一层的一个区间内的点转移到，也就是每一次都给一个区间添上到后一层的某个点的转移。这个可以用线段树分治来维护，即把待操作的区间按照线段树的方式分解成\(O(\log n)\)个区间添上转移，最后遍历线段树处理转移。

总时间复杂度\(O(n \log^2 n)\)

co int N=2e5+10;
int n;
pair<int,int> points[N];
int lastmin[N];
ll t;
vector<pair<int,int> > group[N];
vector<ll> dp[N];
vector<int> querys[N*4];
#define lc (x<<1)
#define rc (x<<1|1)
void build(int x,int l,int r){
    querys[x].clear();
    if(l==r) return;
    int mid=l+r>>1;
    build(lc,l,mid),build(rc,mid+1,r);
}
void change(int x,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr) return querys[x].push_back(v);
    int mid=l+r>>1;
    if(ql<=mid) change(lc,l,mid,ql,qr,v);
    if(qr>mid) change(rc,mid+1,r,ql,qr,v);
}
void solve(co vector<int>&querys,int l,int r,int L,int R,int index){
    if(l>r) return;
    int mid=l+r>>1,j=querys[mid];
    ll best=1e18;
    int pos=-1;
    for(int k=L,dx,dy;k<=R;++k){
        dx=group[index][j].first-group[index-1][k].first,
        dy=group[index][j].second-group[index-1][k].second;
        if(dx>0&&dy>0){
            ll tmp=dp[index-1][k]+(ll)dx*dy;
            if(best>tmp) best=tmp,pos=k;
        }
    }
    dp[index][j]=min(dp[index][j],best);
    solve(querys,l,mid-1,pos,R,index),solve(querys,mid+1,r,L,pos,index);
}
void query(int x,int l,int r,int index){
    solve(querys[x],0,querys[x].size()-1,l,r,index);
    if(l==r) return;
    int mid=l+r>>1;
    query(lc,l,mid,index),query(rc,mid+1,r,index);
}
int main(){
//  freopen(".in","r",stdin),freopen(".out","w",stdout);
    read(n),read(t);
    for(int i=1;i<=n;++i) read(points[i].first),read(points[i].second);
    points[n+1]=make_pair(t,t);
    sort(points,points+n+2);
    int length=-1;
    for(int i=0;i<n+2;++i){
        int L=-1,R=length;
        while(L<R){
            int M=L+R+1>>1;
            if(lastmin[M]<points[i].second) L=M;
            else R=M-1;
        }
        lastmin[L+1]=points[i].second;
        group[L+1].push_back(points[i]);
        length=max(length,L+1);
    }
    dp[0].resize(1);
    dp[0][0]=0;
    for(int i=1;i<=length;++i){
        dp[i].resize(group[i].size());
        build(1,0,dp[i-1].size()-1);
        for(int j=0;j<group[i].size();++j){
            dp[i][j]=1e18;
            int st=-1,ed=-1;
            int L=0,R=group[i-1].size()-1;
            while(L<R){
                int M=L+R>>1;
                if(group[i-1][M].second>group[i][j].second) L=M+1;
                else R=M;
            }
            st=L;
            L=0,R=group[i-1].size()-1;
            while(L<R){
                int M=L+R+1>>1;
                if(group[i-1][M].first>group[i][j].first) R=M-1;
                else L=M;
            }
            ed=L;
            change(1,0,group[i-1].size()-1,st,ed,j);
        }
        query(1,0,group[i-1].size()-1,i);
    }
    printf("%lld\n",dp[length][0]);
    return 0;
}

Topcoder MaxSquare 和 [USACO19FEB]Mowing Mischief