题解

太酷啦

#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <cstdio>
using namespace std;
#define MAXN 300001
#define INF 0x3f3f3f3f3f3f3f

int N, L;
int x[MAXN], y[MAXN];
int xid[MAXN];
int lis[MAXN];
long long dp[MAXN];
long long dpPlus[MAXN];

vector<int> levels[MAXN];

bool cmpx(int a,int b)	
{
	return x[a] < x[b];
}

void computeLIS()
{
	levels[0].push_back(xid[0]);
	lis[xid[0]] = 0;
	int mx = 0;
	for(int i=1;i<N;i++)
	{
		int cur = xid[i];
		int low = -1;
		int high = mx;
		while(low != high)
		{
			int mid = (low+high+1)/2;
			if(y[levels[mid].back()] < y[cur]) low = mid;
			else high = mid-1;
		}
		levels[low+1].push_back(cur);
		mx = max(mx, low+1);
		lis[cur] = low+1;
	}
}

long long cost(int i,int j)
{
	return dp[i] + x[i]*((long long)y[i]) - x[i]*((long long)y[j]) - y[i]*((long long)x[j]) + x[j]*((long long)y[j]);
}

int findLocOvertake(int l,int i,int j) 
{
	int low = 0;
	int high = levels[l].size();
	while(low != high)
	{
		int mid = (low+high)/2;
		if(cost(i, levels[l][mid]) < cost(j, levels[l][mid])) high = mid;
		else low = mid+1;
	}
	return low;
}

int firstDom[MAXN];
int lastDom[MAXN];

int findFirst(int l,int i)	
{
	int low = 0;
	int high = levels[l].size()-1;
	while(low != high)
	{
		int mid = (low + high)/2;
		if(x[levels[l][mid]] > x[i]) high = mid;
		else low = mid+1;
	}
	if(x[levels[l][low]] > x[i] && y[levels[l][low]] > y[i])
		return low;
	return -1;
}

int findLast(int l,int i) 
{
	int low = 0;
	int high = levels[l].size()-1;
	while(low != high)
	{
		int mid = (low + high + 1)/2;
		if(y[levels[l][mid]] > y[i]) low = mid;
		else high = mid-1;
	}
	if(x[levels[l][low]] > x[i] && y[levels[l][low]] > y[i])
		return low;
	return -1;
}

int que[MAXN];
int overtake[MAXN];
vector<int> level;

void solveStartingRegion(int l, int iStart, int iEnd, int qStart, int qEnd) 
{
	int len = 0;
	int i = iStart;
	for(int j=qStart;j<=qEnd;j++)
	{
		int q = levels[l+1][j];
		while(i <= iEnd && firstDom[i] <= j)
		{
			while(len >= 2 && overtake[len-2] <= findLocOvertake(l+1, que[len-1], level[i]))
				len--;
			que[len] = level[i];
			if(len >= 1)
				overtake[len-1] = findLocOvertake(l+1, que[len-1], level[i]);
			len++;
			i++;
		}
		while(len >= 2 && overtake[len-2] <= j)
			len--;
		dp[q] = min(dp[q], cost(que[len-1], q));
	}
}

void solveEndingRegion(int l, int iStart, int iEnd, int qStart, int qEnd)	
{
	int len = 0;
	int i = iEnd;
	for(int j=qEnd;j>=qStart;j--)
	{
		int q = levels[l+1][j];
		while(i >= iStart && lastDom[i] >= j)
		{
			while(len >= 2 && overtake[len-2] >= findLocOvertake(l+1, level[i], que[len-1]))
				len--;
			que[len] = level[i];
			if(len >= 1)
				overtake[len-1] = findLocOvertake(l+1, level[i], que[len-1]);
			len++;
			i--;
		}
		while(len >= 2 && overtake[len-2] > j)
			len--;
		dp[q] = min(dp[q], cost(que[len-1], q));
	}
}

int main()
{
	cin >> N >> L;
	for(int i=0;i<N;i++)
		cin >> x[i] >> y[i];
	x[N] = y[N] = L;
	N++;
	for(int i=0;i<N;i++)
		dp[i] = INF, xid[i] = i;
	
	sort(xid,xid+N,cmpx);
	
	computeLIS();
	for(int i=0;i<levels[0].size();i++)
	{
		int cur = levels[0][i];
		dp[cur] = x[cur]*((long long)y[cur]);
	}
	for(int l=0;levels[l+1].size()>0;l++)
	{
		level.clear();
		for(int i=0;i<levels[l].size();i++)
		{
			int cur = levels[l][i];
			int fd = findFirst(l+1, cur);
			int ld = findLast(l+1, cur);
			if(fd != -1)	
			{
				firstDom[level.size()] = fd;
				lastDom[level.size()] = ld;
				level.push_back(levels[l][i]);
			}
		}
		for(int i=0;i<level.size();)
		{
			int iEnd = i;
			while(iEnd + 1 < level.size() && firstDom[iEnd + 1] <= lastDom[i])
				iEnd++;
			solveStartingRegion(l, i, iEnd, firstDom[i], lastDom[i]);
			if(lastDom[iEnd] >= lastDom[i] + 1)
				solveEndingRegion(l, i+1, iEnd, lastDom[i] + 1, lastDom[iEnd]);
			i = iEnd + 1;
		}
	}
	cout << dp[N-1] << '\n';
}