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

题目描述

Description

Input

Output

Sample Input
见下载

Sample Output
见下载

Data Constraint

题解

lj题卡线段树

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

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

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

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

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

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;
}