多少年不写题解了

题目描述:

著名出题人小 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
    
     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