Board Game CodeForces - 605D (BFS)

大意: 给定$n$张卡$(a_i,b_i,c_i,d_i)$, 初始坐标$(0,0)$.

假设当前在$(x,y)$, 若$x\ge a_i,y\ge b_i$, 则可以使用第$i$张卡, 使用后达到坐标$c_i,d_i$.

求最少使用多少张卡后才能使用最后一张卡.

直接$BFS$的话是$O(n^2)$的, 用数据结构优化即可.

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <map>

#include <queue>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define lc (o<<1)

#define rc (lc|1)

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

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

using namespace std;

typedef pair<int,int> pii;

typedef tuple<int,int,int> t3;

const int N = 1e6+10;

const int INF = 0x3f3f3f3f;

int n, cnt, b[N], pre[N];

struct {int a,b,c,d,id;} a[N];

queue<t3> q;

priority_queue<pii,vector<pii>,greater<pii> > s[N];

pii tr[N<<2];

int ID(int x) {

	return lower_bound(b+1,b+1+*b,x)-b;

}

void dfs(int x) {

	++cnt;

	if (pre[x]!=-1) dfs(pre[x]);

	else printf("%d\n",cnt);

	printf("%d ",x);

}

void build(int o, int l, int r) {

	if (l==r) {

		tr[o].x = s[l].empty()?INF:s[l].top().x;

		tr[o].y = l;

		return;

	}

	build(ls),build(rs);

	tr[o]=min(tr[lc],tr[rc]);

}

void update(int o, int l, int r, int x) {

	if (l==r) {

		tr[o].x = s[l].empty()?INF:s[l].top().x;

		return;

	}

	mid>=x?update(ls,x):update(rs,x);

	tr[o]=min(tr[lc], tr[rc]);

}

pii find(int o, int l, int r, int ql, int qr) {

	if (ql<=l&&r<=qr) return tr[o];

	if (mid>=qr) return find(ls,ql,qr);

	if (mid<ql) return find(rs,ql,qr);

	return min(find(ls,ql,qr),find(rs,ql,qr));

}

int main() {

	scanf("%d", &n);

	REP(i,1,n) {

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

		b[++*b]=a[i].a;

		b[++*b]=a[i].b;

		b[++*b]=a[i].c;

		b[++*b]=a[i].d;

		a[i].id = i;

	}

	b[++*b] = 0;

	sort(b+1,b+1+*b),*b=unique(b+1,b+1+*b)-b-1;

	REP(i,1,n) {

		a[i].a=ID(a[i].a);

		a[i].b=ID(a[i].b);

		a[i].c=ID(a[i].c);

		a[i].d=ID(a[i].d);

		s[a[i].b].push(pii(a[i].a,a[i].id));

	}

	build(1,1,*b);

	q.push(t3(ID(0),ID(0),-1));

	while (q.size()) {

		t3 u = q.front(); q.pop();

		int x, y, id;

		tie(x,y,id) = u;

		while (1) {

			pii ret = find(1,1,*b,1,y);

			if (ret.x>x) break;

			while (s[ret.y].size()&&s[ret.y].top().x<=x) {

				int id2 = s[ret.y].top().y; s[ret.y].pop();

				pre[id2] = id;

				q.push(t3(a[id2].c,a[id2].d,id2));

			}

			update(1,1,*b,ret.y);

		}

	}

	if (!pre[n]) return puts("-1"),0;

	dfs(n),hr;

}