YbtOJ 474「决策单调性优化 dp」网格选点

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e6+100;Cn LL inf=1e12;
int n,Tt,f[N],Ans;LL ans=inf,dp[N];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
PA a[N];
vector<int> v[N],G[N];
#define pb push_back
class BIT{
    private:
        int T[N];
    public:
        I void U(CI p,CI v){RI i;for(i=p+1;i<=Tt+1;i+=i&-i) T[i]=max(T[i],v);}
        I int Q(CI p){RI i,S=0;for(i=p+1;i;i-=i&-i) S=max(S,T[i]);return S;}
}T;
#define mid (l+r>>1)
I void Sol(CI L,CI R,CI l,CI r,CI x,CI d){
    if(l>r) return ;RI i,id=0;LL Mn=inf;
    for(i=L;i<=R;i++) dp[v[d-1][i]]+1LL*(a[G[x][mid]].fi-a[v[d-1][i]].fi)*(a[G[x][mid]].se-a[v[d-1][i]].se)<Mn&&
        (Mn=dp[v[d-1][i]]+1LL*(a[G[x][mid]].fi-a[v[d-1][i]].fi)*(a[G[x][mid]].se-a[v[d-1][i]].se),id=i);
    dp[G[x][mid]]=min(dp[G[x][mid]],Mn);
    Sol(id,R,l,mid-1,x,d),Sol(L,id,mid+1,r,x,d);
}
class SegmentTree{
    private:
        #define PT CI x,CI l,CI r
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
    public:
        I void U(CI p,CI d,PT){
            #define chk(o) (a[o].fi<a[p].fi&&a[o].se<a[p].se)
            if(a[v[d-1][l]].fi>a[p].fia[v[d-1][r]].se>a[p].se) return ;if(chk(v[d-1][l])&&chk(v[d-1][r])) return void(G[x].pb(p));U(p,d,LT),U(p,d,RT);
        }I void Q(CI d,PT){if(Sol(l,r,0,G[x].size()-1,x,d),G[x].clear(),l==r) return ;Q(d,LT),Q(d,RT);}
}S;
int main(){
    freopen("grid.in","r",stdin),freopen("grid.out","w",stdout);
    RI i;for(read(n,Tt),i=1;i<=n;i++) read(a[i].fi,a[i].se);a[++n]=MP(0,0),a[++n]=MP(Tt,Tt);for(sort(a+1,a+n+1),i=1;i<=n;i++) f[i]=T.Q(a[i].se)+1,T.U(a[i].se,f[i]),v[f[i]].pb(i);
    for(i=1;i<=n;i++) Ans=max(Ans,f[i]),dp[i]=f[i]>1?inf:0LL;for(i=2;i<=Ans;S.Q(i,1,0,v[i-1].size()-1),i++) for(auto j:v[i]) S.U(j,i,1,0,v[i-1].size()-1);
    for(i=1;i<=n;i++) f[i]==Ans&&(ans=min(ans,dp[i]));return writeln(ans),0;
}