5246. 【NOIP2017模拟8.8A组】Trip(trip)

(File IO): input:trip.in output:trip.out

Time Limits: 1500 ms Memory Limits: 262144 KB Detailed Limits

Description

多年之后，worldwideD厌倦竞争，隐居山林。

他的家乡开始发展起了旅游业，在一条很长的主干道上，有N个旅游景点，按顺序编号为1到N。根据游客们网上的评分，第i个景点有一个评估值a[i]，为了区分开不同的景点，评估值是两两不同的。

今天有M组游客前来旅游，第i组游客选择遍历景点Li到景点Ri这一段路。他们搜到Li到Ri的所有评估值，如果对于景点j（Li≤j≤Ri），不存在景点x（Li≤x＜j）满足a[x]>a[j]或不存在景点y（j＜y≤Ri）满足a[y]>a[j]，那么他们会进入景点j。

现在worldwideD想知道，每组游客会去多少个景点。

Input

第一行两个整数N,M，意义见题面。

接下来一行N个整数，第i个是a[i]，意义见题面。

接下来M行，第i行两个整数Li，Ri，意义见题目。

Output

M行，第i行表示第i组游客去的景点个数。

Sample Input

6 4

3 1 7 4 5 2

1 5

2 5

2 6

4 6

Sample Output

3

3

4

3

Data Constraint

30%：N,M≤5,000

60%：N,M≤100,000

100%：N,M≤1,000,000 0≤|a[i]|≤1,000,000,000 1≤Li≤Ri≤N

Hint

第一组游客选择路段的景点评估值序列为[3,1,7,4,5]，其中3,7,5满足条件

第二组游客选择路段的景点评估值序列为[1,7,4,5]，其中1,7,5满足条件

第三组游客选择路段的景点评估值序列为[1,7,4,5,2]，其中3,7,5,2满足条件

第四组游客选择路段的景点评估值序列为[4,5,2]，其中4,5,2满足条件

本题数据规模较大，请注意您的常数造成的影响。

在这里给出一种输入输出优化的模板，在主程序中直接调用read()即可读入一个整数，调用write(x)可以把一个int变量x输出并换行。

int read()

{

       int x=0,sig=1;

       char c;

       for (c=getchar();c<'0' || c>'9';c=getchar()) if (c=='-') sig=-1;

       for (;c>='0' && c<='9';c=getchar()) x=x*10+c-48;

       return x*sig;

}

void write(int x)

{

       if (!x) putchar('0');else

       {

              char s[10];

              int i,j=0;

              for (;x>0;x/=10) s[j++]=x%10;

              for (i=j-1;i>=0;i--) putchar(s[i]+48);

       }

       putchar('\n');

}

题解

对于每个区间，找出最大值，然后从两端到最大值分别建两个单调栈，两个栈个数之和-1就是答案

但很显然这样只有30分

怎么优化呢？

给原序列建一颗笛卡尔树，这个用单调栈O(N)搞定

笛卡尔树满足堆和二叉搜索树（二叉排序树）的性质

即它的中序遍历是原序列，同时跟比左右儿子大（小）

于是，我们发现

1. 答案只可能出现在L和R在笛卡尔树上的路径上

2. 在L到lca(L,R)的路径上，只有自己是父亲节点的左儿子的节点，才对答案贡献1，R到lca(L,R)就反过来

那么就用Tarjan求lca，并预处理出每个点到根节点有多少个点是父亲的左/右节点

代码

#pragma GCC optimize (2)

#include<cstdio>

#include<vector>

#define N 1000010

using namespace std;

struct node{

    long key,lc,rc,fa;

}a[N];

long sta[N],l[N],r[N],top,ll,rr;

void push(long q)

{

    sta[++top]=q;

}

void pop()

{

    top--;

}

long front()

{

    return sta[top];

}

long father[N];

long cha(long now)

{

    return (father[now]==now)?now:father[now]=cha(father[now]);

}

void bin(long a,long b)

{

    father[cha(b)]=cha(a);

}

long ans[N],x[N],y[N];

bool b[N];

vector<long>ask[N];

void tarjan1(long now)

{   long i;

    bool t=false;

    for(i=a[now].lc;i&&!b[i];i=a[i].lc){

        push(i);

        l[i]=l[a[i].fa]+1;

        r[i]=r[a[i].fa];

        t=true;

    }

    if(t)return;

    b[now]=true;

    if(a[now].rc){

        l[a[now].rc]=l[now];

        r[a[now].rc]=r[now]+1;

        push(a[now].rc);

        return;

    }

}

void tarjan2(long now)

{   long q,w;

    vector<long>::iterator i;

    for(i=ask[now].begin();i!=ask[now].end();++i){

        q=*i;

        if(now==x[q])w=y[q];

        else w=x[q];

        if(!ans[q]&&b[w])

            ans[q]=cha(w);

    }

    bin(a[now].fa,now);

}

void tarjan(long now)

{

    push(now);

    l[now]=r[now]=0;

    while(top){

        if(!b[front()])

            tarjan1(front());

        else{

            tarjan2(front());

            pop();

        }

    }

}

int read()

{

       int x=0,sig=1;

       char c;

       for (c=getchar();c<'0' || c>'9';c=getchar()) if (c=='-') sig=-1;

       for (;c>='0' && c<='9';c=getchar()) x=x*10+c-48;

       return x*sig;

}

void write(int x)

{

       if (!x) putchar('0');else

       {

              char s[10];

              int i,j=0;

              for (;x>0;x/=10) s[j++]=x%10;

              for (i=j-1;i>=0;i--) putchar(s[i]+48);

       }

       putchar('\n');

}

int main()

{   long n,m,i,maxx=-2147483647,pos;

    freopen("trip.in","r",stdin);

    freopen("trip.out","w",stdout);

    n=read();

    m=read();

    for(i=1;i<=n;i++){

        a[i].key=read();

        father[i]=i;

        if(a[i].key>maxx){

            maxx=a[i].key;

            pos=i;

        }

        while(top&&a[sta[top]].key<a[i].key){

            a[i].lc=front();

            pop();

        }

        a[a[i].lc].fa=i;

        if(top){

            a[i].fa=front();

            a[front()].rc=i;

        }

        push(i);

    }

    for(i=1;i<=m;i++){

        x[i]=read();

        y[i]=read();

        ask[x[i]].push_back(i);

        ask[y[i]].push_back(i);

    }

    top=0;

    tarjan(pos);

    for(i=1;i<=m;i++)

        write(l[x[i]]-l[ans[i]]+r[y[i]]-r[ans[i]]+1);

    return 0;

}

JZOJ 5246. 【NOIP2017模拟8.8A组】Trip(trip)的相关教程结束。