BZOJ 5127 [Lydsy12月赛]数据校验

题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=5127

题意:略。

思路dp[i]为以i结尾最早的位置使这段区域满足值域上连续,询问的时候只要判断dp[l]是否等于dp[r]即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int i,n,m,l,r,b[N],dp[N];
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",b+i);
    for (dp[1]=1,i=2;i<=n;i++){
        int tmp=abs(b[i]-b[i-1]);
        if (tmp<=1 && tmp>=0) dp[i]=dp[i-1];
        else dp[i]=i;
    }
    for (i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        puts(dp[l]==dp[r]?"YES":"NO");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注