欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-25 17:27:55
...

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满足条件
本题数据规模较大,请注意您的常数造成的影响。


解法

按照原序列建一棵笛卡尔树(大根),然后通过笛卡尔树一些性质,我们发现,对于区间[l,r]。
1.答案是树上这两点路径上的某些点。
2.其中l到lca上的点,如果这个点是父亲的左儿子,就对答案有1的贡献。r到lca则相反。
建树可以用单调栈O(n)建,求lca用tarjan,dfs时打人工栈。
时间:O(nαn),可以过。

然而,很多人没有打人工栈,甚至有的人lca用倍增的,却过了,打的估计很优美。
我懒得打人工栈,脸又不好,爆栈了,心态炸了,不想改了。


代码

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

const int maxn=1e6+5;
struct cy{
    int l,r,ls,rs;
}tree[maxn];
struct hg{
    int x,y,lca;
}que[maxn];
int a[maxn],stack[maxn],id[maxn*2];
int dad[maxn],next[maxn*2],fre[maxn],go[maxn*2];
int n,m,ans,top,now,num,root;
bool bz[maxn];

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');
}
void add(int x,int y,int z)
{
    go[++num]=y;
    next[num]=fre[x];
    fre[x]=num;
    id[num]=z;
}
int getdad(int x)
{
    if (dad[x]==x) return x;
    else {
        int k=getdad(dad[x]);
        dad[x]=k; 
        return k;
    }
}
void dfs(int x,int fa)
{
    bz[x]=true;
    if (tree[x].l){
        tree[tree[x].l].ls=tree[x].ls+1;
        tree[tree[x].l].rs=tree[x].rs;
        dfs(tree[x].l,x);
    }
    if (tree[x].r){
        tree[tree[x].r].ls=tree[x].ls;
        tree[tree[x].r].rs=tree[x].rs+1;
        dfs(tree[x].r,x);
    }
    for(int i=fre[x];i;i=next[i]){
        int u=go[i];
        if (bz[u]) que[id[i]].lca=getdad(u);
    }
    dad[x]=fa;
}
int main()
{
    freopen("trip.in","r",stdin);
    freopen("trip.out","w",stdout);
    n=read(); m=read();
    a[0]=1e9+1; 
    fo(i,1,n) {
        a[i]=read(); dad[i]=i;
        int now=0;
        while (top>0&&a[stack[top]]<a[i]) now=stack[top--];
        if (now) tree[i].l=now;
        tree[stack[top]].r=i;
        stack[++top]=i;
    }
    root=stack[1];

    fo(i,1,m){
        scanf("%d%d",&que[i].x,&que[i].y);
        add(que[i].x,que[i].y,i);
        add(que[i].y,que[i].x,i);
    }

    dfs(root,root);
    fo(i,1,m){
        ans=tree[que[i].x].ls-tree[que[i].lca].ls;
        ans+=tree[que[i].y].rs-tree[que[i].lca].rs+1;
        printf("%d\n",ans);
    }
}

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