dutacm.club_1094_等差区间_(线段树)(RMQ算法)

时间：2025-04-22 18:07:31

1094: 等差区间

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

[Submit][Status][Discuss]

Description

已知一个长度为 nn 的数组 a[1],a[2],…,a[n]，我们进行 qq 次询问，每次询问区间 a[l],a[l+1],…,a[r−1],a[r]，数字从小到大排列后，是否会形成等差数列。等差数列的定义为，数列相邻两项（后一项减去前一项）的差值相等。

Input

本题有多组输入数据。

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

1≤n,q≤10^5,1≤a[i]≤10^6

Output

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

Sample Input

5 5

3 1 5 2 4

1 3

4 5

1 4

3 4

2 2

Sample Output

Yes

Yes

No

Yes

Yes

题意：给定一个n位数列，q条查询[l,r]，询问子序列[l--r]排序后是否为等差数列。

看题解说用的什么 RMQ求区间最大最小 但是没有学过，过些天再补。我用线段树来代替的求最大最小值。

思路：一个区间要是等差数列：1.所有数相等;2.所有数不等，且求公差，满足g*(r-l)==maxn-minn。

然后就是公差，我反正是没想到。求这个序列所有相邻两项差的最大公约数，结果即为公差，求公差也需要在线段树中进行，不能枚举。

同时，需要记录当前这个数上一次出现的位置。

线段树中维护区间：最大值，最小值，公差，序列中所有出现过的数上一次出现的位置的最大值(因为第2中情况需要所有数不同)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<stdlib.h>

using namespace std;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define N 100005

int num[N];

struct Node

{

    int l,r;

    int maxn,minn,g,lef;

} tree[N<<];

int Gcd(int a,int b)

{

    if(a==||b==)

        return ;

    if(a<b)

    {

        int t=a;

        a=b;

        b=t;

    }

    if(a%b==)

        return b;

    return Gcd(b,a%b);

}

int cha[N],loc[N*],last[N];

void build(int l,int r,int rt)

{

    tree[rt].maxn=tree[rt].minn=;

    tree[rt].l=l;

    tree[rt].r=r;

    if(l==r)

    {

        tree[rt].maxn=num[l];

        tree[rt].minn=num[l];

        tree[rt].g=-;

        tree[rt].lef=last[l];

        return;

    }

    int mid=(l+r)>>;

    build(lson);

    build(rson);

    tree[rt].maxn=max(tree[rt<<].maxn,tree[rt<<|].maxn);

    tree[rt].minn=min(tree[rt<<].minn,tree[rt<<|].minn);

    if(tree[rt<<].l==tree[rt<<].r&&tree[rt<<|].l==tree[rt<<|].r) //建树时求出所有子节点数大于1的结点的公差

        tree[rt].g=abs(num[tree[rt<<].r]-num[tree[rt<<|].l]);

    else if(tree[rt<<|].l==tree[rt<<|].r)

        tree[rt].g=Gcd(tree[rt<<].g,abs(num[tree[rt<<].r]-num[tree[rt<<|].l]));

    else

        tree[rt].g=Gcd(Gcd(tree[rt<<].g,abs(num[tree[rt<<].r]-num[tree[rt<<|].l])),tree[rt<<|].g);

    tree[rt].lef=max(tree[rt<<].lef,tree[rt<<|].lef);

}

struct Res

{

    int maxn,minn,g,lef;

    Res(){}

    Res(int a,int b,int g1,int le)

    {

        maxn=a;

        minn=b;

        g=g1;

        lef=le;

    }

};

/*Res deal(Res a,Res b)

{

    Res tmp(max(a.maxn,b.maxn),min(a.minn,b.minn));

    return tmp;

}*/

Res query(int L,int R,int l,int r,int rt)

{

    if(L==l&&r==R)

    {

        Res tmp(tree[rt].maxn,tree[rt].minn,tree[rt].g,tree[rt].lef);

        return tmp;

    }

    int mid=(l+r)>>;

    if(L>mid)

        return query(L,R,rson);

    else if(R<=mid)

        return query(L,R,lson);

    else

    {

        Res r1=query(L,mid,lson);

        Res r2=query(mid+,R,rson);

        Res r3;

        r3.maxn=max(r1.maxn,r2.maxn);

        r3.minn=min(r1.minn,r2.minn);

        if(r1.g==-&&r2.g==-)  //查询时需注意，若查到叶子结点，其公约数为-1，需特殊处理

            r3.g=abs(num[mid]-num[mid+]);

        else if(r1.g==-)

            r3.g=Gcd(abs(num[mid]-num[mid+]),r2.g);

        else if(r2.g==-)

            r3.g=Gcd(abs(num[mid]-num[mid+]),r1.g);

        else

            r3.g=Gcd(r1.g,Gcd(abs(num[tree[rt<<].r]-num[tree[rt<<|].l]),r2.g));

        r3.lef=max(r1.lef,r2.lef);

        return r3;

    }

}

int main()

{

    int n,q;

    while(scanf("%d%d",&n,&q)!=EOF)

    {

        //memset(tree,0,sizeof(tree));

        memset(loc,,sizeof(loc));

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

        {

            scanf("%d",&num[i]);

            if(loc[num[i]]==)

                last[i]=;

            else

                last[i]=loc[num[i]];

            loc[num[i]]=i;

            if(i>)

                cha[i-]=abs(num[i]-num[i-]);

        }

        build(,n,);

        while(q--)

        {

            int ll,rr;

            scanf("%d%d",&ll,&rr);

            Res tm=query(ll,rr,,n,);

            int maxn=tm.maxn;

            int minn=tm.minn;

            int g=tm.g;

            int lef=tm.lef;

            //cout<<maxn<<' '<<minn<<' '<<g<<' '<<lef<<endl;

            if(minn==maxn)

            {

                printf("Yes\n");

                continue;

            }

            if(lef<ll&&(g*(rr-ll)==maxn-minn))

                printf("Yes\n");

            else

                printf("No\n");

        }

    }

    return ;

}
 RMQ（Range Minimum/Maximum Query），即区间最值查询。一种动态规划。思路和线段树的一样。
#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<stdlib.h>

using namespace std;

#define N 100005

int dpMax[N][],dpMin[N][],dpG[N][],dpLeft[N][],n,loc[N*];

int Gcd(int a,int b)

{

    if(a==||b==)

        return ;

    if(a<b)

    {

        int tmp=a;

        a=b;

        b=tmp;

    }

    if(a%b==)

        return b;

    return Gcd(b,a%b);

}

void RMQ()

{

    for(int j=; j<=; j++)

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

            if((<<j)+i-<=n)

            {

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

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

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

                if(j==)

                    dpG[i][j]=abs(dpMin[i][]-dpMin[i+][]);

                else

                    dpG[i][j]=Gcd(dpG[i][j-],Gcd(abs(dpMin[i+(<<j-)][]-dpMin[i+(<<j-)-][]),dpG[i+(<<j-)][j-]));

            }

}

int main()

{

    //cout<<log2(0)<<endl;

    int q;

    while(scanf("%d%d",&n,&q)!=EOF)

    {

        memset(loc,,sizeof(loc));

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

        {

            scanf("%d",&dpMin[i][]);

            dpMax[i][]=dpMin[i][];

            dpG[i][]=-;

            if(loc[dpMin[i][]]==)

                dpLeft[i][]=;

            else

                dpLeft[i][]=loc[dpMin[i][]];

            loc[dpMin[i][]]=i;

        }

        RMQ();

        while(q--)

        {

            int l,r;

            scanf("%d%d",&l,&r);

            int k=log2(r-l+);

            int maxn=max(dpMax[l][k],dpMax[r-(<<k)+][k]);

            int minn=min(dpMin[l][k],dpMin[r-(<<k)+][k]);

            int left=max(dpLeft[l][k],dpLeft[r-(<<k)+][k]);

            int g=abs(dpMin[l][]-dpMin[r][]);

            if(r-l>)

                g=Gcd(g,Gcd(dpG[l][k],dpG[r-(<<k)+][k]));

            //cout<<maxn<<' '<<minn<<' '<<g<<' '<<left<<endl;

            if(maxn==minn)

                printf("Yes\n");

            else

            {

                if(left<l&&maxn-minn==(r-l)*g)

                    printf("Yes\n");

                else

                    printf("No\n");

            }

        }

    }

    return ;

}
 

相关文章