哲学家的沉思

非正常人类研究中心的哲学家牛拉底鲁曾有一句名言：“人一次也不能踏进同一条河流”，除此之外他还喜欢将连续的一段划分为若干片段。你作为中心的一名员工，为了照顾牛拉底鲁的生活起居，不得不陪他玩这样的一个游戏。

这个游戏的过程如下：牛拉底鲁会给你 $n$ 个数字，第 $i$ 个数字为 $a[i]$ 。接下来他会进行 $q$ 次询问，每次询问将给出两个数字 $l$ 与 $r$ ，要你把 $[l,r]$ 区间划分为若干个片段 $[l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}]$ 。要求对于任意一个片段 $[l_{i},r_{i}]$ ， $a[l_{i}]$ 为这个片段中的最大值。

牛拉底鲁想要最小化片段的数量，因此对于每次询问，请你回答出 $k$ 的最小值。

#include<bits/stdc++.h> using namespace std; int a[100005],rr[100005],st[100005][20]; int main() { int i,j,n,q,l,r,ans; scanf("%d%d",&n,&q); for(i=1;i<=n;i++)scanf("%d",&a[i]); st[n][0]=rr[n]=n+1; for(i=n-1;i>=1;i--) { for(j=i+1;j!=n+1&&a[j]<=a[i];j=rr[j]); rr[i]=st[i][0]=j; } for(i=1;i<=17;i++) { for(j=1;j<=n;j++) { if(st[j][i-1]>n)st[j][i]=1e9; else st[j][i]=st[st[j][i-1]][i-1]; } } while(q--) { scanf("%d%d",&l,&r),ans=0; for(i=17;i>=0;i--)if(st[l][i]<=r)l=st[l][i],ans|=(1<<i); printf("%d\n",ans+1); } }

详情