Description：

给一个二分图，对于一个 $X$ 部的点 $x$ ，对应在 $Y$ 部的相邻点只会是一个连续区间。

找一个最大匹配，且两个匹配边不相交

$1\le n \le 300000$

Solution：

似乎是一个线段树优化连边，但仔细想想发现不可做。

记 $f[i]$ 表示 $i$ 个合法匹配对应 $Y$ 部点的编号最大的点的最小编号是多少，显然 $f[i]$ 严格单调递增，对于每次建边，发现对于 $f[i]\in [l,r)$ ，他们可以转移到 $f[i+1]$ ，但我们显然不能一个一个转移，发现转移一定是形如 $f[i+1]=f[i]+1$ ，于是可以区间整体打 $+1$ 标记，并删除区间最右点，在区间最左边插入一个 $l$ ，因为腾出来了一个位置，而 $f[i]\in [l,r)$ ，所以把最左边赋成 $l$ 一定不会更劣，也就是说实际一定是这样转移的，于是写个 $splay$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 300010

#define INF 0x3f3f3f3f

struct node

{

	int c[2],fa,f;

	int tag;

}t[MAXN];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

inline void pushdown(int rt)

{

	if(t[rt].tag == 0)return;

	if(t[rt].c[0] != 0){t[t[rt].c[0]].tag += t[rt].tag;t[t[rt].c[0]].f += t[rt].tag;}

	if(t[rt].c[1] != 0){t[t[rt].c[1]].tag += t[rt].tag;t[t[rt].c[1]].f += t[rt].tag;}

	t[rt].tag = 0;

	return;

}

inline int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

inline void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa;

	pushdown(z);pushdown(y);

	int fx = id(x),fy = id(y);

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	connect(x,z,fy);

	return;

}

inline void splay(int x,int &k)

{

	int to = t[k].fa;

	while(t[x].fa != to)

	{

		int y = t[x].fa;

		if(t[y].fa == to){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	k = x;

	return;

}

int lefbound(int k)

{

	int cur = root,p = INF;

	while(true)

	{

		if(cur == 0)break;

		pushdown(cur);

		if(k == t[cur].f){p = cur;break;}

		if(k > t[cur].f)cur = t[cur].c[1];

		else{p = cur;cur = t[cur].c[0];}

	}

	return p;

}

int rigbound(int k)

{

	int cur = root,p = INF;

	while(true)

	{

		if(cur == 0)break;

		pushdown(cur);

		if(k == t[cur].f){p = cur;break;}

		if(k < t[cur].f)cur = t[cur].c[0];

		else{p = cur;cur = t[cur].c[1];}

	}

	return p;

}

inline int pre(int k)

{

	splay(k,root);

	if(t[k].c[0] == 0)return INF;

	pushdown(k);k = t[k].c[0];

	while(t[k].c[1] != 0){pushdown(k);k = t[k].c[1];}

	pushdown(k);

	splay(k,root);

	return k;

}

inline int nxt(int k)

{

	splay(k,root);

	if(t[k].c[1] == 0)return INF;

	pushdown(k);k = t[k].c[1];

	while(t[k].c[0] != 0){pushdown(k);k = t[k].c[0];}

	pushdown(k);

	splay(k,root);

	return k;

}

inline void remove(int k)

{

	int p = lefbound(k);

	if(p == INF)return;

	splay(p,root);pushdown(root);

	if(t[p].c[0] == 0){root = t[p].c[1];t[t[p].c[1]].fa = 0;return;}

	if(t[p].c[1] == 0){root = t[p].c[0];t[t[p].c[0]].fa = 0;return;}

	int nrt = nxt(p);

	splay(nrt,t[p].c[1]);pushdown(nrt);

	pushdown(t[p].c[0]);

	connect(t[p].c[0],t[p].c[1],0);

	root = t[p].c[1];

	t[t[p].c[1]].fa = 0;

	return;

}

inline int get(int l,int r)

{

	int l_ = lefbound(l);

	if(l_ == INF)return INF;

	int r_ = rigbound(r);

	if(r_ == INF)return INF;

	if(t[l_].f > t[r_].f)return INF;

	l_ = pre(l_);r_ = nxt(r_);

	if(l_ == INF && r_ == INF)return root;

	if(l_ == INF){splay(r_,root);return t[root].c[0];}

	if(r_ == INF){splay(l_,root);return t[root].c[1];}

	splay(l_,root);splay(r_,t[root].c[1]); 

	return t[t[root].c[1]].c[0];

}

inline int create(int k,int fa)

{

	int p = newnode();

	t[p].fa = fa;t[p].f = k;

	return p;

}

inline void insert(int k)

{

	int cur = root;

	while(true)

	{

		pushdown(cur); 

		if(k < t[cur].f)

		{

			if(t[cur].c[0] == 0)

			{

				t[cur].c[0] = create(k,cur);

				splay(t[cur].c[0],root);

				return;

			}

			else cur = t[cur].c[0];

		}

		else

		{

			if(t[cur].c[1] == 0)

			{

				t[cur].c[1] = create(k,cur);

				splay(t[cur].c[1],root);

				return;

			}

			else cur = t[cur].c[1];

		}

	}

	return;

}

void pt(int rt)

{

	if(rt == 0 || rt == INF)return;

	pushdown(rt);

	pt(t[rt].c[0]);

	cout << t[rt].f << " ";

	pt(t[rt].c[1]);

	return;

}

inline void modify(int l,int r)

{

	remove(r);

	int k = get(l,r - 1);

	if(k != INF){t[k].f += 1;t[k].tag += 1;}

	insert(l);

	return;

}

inline void init()

{

	root = newnode();

	t[root].f = 0;

	return;

}

int cnt(int rt)

{

	if(rt == 0)return 0;

	return cnt(t[rt].c[0]) + 1 + cnt(t[rt].c[1]);

}

int main()

{

	scanf("%d",&n);

	int l,r;

	init();

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

	{

		scanf("%d%d",&l,&r);

		modify(l,r);

	}

	cout << cnt(root) - 1 << endl;

	return 0;

}