2023-07-16 16:44:17
发布于：广东
78阅读
0回复
0点赞
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define M 1000000
#define LL long long
#define INF (LL)1e18
using namespace std;
int n,m;struct P {int x,y;I bool operator < (Con P& o) Con {return x<o.x;}}p[N+5];
vector<P> w[N+5];vector<LL> f[N+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
char oc,FI[FS],*FA=FI,*FB=FI;
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
}using namespace FastIO;
namespace DP//决策单调性优化DP
{
P p[N+5],q[N+5];LL f[N+5],ans[N+5];
I void Solve(CI l,CI r,CI L,CI R)//分治决策单调性
{
#define Calc(i) (f[i]+1LL*(q[mid].x-p[i].x)*(q[mid].y-p[i].y))
if(l>r) return;RI mid=l+r>>1,g=L;for(RI i=L+1;i<=R;++i) Calc(g)>Calc(i)&&(g=i);//枚举最优决策点
ans[mid]=Calc(g),Solve(l,mid-1,g,R),Solve(mid+1,r,L,g);//这一层越靠后的位置，越可能选择上一层靠前的位置
}
}
int sz;class SegmentTree
{
private:
#define PT CI l=0,CI r=sz-1,CI rt=1
#define LT l,mid,rt<<1
#define RT mid+1,r,rt<<1|1
vector<int> V[N<<2];
public:
I void K(CI L,CI R,CI p,PT)//把区间扔到线段树上
{
if(L<=l&&r<=R) return (void)V[rt].push_back(p);
RI mid=l+r>>1;L<=mid&&(K(L,R,p,LT),0),R>mid&&(K(L,R,p,RT),0);
}
I void Solve(CI id,PT)//线段树分治
{
if(!V[rt].empty())
{
RI i,sz;for(i=l;i<=r;++i) DP::p[i-l+1]=w[id-1][i],DP::f[i-l+1]=f[id-1][i];
for(sz=V[rt].size(),i=0;i^sz;++i) DP::q[i+1]=w[id][V[rt][i]];
for(DP::Solve(1,sz,1,r-l+1),i=0;i^sz;++i) f[id][V[rt][i]]=min(f[id][V[rt][i]],DP::ans[i+1]);V[rt].clear();//与原有答案比较
}
if(l==r) return;RI mid=l+r>>1;Solve(id,LT),Solve(id,RT);
}
}S;
struct TreeArray
{
int a[M+5];I void U(RI x,CI v) {W(x<=m&&a[x]<v) a[x]=v,x+=x&-x;}
I int Q(RI x) {RI t=0;W(x) t=max(t,a[x]),x-=x&-x;return t;}
}T;
I int FX(Con vector<P>& v,CI x) {RI l=0,r=v.size()-1,mid;W(l^r) v[mid=l+r+1>>1].x<x?l=mid:r=mid-1;return l;}//二分最后的横坐标小于x的位置
I int FY(Con vector<P>& v,CI y) {RI l=0,r=v.size()-1,mid;W(l^r) v[mid=l+r-1>>1].y<y?r=mid:l=mid+1;return r;}//二分第一个横坐标小于y的位置
int main()
{
RI i,j,x;for(read(n),read(m),i=1;i<=n;++i) read(p[i].x),read(p[i].y);
RI Mx=0;for(sort(p+1,p+n+1),i=1;i<=n;++i) T.U(p[i].y,x=T.Q(p[i].y)+1),w[x].push_back(p[i]),Mx=max(Mx,x);//按横坐标排序，树状数组求LIS并分层
for(w[0].push_back((P){0,0}),f[0].push_back(0),i=1;i<=Mx;S.Solve(i++))//分层转移
for(sz=w[i-1].size(),x=w[i].size(),j=0;j^x;++j) S.K(FY(w[i-1],w[i][j].y),FX(w[i-1],w[i][j].x),j),f[i].push_back(INF);//求出转移范围，利用线段树分治化掉转移限制
LL t=INF;for(j=0;j^x;++j) t=min(t,f[Mx][j]+1LL*(m-w[Mx][j].x)*(m-w[Mx][j].y));return printf("%lld\n",t),0;//枚举最后一层点求答案
}
有帮助，赞一个