题目描述

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]='\n';

}

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;

}

巴特西

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

题目描述

题解

code

最新文章

热门文章