太久没写算法题了，又犯了傻逼错误。没开 long long 喜挂 100100 pts。

1816 反导弹系统

题意：一个 N×M(1≤N,M≤3000)N\times M(1\le N,M\le 3000) 的矩形，选出其中一个 A×BA\times B 的中矩形，再从这个中矩形中选出一个严格包含的 C×DC\times D 的小矩形，使得中矩形中小矩形之外的点的权值和最大。满足单点权值不超过 100100。

解析：经典单调队列题，本质就是两个滑动窗口套起来。

首先处理出二维前缀和，然后枚举一个方向（不妨固定住某行），然后用单调队列维护此时另一个方向（列）从头至尾移动时，以这个点作为右下角对应的中矩形中，能取出的小矩形权值和最小值，并把它存下来。再换另一个方向（列）枚举，用另一个单调队列维护这个方向（行）从头至尾移动时，以这个点作为右下角对应的中矩形中，刚才存下来的值中的最小值，这样就得到了这个中矩形中所有满足条件的小矩形的最小权值和，即可求得答案。复杂度为 O(NM)O(NM)。

代码中是维护的左上角对应的中矩形，影响不大，不过这时需要注意初始入队情况（因此维护右下角的会好写一些）。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/21.
//
#include<cstdio>
const int maxn=3e3;
int n,m,A,B,C,D;
int x[maxn+5][maxn+5];
int sum[maxn+5][maxn+5];
int q[maxn+5],l,r;
int ab[maxn+5][maxn+5],cd[maxn+5][maxn+5];
int minn[maxn+5][maxn+5];
int min(int a,int b)
{
    return (a<b)?a:b;
}
int max(int a,int b)
{
    return (a>b)?a:b;
}
int main()
{
    int ans=0;
    scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&C,&D);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&x[i][j]);
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i<=n-A+1&&j<=m-B+1)
                ab[i][j]=sum[i+A-1][j+B-1]-sum[i+A-1][j-1]-sum[i-1][j+B-1]+sum[i-1][j-1];
            if(i<=n-C+1&&j<=m-D+1)
                cd[i][j]=sum[i+C-1][j+D-1]-sum[i+C-1][j-1]-sum[i-1][j+D-1]+sum[i-1][j-1];
        }
    for(int i=1;i<=n-C;i++)
    {
        l=1,r=0;
        for(int j=1;j<=B-D-1;j++) {
            while(l<=r&&cd[i+1][q[r]]>=cd[i+1][j+1]) r--;
            q[++r]=j+1;
        }
        minn[i][1]=cd[i+1][q[l]];
        for(int j=2;j<=m-B+1;j++)
        {
            while(l<=r&&q[l]<=j) l++;
            while(l<=r&&cd[i+1][q[r]]>=cd[i+1][j+B-D-1]) r--;
            q[++r]=j+B-D-1;
            minn[i][j]=cd[i+1][q[l]];
        }
    }
    for(int j=1;j<=m-B+1;j++)
    {
        l=1,r=0;
        for(int i=1;i<=A-C-1;i++) {
            while(l<=r&&minn[q[r]][j]>=minn[i][j]) r--;
            q[++r]=i;
        }
        ans=max(ans,ab[1][j]-minn[q[l]][j]);
        for(int i=2;i<=n-A+1;i++)
        {
            while(l<=r&&q[l]<i) l++;
            while(l<=r&&minn[q[r]][j]>=minn[i+A-C-2][j]) r--;
            q[++r]=i+A-C-2;
            ans=max(ans,ab[i][j]-minn[q[l]][j]);
        }
    }
    printf("%d",ans);
    return 0;
}

1811 zhongzero的打怪兽之旅

题意：有 n(1≤n≤105)n(1\le n\le 10 ^{5}) 只怪兽，第 ii 只怪兽的血量为 ai(1≤ai≤109)a _{i}(1\le a_{i}\le 10 ^{9})，攻击力为 bi(0≤bi≤109)b _{i}(0\le b_{i}\le 10 ^{9})。保证 a1=1,bn=0a _{1}=1,b _{n}=0，aia _{i} 严格递增，bib _{i} 严格递减。现在你的武器每回合可以给一只怪兽造成一点伤害，然后你会受到你杀死的所有怪兽中，攻击力最小的怪兽的攻击力 bkb _{k} 的伤害。现在要求你第一回合必须杀死第一只怪兽，请问打死所有怪兽受到的伤害最小为多少？（杀死所有怪兽后不会再受到攻击）

解析：经典斜率优化。

首先容易证明先杀死前面的怪兽再杀死后面的怪兽一定比先杀死后面的怪兽再杀死前面的怪兽更优，证明如下：

假设现在已经杀死的怪兽中编号最大的为 kk，k<i<jk<i<j，如果我们先杀 ii 再杀 jj，则新受到的伤害为 bkai+biajb _{k}a _{i}+b _{i}a _{j}；反之，新受到的伤害为 bkaj+bjaib _{k}a _{j}+b _{j}a _{i}。我们将它们作差，可以得到

bkaj+bjai−bkai−biaj=aj(bk−bi)−ai(bk−bj)>aj(bk−bj)−ai(bk−bj)=(aj−ai)(bk−bj)>0\begin{aligned} b _{k}a _{j}+b _{j}a _{i} -b _{k}a _{i}-b _{i}a _{j} &=a _{j}(b _{k}-b _{i})-a _{i}(b _{k}-b _{j})\\ &>a _{j}(b _{k}-b _{j})-a _{i}(b _{k}-b _{j})\\ &=(a _{j}-a _{i})(b _{k}-b _{j})>0 \end{aligned}

即可证明 bkai+biaj<bkaj+bjaib _{k}a _{i}+b _{i}a _{j}<b _{k}a _{j}+b _{j}a _{i}，故先杀 ii 再杀 jj 更优。

这说明我们需要从小到大杀怪，然后就可以愉快的 DP 了。设 fif _{i} 为打死第 ii 只怪兽后受到的最小伤害，容易推出转移方程为

fi=min⁡1≤j<i(fj+bjai)f _{i}=\min _{1\le j<i}(f _{j}+b _{j}a _{i})

然后就是非常经典的斜率优化了，令 x=−bj,y=fj,k=ai,b=fix=-b _{j},y=f _{j},k=a _{i},b=f _{i}，即 b=−kx+yb=-kx+y，由于求最小值，且斜率 kk 与横坐标 xx 都是递增的，因此用单调队列维护下凸包即可。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/21.
//
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<string>
const int maxn=1e5;
long long n,a[maxn+5],b[maxn+5];
long long f[maxn+5];
long long q[maxn+5];
long long X(int i)
{
    return -b[i];
}
long long Y(int i)
{
    return f[i];
}
double k(int i)
{
    return 1.0*a[i];
}
double slope(int i,int j)
{
    return (double)(Y(i)-Y(j))/(X(i)-X(j));
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]);
    f[1]=0;
    int l=1,r=1;
    q[l]=1;
    for(int i=2;i<=n;i++)
    {
        while(l<r&&slope(q[l],q[l+1])<k(i)) l++;
        f[i]=f[q[l]]+b[q[l]]*a[i];
        while(l<r&&slope(q[r-1],q[r])>slope(q[r],i)) r--;
        q[++r]=i;
    }
    printf("%lld",f[n]);
    return 0;
}

1810 zhongzero的idea重启计划

题意：一个长度为 n(2≤n≤105)n(2\le n\le 10 ^{5}) 的序列 ai(1≤ai≤n)a _{i}(1\le a _{i}\le n)，将它分成 k(2≤k≤n)k(2\le k\le n) 个连续子序列，每个连续子序列的费用是其中相同元素的对数（如序列 121212121\mathtt{121212121} 中相同元素的对数为 (52)+(42)=16\dbinom{5}{2}+\dbinom{4}{2}=16），求所有连续子序列费用之和最小值。

解析：首先能够写出一个非常简单的 DP。设 fi,jf _{i,j} 代表前 ii 个数分 jj 个连续子序列的最小费用，则

fi,j=min⁡0≤k<i(fk,j−1+wk+1,i)f _{i,j}=\min _{0\le k<i}(f _{k,j-1}+w _{k+1,i})

其中 wi,jw _{i,j} 代表 [i,j][i,j] 中相同元素的对数，对于这个我们可以直接用双指针维护，类似莫队。此时暴力复杂度为 O(n2k)O(n ^{2}k)，显然无法通过这道题。

容易发现，固定 jj 后，fi,jf _{i,j} 是满足决策单调性的，我们可以用二分栈或者分治做法来维护它。但是为了快速求出 ww，我们可以采用分治做法，此时每一层的递归中总共会移动双指针 O(n)O(n) 次，而总共有 O(log⁡n)O(\log n) 层，于是就得到了一个 O(knlog⁡n)O(kn\log n) 的做法。

但是这个复杂度依然不能通过此题。我们考虑优化掉 jj 这一维，这里可以使用 wqs 二分，因为可以发现该 DP 满足凸优化的条件。于是我们可以二分一个附加的权值 WW，此时转移方程变为了

fi=min⁡0≤k<i−1(fk+wk+1,i)+Wf _{i}=\min _{0\le k<i-1}(f _{k}+w _{k+1,i})+W

该方程依然是满足决策单调性的，因此我们仍然可以用分治来做。但是这样有一个问题，就是在调用 fkf _{k} 时可能它还并没有被求出。我们可以在外面套上 CDQ 分治来解决。先算出左边的区间，然后用决策单调性将左边区间的值对右边进行转移后，再算右边的区间。此时如果 wqs 二分中 WW 的值域是 VV，那么复杂度即为 O(nlog⁡2nlog⁡V)O(n\log ^{2}n\log V)。

如果直接将 VV 设为 long long 的范围的话，手算一下此时大概有 2×1092\times 10 ^{9} 的计算量，过这道题依然会被卡。如何算出较准确的 WW 的范围呢？要使这个 WW 能够影响决策点的选择，显然 WW 要取在 [−max⁡fn,max⁡fn][-\max f _{n},\max f _{n}] 之间。考虑最坏的情况，由于 k(nk2)≤(n2)k\dbinom{\frac{n}{k}}{2}\le \dbinom{n}{2}，因此所有元素都相同时的答案是最大的。因此取 V=[−(n2),(n2)]V=\left[-\dbinom{n}{2},\dbinom{n}{2}\right] 即可，此时 VV 约为 n2n ^{2} 级别，那么 log⁡V\log V 也为 log⁡n\log n 级别，复杂度为 O(nlog⁡3n)O(n\log ^{3} n)，能够通过此题。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/29.
//
#include<cstdio>
#include<cstring>
const int maxn=1e5;
long long INF;
int n,k,a[maxn+5];
int cnt[maxn+5],num[maxn+5];
int nowl=1,nowr=0;
long long f[maxn+5],cost,Mid;
void move(int l,int r)
{
    while(nowl>l)
    {
        cost+=num[a[--nowl]];
        num[a[nowl]]++;
    }
    while(nowr<r)
    {
        cost+=num[a[++nowr]];
        num[a[nowr]]++;
    }
    while(nowl<l)
    {
        num[a[nowl]]--;
        cost-=num[a[nowl++]];
    }
    while(nowr>r)
    {
        num[a[nowr]]--;
        cost-=num[a[nowr--]];
    }
}
void dp(int l,int r,int L,int R)//用[l,r]的决策点更新[L,R]
{
    if(L>R)
        return;
    int mid=(L+R)>>1;
    int pos=0;
    long long minn=INF;
    for(int i=l;i<=r;i++)
    {
        move(i+1,mid);
        long long now=f[i]+cost+Mid;
        if(now<minn)
        {
            minn=now;
            pos=i;
        }
    }
    if(minn<f[mid])
    {
        f[mid]=minn;
        cnt[mid]=cnt[pos]+1;
    }
    dp(l,pos,L,mid-1);
    dp(pos,r,mid+1,R);
}
void CDQ(int l,int r)
{
    if(l>=r)
        return;
    int mid=(l+r)>>1;
    CDQ(l,mid);
    dp(l,mid,mid+1,r);
    CDQ(mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&k);
    INF=1ll*n*(n-1)/2;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    long long l=-INF/k,r=INF/k;
    while(l<=r)
    {
        Mid=(l+r)/2;
        memset(f,0x3f,sizeof(long long)*(n+1));
        f[0]=cnt[0]=0;
        CDQ(0,n);
        if(cnt[n]>k)
            l=Mid+1;
        else
            r=Mid-1;
    }
    Mid=l;
    memset(f,0x3f,sizeof(long long)*(n+1));
    f[0]=cnt[0]=0;
    CDQ(0,n);
    printf("%lld",f[n]-1ll*k*Mid);
    return 0;
}