bzoj千题计划165:bzoj5127: 数据校验

时间:2023-03-10 03:17:02
bzoj千题计划165:bzoj5127: 数据校验

http://www.lydsy.com/JudgeOnline/upload/201712/prob12.pdf

区间的任意一个子区间都满足值域连续

等价于

区间任意一个长为2的子区间都满足值域连续

区间任意相邻的两个数 大的 减 小的 <=1

线段树维护即可

#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 int a[N]; bool ok[N<<]; bool ans; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void build(int k,int l,int r)
{
if(l==r)
{
ok[k]=(max(a[l],a[l+])-min(a[l],a[l+])<=);
return;
}
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
ok[k]=ok[k<<]&ok[k<<|];
} void query(int k,int l,int r,int opl,int opr)
{
if(l>=opl && r<=opr)
{
ans&=ok[k];
return;
}
int mid=l+r>>;
if(opl<=mid) query(k<<,l,mid,opl,opr);
if(opr>mid) query(k<<|,mid+,r,opl,opr);
} int main()
{
int n,m;
read(n); read(m);
for(int i=;i<=n;++i) read(a[i]);
if(n==)
{
while(m--) puts("YES");
return ;
}
build(,,n-);
int l,r;
while(m--)
{
read(l); read(r);
if(l==r)
{
puts("YES");
continue;
}
ans=true;
query(,,n-,l,r-);
puts(ans ? "YES" : "NO");
}
}