1094: 等差区间

Time Limit:5000/3000 MS (Java/Others) Memory Limit:163840/131072 KB (Java/Others)
Total Submissions:655 Accepted:54

[Submit][Status][Discuss]

Description

已知一个长度为 n

的数组 a[1],a[2],…,a[n]，我们进行 q 次询问，每次询问区间 a[l],a[l+1],…,a[r−1],a[r]

，数字从小到大排列后，是否会形成等差数列。等差数列的定义为，数列相邻两项（后一项减去前一项）的差值相等。

Input

本题有多组输入数据。

每组输入数据第一行输入两个正整数 n

和 q。第二行输入 n 个正整数 a[1],a[2],…,a[n]。最后输入 q 行，每行两个数字 l,r（1≤l≤r≤n），表示询问区间 a[l],…,a[r]

。

1≤n,q≤105,1≤a[i]≤106

Output

对于每组询问输出一行，如果形成等差数列，输出“Yes ”，否则输出“No”（不含引号）。

Sample Input

Sample Output

Yes

Yes

No

Yes

Yes

HINT

【分析】

区间 [L,R] 内的数排序后构成等差数列可分两种情况
1.公差为 0
2.公差不为 0 ⟺ 区间内无相同元素且相邻两项差构成的数列的GCD ×（R−L) = (区间最大值-区间最小值）
所以RMQ查询区间最大值最小值以及（各个数的上一个相同数的下标的最大值）以及区间GCD

好强大的RMQ啊，打算明天自己裸敲一遍。。。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

typedef pair<int, int>pii;

const int N = 1e5+;

const int M = ;

int mn[N][M],mx[N][M],pre[N][M],gcd[N][M];

int mm[N],n,q;

int mat[N*];

void init() {

    for(int j=; j<=mm[n]; ++j) {

        for(int i=; i+(<<j)-<=n; ++i) {

            mn[i][j]=min(mn[i][j-],mn[i+(<<(j-))][j-]);

            mx[i][j]=max(mx[i][j-],mx[i+(<<(j-))][j-]);

            pre[i][j]=max(pre[i][j-],pre[i+(<<(j-))][j-]);

            gcd[i][j]=__gcd(gcd[i][j-],gcd[i+(<<(j-))][j-]);

        }

    }

}

int getmx(int l,int r) {

    int k = mm[r-l+];

    return max(mx[l][k],mx[r-(<<k)+][k]);

}

int getmn(int l,int r) {

    int k = mm[r-l+];

    return min(mn[l][k],mn[r-(<<k)+][k]);

}

int getpre(int l,int r) {

    int k = mm[r-l+];

    return max(pre[l][k],pre[r-(<<k)+][k]);

}

int getgcd(int l,int r) {

    int k = mm[r-l+];

    return __gcd(gcd[l][k],gcd[r-(<<k)+][k]);

}

int read() {

    int x=,f=;

    char ch=getchar();

    while(ch<''||ch>'') {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='') {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

int main() {

    mm[]=-;

    for(int i=; i<N; ++i)mm[i]=(i&(i-))?mm[i-]:mm[i-]+;

    while(~scanf("%d%d",&n,&q)) {

        for(int i=; i<=; ++i)mat[i] = ;

        for(int i=; i<=n; ++i) {

            mn[i][]=read();

            mx[i][]=mn[i][];

            pre[i][]=mat[mn[i][]];

            mat[mn[i][]]=i;

            if(i>)gcd[i-][] = abs(mn[i][]-mn[i-][]);

        }

        init();

        while(q--) {

            int l=read(),r=read();

            if(l==r) {

                printf("Yes\n");

                continue;

            }

            int x=getmn(l,r),y=getmx(l,r);

            if(x==y) {

                printf("Yes\n");

                continue;

            }

            if(getpre(l,r)>=l) {

                printf("No\n");

                continue;

            }

            int d = getgcd(l,r-);

            if(x+1ll*(r-l)*d==y)printf("Yes\n");

            else printf("No\n");

        }

    }

    return ;

}

巴特西

dutacm.club 1094: 等差区间（RMQ区间最大、最小值，区间GCD）