题目大意：

给定平面上的一些点，求这些点的一个\(LIS\)，并且还需要满足下列式子最小：

\[ \sum_{i=1}^{n-1}(a[i+1].x-a[i].x)*(a[i+1].y-a[i].y) \]

题解：

比较巧妙的一道题。

首先我们需要找出一个性质，我们先令\(dp[i]\)表示以\(i\)点结尾的\(LIS\),然后这些\(LIS\)相同的点在平面上是横坐标递增，纵坐标递减的，下面我们说的转移点的顺序都是按照这个顺序来的。

然后我们在观察转移，我们令两个转移点\(j\)和\(k\),若\(k\)比\(j\)更优，那么有：

\[ dp[k]+(a[i].x-a[k].x)*(a[i].y-a[k].y)\geq dp[j]+(a[i].x-a[j].x)*(a[i].y-a[j].y) \]

\[ a[i].x*(a[j].y-a[k].y)+a[i].y*(a[j].x-a[k].x)\geq dp[j]-dp[k]+a[j].x*a[j].y-a[k].x*a[k].y \]

\[ A*a[i].x+B*a[i].y\geq C \]

可以看出，这其实是一个半平面,结合上面的性质，对于一排待转移点，更优的转移是一段前缀或者一段后缀，这启发我们这道题中有决策单调性。

但是这个东西还有一个条件就是\(a[i].x\geq a[j].x\ \ a[i].y\geq a[j].y\)，这个东西其实我们发现合法的转移点也是一段连续的区间，这启发我们在外面线段树分治解决这个限制。

对于决策单调性的部分，我们可以令\(k\)是\(j\)的后面一个点，那么上面的\(A\)是负的\(B\)是正的，所以合法的区域在直线上方，按照这个做决策单调性就好了。

代码

#include
    
     #define M 1000009#define N 200009using namespace std;typedef long long ll;vector
     
      vec[N],now;vector
      
       ::iterator it;int n,T,dp[N];ll f[N],ans;inline ll rd(){    ll x=0;char c=getchar();bool f=0;    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct BIT{    int tr[M];    inline void add(int x,int y){        while(x<=T)tr[x]=max(tr[x],y),x+=x&-x;    }    inline int query(int x){        int ans=0;        while(x)ans=max(ans,tr[x]),x-=x&-x;        return ans;    }}T1;struct point{    int x,y;    inline bool operator <(const point &b)const{        if(x!=b.x)return x