线段树+决策单调性-好题-[USACO19FEB]Mowing Mischief-解题报告

· · 题解

好题！我把minmax看反推了半天 Blog

我们肯定要求出以每个点结尾的LIS长度，然后长度相差1的点之间转移。

性质：LIS相同的点，横坐标增加，纵坐标减小

我们列出转移方程：

dp_i=\min_{j\in\ L[l-1] ,\ x_j< x_i,y_j< y_i}\{dp_j+(x_i-x_j)(y_i-y_j)\}

看着比较像斜率优化，但是好像化简不到标准形式？这是就要用到优化DP的另一个利器了：决策单调性！

考虑 j,k(k<j) 两处转移，令 j 优于 k，则

dp_j+x_jy_j-x_iy_j-x_jy_i\leq dp_k+x_ky_k-x_iy_k-x_ky_i (y_k-y_j)x_i+(x_k-x_j)y_i\leq dp_k+x_ky_k-dp_j-x_jy_j

注意到 y_k-y_j和 x_k-x_j必然一正一负，因此这个半平面是一个斜率为正的半平面，一定会将下一层的点分为前后两部分，因而若排除掉 x_j\leq x_i,y_j\leq y_i的限制，该 DP 的转移具有决策单调性。

这道题的决策单调性是反的：后边的点更可能成为前边的点的最优决策点。

然后考虑如何解决x_j\leq x_i,y_j\leq y_i的限制。

注意到，如果我们把点按照横坐标递增编号，那么同一层中，满足x_j\leq x_i,y_j\leq y_i的编号是连续的，这启发我们把询问放到线段树上，对于线段树的每个节点。把节点上的询问拿出来，跑一边决策单调性。

复杂度O(n\log ^2n)

#define N 200005
int n;
struct Node
{
    int x,y;
    Node() {}
    Node(const int _x,const int _y) {x=_x,y=_y;}
    friend bool operator<(const Node &a,const Node &b) {return a.x<b.x;}
} pt[N];
il LL dis(const int a,const int b) {return abs((LL)(pt[a].x-pt[b].x)*(pt[a].y-pt[b].y));}
const LL inf=1ll<<60;
LL dp[N];
void solve(int l,int r,int al,int ar,const vector<int> &q,const vector<int> &g)
{
    int _mid=(l+r)>>1,mid=q[_mid],am=0; LL t=inf;
    for(ri i=al; i<=ar; ++i) if(ckmin(t,dp[g[i]]+dis(g[i],mid))) am=i;
    ckmin(dp[mid],t);
    if(l<_mid) solve(l,_mid-1,am,ar,q,g);
    if(_mid<r) solve(_mid+1,r,al,am,q,g);
}
#define M N*4
#define ls (x<<1)
#define rs (x<<1|1)
const int rt=1;
vector<int>qu[M];
void upd(int x,int l,int r,int p,const vector<int> &g)
{
    if(pt[g[l]].y<=pt[p].y&&g[r]<=p) return qu[x].pb(p);
    if(pt[g[r]].y>pt[p].y||g[l]>p) return;
    gm;
    upd(ls,l,mid,p,g),upd(rs,mid+1,r,p,g);
}
void work(int x,int l,int r,const vector<int> &g)
{
    if(Size(qu[x]))
    {
        solve(0,Size(qu[x])-1,l,r,qu[x],g);
        qu[x].clear();
    }
    if(l==r) return;
    gm;
    work(ls,l,mid,g),work(rs,mid+1,r,g);
}
vector<int>pos[N];
int T;
int tre[N];
void upd(int x,int k)
{
    for(; x<=n; x+=x&-x) ckmax(tre[x],k);
}
int ask(int x)
{
    int res=0;
    for(; x; x-=x&-x) ckmax(res,tre[x]);
    return res;
}
int lis[N];
int ui[N],cu;
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("ot.out","w",stdout);
#endif
    in(n,T);
    for(ri i=1; i<=n; ++i) in(pt[i].x,pt[i].y),ui[i]=pt[i].y;
    sort(ui+1,ui+1+n);
    sort(pt+1,pt+1+n);
    int mx=0;
    for(ri i=1,L; i<=n; ++i)
    {
        L=lower_bound(ui+1,ui+1+n,pt[i].y)-ui;
        lis[i]=ask(L)+1,ckmax(mx,lis[i]);
        upd(L,lis[i]);
        pos[lis[i]].pb(i);
    }
    for(ri i=1; i<=n; ++i) dp[i]=inf;
    for(solid i:pos[1]) dp[i]=(LL)pt[i].x*pt[i].y;
    for(ri i=2; i<=mx; ++i)
    {
        for(solid j:pos[i]) upd(rt,0,Size(pos[i-1])-1,j,pos[i-1]);
        work(rt,0,Size(pos[i-1])-1,pos[i-1]);
    }
    LL ans=inf;
    for(solid i:pos[mx]) ckmin(ans,dp[i]+(LL)(T-pt[i].x)*(T-pt[i].y));
    out(ans);
    return 0;
}