Description：

$n$ 张牌，每张有四个属性 $a,b,c,d$ ，手上有两个数 $x,y$ 初始为 $0$ ，然后每次可以拿牌当 $a_i\leqslant x,b_i\leqslant y$ ，之后 $x=c_i,y=d_i$ ，问最少拿几次可以拿到第 $n$ 张牌。

$1\leqslant n\leqslant 10^5$

Solution：

$a_i\leqslant c_j,b_i\leqslant d_j$ ，那么连一条 $i'\to j$ 边权为 $0$ 的边，连一条 $j\to j'$ 边权为 $1$ 的边，那么答案就是从 $(0,0)$ 到 $n'$ 的最短路，但是这样建边是 $O(n^2)$ 的，发现连边的是一个二维前缀，于是主席树优化建边即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int a[MAXN],b[MAXN],c[MAXN],d[MAXN];

int v[MAXN * 4];

struct edge

{

	int to,nxt,v;

}e[MAXN * 60];

int edgenum = 0;

int lin[MAXN * 30] = {0};

void add(int a,int b,int c)

{

	if(a == 0 || b == 0)return;

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	return;

}

struct node

{

	int lc,rc;

}t[MAXN * 30];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

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

void insert(int &rt,int p,int id,int l,int r)

{

	int k = newnode();t[k] = t[rt];

	add(k,rt,0);rt = k;

	if(l == r){add(rt,id,0);return;}

	if(p <= mid)insert(t[rt].lc,p,id,l,mid),add(rt,t[rt].lc,0);

	else insert(t[rt].rc,p,id,mid + 1,r),add(rt,t[rt].rc,0);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(rt == 0)return;

	if(L <= l && r <= R){add(k,rt,0);return;}

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

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

	return;

}

struct point

{

	int x,y;

	bool operator == (const point &b)const{return x == b.x && y == b.y;}

	bool operator < (const point &b)const{return (x == b.x ? y < b.y : x < b.x);}

}p[MAXN << 1];

int dis[MAXN * 30];

bool vis[MAXN * 30];

int tot = 0;

int fa[MAXN * 30];

int stack[MAXN],top = 0;

int main()

{

	scanf("%d",&n);

	bool found = false;

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

	{

		scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);

		if(a[i] == 0 && b[i] == 0)found = true;

	}

	if(!found){puts("-1");return 0;}

	for(int i = 1;i <= n;++i)v[++tot] = a[i];

	for(int i = 1;i <= n;++i)v[++tot] = b[i];

	for(int i = 1;i <= n;++i)v[++tot] = c[i];

	for(int i = 1;i <= n;++i)v[++tot] = d[i];

	sort(v + 1,v + 1 + tot);

	tot = unique(v + 1,v + 1 + tot) - v - 1;

	for(int i = 1;i <= n;++i)a[i] = lower_bound(v + 1,v + 1 + tot,a[i]) - v;

	for(int i = 1;i <= n;++i)b[i] = lower_bound(v + 1,v + 1 + tot,b[i]) - v;

	for(int i = 1;i <= n;++i)c[i] = lower_bound(v + 1,v + 1 + tot,c[i]) - v;

	for(int i = 1;i <= n;++i)d[i] = lower_bound(v + 1,v + 1 + tot,d[i]) - v;

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

	{

		p[i].x = a[i];p[i].y = b[i];

	}

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

	m = unique(p + 1,p + 1 + n) - p - 1;

	ptr = m + n;

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

	{

		root[i] = root[i - 1];

		for(;p[j].x == i;++j)insert(root[i],p[j].y,j,1,tot);

	}

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

	{

		add(root[c[i]],1,d[i],m + i,1,tot);

	}

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

	{

		int p1 = lower_bound(p + 1,p + 1 + m,(point){a[i],b[i]}) - p;

		add(p1,i + m,1);

	}

	memset(dis,0x3f,sizeof(dis));

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,1));dis[1] = 0;

	memset(vis,false,sizeof(vis));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;

		vis[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(dis[e[i].to] > dis[k] + e[i].v)

			{

				fa[e[i].to] = k;

				dis[e[i].to] = dis[k] + e[i].v;

				q.push(make_pair(-dis[e[i].to],e[i].to));

			}

		}

	}

	if(dis[n + m] == 0x3f3f3f3f)

	{

		puts("-1");

		return 0;

	}

	cout << dis[n + m] << endl;

	int des = n + m;

	while(des)

	{

		if(m + 1 <= des && des <= n + m)stack[++top] = des - m;

		des = fa[des];

	}

	while(top)printf("%d ",stack[top--]);

	cout << endl;

	return 0;

}