多少年不写题解了 题目描述: 著名出题人小 Q 出了一道题，这个题给定一个正整数序列 a1, a2, ..., an，并保证输入数据中，对于 a 的任意一个非空连续子区间 [l, r]，该区间内出现过的数值在整数上值域连续。 现在小 Q 生成了一个长度为 n 的序列 b1, b2, ..., bn，他发现数据生成器似乎并不能保证数据合法， 因此希望从中截取一段连续子区间作为测试数据。 小 Q 选定了其中 m 个连续子区间 [l, r]，请写一个程序，对于每个区间判断该区间是否满足条件。 n,m<=1e5
sb题....然而我看偏了搞出来一个log,写着写着发现自己傻了.... 合法的区间中所有长度为2的区间必然满足条件,所以相邻两个数字之差的绝对值必然满足条件.显然满足这个条件那么所有子区间都满足条件. 前缀和一波判断一下就完了.O(n+m).
#include<cstdio> const int maxn=500005; int b[maxn]; int d[maxn]; int main(){ int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%d",b+i); } for(int i=1;i<n;++i){ d[i]=b[i]-b[i+1]; } for(int i=1;i<n;++i){ if(-1<=d[i]&&d[i]<=1){ d[i]=0; }else{ d[i]=1; } } for(int i=1;i<n;++i)d[i]+=d[i-1]; for(int i=1,l,r;i<=m;++i){ scanf("%d%d",&l,&r); if(l==r)printf("YES\n"); else if(d[r-1]-d[l-1]==0)printf("YES\n"); else printf("NO\n"); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/8425974.html
相关资源：数据结构—成绩单生成器