旅行(并查集-链)

这题最关键的是如何跳过无用结点

可以用链表，每一个结点指向它或它右侧的可用结点

但是查找悲剧

所以，我们可以用并查集，把所有结点指向[它或它右侧的可用结点]

这样就可以直接跳过，注意 根为最右侧可用结点，其它结点为它左侧所有删去的点

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (1000000+10)
#define Read(x) {x=0;\
while (isdigit(c=getchar())) x=x*10+c-48;}
typedef long long ll;
int n,s,l[MAXN],r[MAXN];
int father[MAXN];
int st[MAXN];
char c;
int getfather(int x)
{
   int size=1;st[1]=x;
   while (st[size]&&father[st[size]]^st[size]) 
   {
      st[size+1]=father[st[size]];
      size++;
   }
   For(i,size-1) father[st[i]]=st[size];
   return father[x];
}
bool b[MAXN]={0};
int q[MAXN],d[MAXN];
void bfs(int s)
{
   For(i,n) d[i]=-1;
   d[s]=0;q[1]=s;b[s]=1;father[s]=s+1;
   int head=1,tail=1;
   while (head<=tail)
   {
      int now=q[head];
   // cout<