51nod 1249 近似有序区间
1249 近似有序区间 题目来源： HackerRank 基准时间限制：1 秒 空间限制：131072 KB 分值: 160 难度：6级算法题 收藏 关注 一个1到N的排列S，S的近似有序的区间满足如下性质： 1、是S的连续子序列。 2、第一个数是最小的。 3、最后一个数是最大的。 例如：S = {3, 1, 2, 5, 4}，S的所有近似有序区间为: {3}, {1}, {1, 2}, {1, 2, 5}, {2}, {2, 5}, {5}, {4} 给出S，求S的近似有序区间的数量。 Input 第一行：一个数N，表示S的长度。（1 <= N <= 50000) 第2 - N + 1行：每行1个数，对应1 - N的排列。 Output 输出S近似区间的数量。 解题思路 用线段树 从后开始扫描 3 1 2 5 4 第一个4 所以贡献值为1 第二个5 后一个比它小 5的贡献也是1 第三个2 2后面比它大 2的贡献等于5的贡献+1（本身） 然后再扫描5后面有没有比5大的数 且范围大于2 第四个1 1后面比它大 1的贡献等于2的贡献加1 #include <stdio.h> #include <bits/stdc++.h> #define mod 1000000007 #define read(); freopen("input.txt","r",stdin); typedef long long ll; using namespace std; int s[50005]; int vis[50005]; int sum[50005]; int maxtree[200050]; int n; void build(int i,int l,int r){ if(l==r){ maxtree[i]=s[l]; return ; } int mid=l+r>>1; build(i*2,l,mid); build(i*2+1,mid+1,r); maxtree[i]=max(maxtree[i*2],maxtree[i*2+1]); } int query(int i,int l,int r,int x,int y,int maxn){ if(l==r) { if(s[l]>=maxn) return l; return 0; } int mid=l+r>>1; int k=0; if(maxtree[i]>=maxn){ if(x<=mid){ k=query(i*2,l,mid,x,y,maxn); } if(k==0 && y>mid) k=query(i*2+1,mid+1,r,x,y,maxn); } return k; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>s[i]; build(1,1,n); for(int i=n;i>=1;i--){ if(s[i]>s[i+1]) sum[i]=1,vis[i]=i; else{ vis[i]=vis[i+1]; sum[i]=sum[i+1]+1; int maxn=s[vis[i]]; int l=vis[i]+1,r=l; while(s[r]>=s[i]){ r=vis[r]+1; }r-=1; while(l<=r){ maxn=query(1,1,n,l,r,maxn); if(maxn!=0)sum[i]++; else break; l=maxn+1; vis[i]=maxn; maxn=s[maxn]; } } } ll ans=0; for(int i=1;i<=n;i++) ans+=sum[i]; cout<<ans; return 0; }