6424. 【NOIP2019模拟2019.11.13】我的订书机之恋

题目描述

Description

Input

Output

Sample Input
见下载

Sample Output
见下载

Data Constraint

题解

lj题卡线段树

求出每个右端点往左第一个跳到的点，可以变成一棵树

如果r1r2（r1<r2）中间没有把两个点分开的弦，那么就是r1的深度

用一个单调栈可以求出往左跳到的点（每次把若干小区间合并），但是有可能一条弦跳到的位置会被向后的一条弦切断

所以再用一个单调栈求出每个右端点向左第一个跨过它的左端点，如果再维护过程中出现了交叉的情况就把前面的弹掉

最后判断跳到的点是否合法，连边求深度即可

fwrite真好用

code

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;

int a[2000001][2];
int ls[2000001];
int b[2000001];
int c[2000001];
int p[2000001][2];
int d[2000001];
int Fa[2000001];
int P[2000001][2];
bool Bz[2000001];
char st[32000001];
char St[8000001];
char Put[11];
char *Ch=st;
int Q,N,n,i,j,k,l,len,x,y,t,T,len2;
bool bz;

int get()
{
	int x=0;
	
	while (*Ch<'0' || *Ch>'9') *++Ch;
	while (*Ch>='0' && *Ch<='9') x=x*10+(*Ch-'0'),*++Ch;
	
	return x;
}

void put(int x)
{
	int len=0;
	
	if (!x)
	Put[++len]='0';
	while (x)
	{
		Put[++len]=x%10+'0';
		x/=10;
	}
	
	while (len)
	St[++len2]=Put[len--];
	St[++len2]='
';
}

void New(int x,int y)
{
	++len;
	a[len][0]=y;
	a[len][1]=ls[x];
	ls[x]=len;
}

void swap(int &x,int &y)
{
	int z=x;
	x=y;
	y=z;
}

int main()
{
//	freopen("6_1.in","r",stdin);
//	freopen("hotchkiss5.in","r",stdin);
	freopen("hotchkiss.in","r",stdin);
	freopen("hotchkiss.out","w",stdout);
	
	fread(st,1,32000001,stdin);
	
	n=get();Q=get();N=n+n;
	fo(i,1,N)
	b[i]=get();
	
	l=0;
	fo(i,1,N)
	if (i<b[i])
	{
		while (T && P[T][1]<b[i])
		--T;
		
		++T;
		P[T][0]=i;
		P[T][1]=b[i];
	}
	else
	{
		while (T && P[T][1]<=i)
		--T;
		
		bz=0;
		while (t && b[i]<p[t][1])
		--t,bz=1;
		
		if (bz)
		{
			++t;
			p[t][0]=min(p[t][0],b[i]);
			p[t][1]=i;
		}
		else
		{
			++t;
			p[t][0]=b[i];
			p[t][1]=i;
		}
		
		if (!T || P[T][0]<p[t][0])
		New(p[t][0]-1,i);
	}
	
//	---
	
	memset(Fa,255,sizeof(Fa));
	fo(j,0,N)
	{
		if (Fa[j]==-1)
		Fa[j]=j;
		
		for (i=ls[j]; i; i=a[i][1])
		{
			Fa[a[i][0]]=Fa[j];
			d[a[i][0]]=d[j]+1;
		}
	}
	
	len2=-1;
	for (;Q;--Q)
	{
		x=get();y=get();
		if (x>y)
		swap(x,y);
		
		if (x && y && b[x]<x && b[y]<y && Fa[x]==Fa[y])
		put(d[x]);
		else
		put(0);
	}
	
	fwrite(St,1,len2,stdout);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}