标签：variant   输入输出   play   return   中间   open   sub   not   app   

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,S_i)\) 看成点，那么我们要找的就是两个点构成的矩形面积的最大值。

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

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

若左下角有决策点 \(y ，右上角有决策点 \(i ，并且 \(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\) 而 \(j>i,S_j，所以把 \(i\) 换成 \(j\)，把 \(S_i\) 换成 \(S_j\) 之后该不等式依然成立。也就是说

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

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

时间复杂度大概一个log？

vector lef,rig;
vector a;
vector 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 x,vector y){
        a.resize(n);
        CO int64 mod=1LL>20)%q+o;
            int64 s0=s*621%mod;
            int64 s1=s*825%mod;
            int64 s2=s*494%mod;
            s=s*23%mod;
            s=((spre[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

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 points[N];
int lastmin[N];
ll t;
vector > group[N];
vector dp[N];
vector querys[N*4];
#define lc (x>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>1;
    if(qlmid) change(rc,mid+1,r,ql,qr,v);
}
void solve(co vector&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;k0&&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>1;
            if(lastmin[M]>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>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

标签：variant   输入输出   play   return   中间   open   sub   not   app   

原文地址：https://www.cnblogs.com/autoint/p/10599067.html