[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]B Balloon Warehouse

    题目大意：初始有一个无穷的从第0项开始的序列，每一项为0，给出n个操作a,b表示在每个数字a后面增加一个数字b，输出最终第l至r-1个数字。(n<=200000,l,r<=1000000,r-l<=100000)

    遍历即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=400010,maxr=1e6+10,inf=~0U>>1;

inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline int read()
{
	char ch=nc();int sum=0;
	while(!(ch>='0'&&ch<='9')) ch=nc();
	while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
	return sum;
}

int head[maxn],nxt[maxn],E[maxn],P[maxn],Ecnt;
int ans[maxr];
int n,l,r,cnt;

void Add_Edge(int x,int y,int ID)
{
	nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;P[Ecnt]=ID;
}

void DFS(int x,int pos)
{
	ans[cnt++]=x;
	for (int i=head[x];i && cnt<r;i=nxt[i]) if (P[i]>pos) DFS(E[i],P[i]);else break;
}

int main()
{
	n=read(),l=read(),r=read();
	for (int i=1,x,y;i<=n;i++) x=read(),y=read(),Add_Edge(x,y,i);
	while (cnt<r) DFS(0,0);
	for (int i=l;i<r;i++) printf("%d%c",ans[i],(i==r-1)?'\n':' ');
}