Description：

一个抓娃娃机，每个娃娃有一个坐标，要求从 $(0,10^6)$ 按 $1\sim n$ 的顺序依次经过所有娃娃最后回到 $(10^6,10^6)$ ，不能从娃娃下面经过，在最开始可以选择把一些娃娃 $+1$ ，求调整后经过的最短距离。

$1\leqslant n\leqslant 10^6$

Solution：

列出答案的式子： $$ \begin{align} ans&=10^6-y_1+\sum_{i=1}^{n-1}\Big(2\times \mathrm{maxy}(\min(x_i,x_{i+1}),\max(x_i,x_{i+1}))-y_i-y_{i+1}\Big)+10^6-y_n\\ &=2\times \Big(10^6+\sum_{i=1}^{n-1}\mathrm{maxy}(\min(x_i,x_{i+1}),\max(x_i,x_{i+1}))-\sum_{i=1}^ny_i\Big) \end{align} $$ 也就是我们实际上是要最小化： $$ \sum_{i=1}^{n-1}\mathrm{maxy}(\min(x_i,x_{i+1}),\max(x_i,x_{i+1}))-\sum_{i=1}^ny_i $$ 先考虑一个部分分， $y_i$ 两两不同，那么因为最多只能加一，所以不同的 $y_i$ 不会相互影响，我们只要统计出有多少个区间以这个点为最高值，然后计算一下加一优还是不加一优即可。

上面那个做法启发我们分别处理每个 $\mathrm{maxy}(\min(x_i,x_{i+1}),\max(x_i,x_{i+1}))$ ，那么问题变成：给你一个序列和很多区间，可以给一个元素 $+1$ ，最大化 $(+1$ 的元素个数 $)-($ 有 $+1$ 的区间个数 $)$ 。

这个可以 $DP$ ：先假设所有区间都有加一，设 $dp[i]$ 表示 $i$ 一定 $+1$ 的最小值，转移为： $$ dp[i]=\min_{j<i}(dp[j]+cnt(j+1,i-1)+1) $$ $cnt$ 表示完全落在这个区间的区间个数。

这个可以线段树优化 $DP$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")

using namespace std;

int n;

namespace io {

	const int SIZE = (1 << 21) + 1;

	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;

	// getchar

	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)

	// print the remaining part

	inline void flush () {

		fwrite (obuf, 1, oS - obuf, stdout);

		oS = obuf;

	}

	// putchar

	inline void putc (char x) {

		*oS ++ = x;

		if (oS == oT) flush ();

	}

	// input a signed integer

	template <class I>

	inline void gi (I &x) {

		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;

		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;

	}

	// print a signed integer

	template <class I>

	inline void print (I &x) {

		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;

		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;

		while (qr) putc (qu[qr --]);

	}

	//no need to call flush at the end manually!

	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;

}

using io :: gi;

using io :: putc;

using io :: print;

#define MAXN 1000010

#define N 1000000

struct point

{

	int x,y;

}p[MAXN];

bool cmp_y(point a,point b){return a.y < b.y;}

#define INF 0x3f3f3f3f

typedef long long ll;

#define reg register

#define I inline

struct node

{

	int lc,rc;

	int tag,maxv;

	node(){tag = 0;maxv = 0;}

}t[MAXN << 1];

int ptr = 0;

I int newnode()

{

	reg int k = ++ptr;

	t[k].lc = t[k].rc = t[k].tag = t[k].maxv = 0;

	return k;

}

int root;

#define mid ((l + r) >> 1)

I void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

I void add(int rt,int L,int R,int v,int l,int r)

{

	if(L <= l && r <= R){t[rt].tag += v;t[rt].maxv += v;return;}

	if(L <= mid)add(t[rt].lc,L,R,v,l,mid);

	if(R > mid)add(t[rt].rc,L,R,v,mid + 1,r);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv) + t[rt].tag;

	return;

}

I int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].maxv;

	reg int res = 0;

	if(L <= mid)res = max(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = max(res,query(t[rt].rc,L,R,mid + 1,r));

	return res + t[rt].tag;

}

struct seg

{

	int l,r,maxv;

}s[MAXN];

seg ss[MAXN];

int tot = 0;

int pos[MAXN];

bool cmp_r(seg a,seg b){return a.r < b.r;}

bool cmp_maxv(seg a,seg b){return a.maxv < b.maxv;}

I ll work(int v)

{

	sort(pos + 1,pos + 1 + pos[0]);

	ptr = root = 0;

	sort(ss + 1,ss + 1 + tot,cmp_r);

	for(reg int i = 1,cur = 1;i <= tot;++i)

	{

		ss[i].l = lower_bound(pos + 1,pos + 1 + pos[0],ss[i].l) - pos;

		while(cur < pos[0] && pos[cur + 1] <= ss[i].r)++cur;

		ss[i].r = cur;

	}

	build(root,0,pos[0]);

	for(reg int i = 1,cur = 1;i <= pos[0];++i)

	{

		add(root,i,i,query(root,0,i - 1,0,pos[0]) + 1,0,pos[0]);

		while(cur <= tot && ss[cur].r == i)add(root,0,ss[cur].l - 1,1,0,pos[0]),++cur;

	}

	reg ll ans = -t[root].maxv + tot + 1ll * tot * v - 1ll * pos[0] * v;

	return ans;

}

int main()

{

	freopen("doll.in","r",stdin);

	freopen("doll.out","w",stdout);

	scanf("%d",&n);

	for(reg int i = 1;i <= n;++i)gi(p[i].x),gi(p[i].y);

	build(root,0,N);

	for(reg int i = 1;i <= n;++i)add(root,p[i].x,p[i].x,p[i].y,0,N);

	for(reg int i = 1;i < n;++i)

	{

		s[i].l = min(p[i].x,p[i + 1].x);

		s[i].r = max(p[i].x,p[i + 1].x);

		s[i].maxv = query(root,s[i].l,s[i].r,0,N);

	}

	sort(s + 1,s + 1 + n - 1,cmp_maxv);

	sort(p + 1,p + 1 + n,cmp_y);

	reg ll ans = 0;

	reg int i,j;

	for(i = 1,j = 1;i < n;++i)

	{

		ss[++tot] = s[i];

		if(i == N || s[i].maxv != s[i + 1].maxv)

		{

			pos[0] = 0;

			while(p[j].y < s[i].maxv)ans -= p[j].y + 1,++j;

			while(j <= n && p[j].y == s[i].maxv)pos[++pos[0]] = p[j].x,++j;

			ans += work(s[i].maxv);

			tot = 0;

		}

	}

	while(j <= n)ans -= p[j].y + 1,++j;

	ans = (ans + N) * 2;

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}