首页 > 代码库 > F题:等差区间(RMQ)
F题:等差区间(RMQ)
原题大意:原题链接 题解链接
给定一个长为n的数组元素和q次区间[l,r]询问,判断区间[l,r]内元素排序后能否构成等差数列
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5+10; int n,q,l,r; int a[maxn],temp[1000010]; int mi[maxn][20],ma[maxn][20]; int gd[maxn][20],po[maxn][20]; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int ggg(int a,int b) { if(a==0||b==0) return 0; return gcd(a,b); } void Rmq_Precede() { for(int j=1;(1<<j)<=n;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]); mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); gd[i][j]=ggg(gd[i][j-1],gd[i+(1<<(j-1))][j-1]); po[i][j]=max(po[i][j-1],po[i+(1<<(j-1))][j-1]); } } } int Rmq_Max(int l,int r) { int k=log2(r-l+1); return max(ma[l][k],ma[r-(1<<k)+1][k]); } int Rmq_Min(int l,int r) { int k=log2(r-l+1); return min(mi[l][k],mi[r-(1<<k)+1][k]); } int Rmq_Gcd(int l,int r) { int k=log2(r-l+1); return gcd(gd[l][k],gd[r-(1<<k)+1][k]); } int Rmq_Pos(int l,int r) { int k=log2(r-l+1); return max(po[l][k],po[r-(1<<k)+1][k]); } int main() { while(scanf("%d%d",&n,&q)!=EOF){ memset(temp,0,sizeof(temp)); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); po[i][0]=temp[a[i]];//如果有重复元素,则temp[a[i]]会被覆盖 temp[a[i]]=i; mi[i][0]=ma[i][0]=a[i]; gd[i][0]=abs(a[i]-a[i-1]); } Rmq_Precede(); while(q--){ scanf("%d%d",&l,&r); if(l==r||l+1==r) {printf("Yes\n"); continue;} int curmi=Rmq_Min(l,r),curma=Rmq_Max(l,r),curgd=Rmq_Gcd(l+1,r); if(Rmq_Pos(l,r)>=l){//判重,如果数组中有相同元素,一定会执行此步骤 if(curmi==curma){printf("Yes\n"); continue;} else{printf("No\n"); continue;} } if(curgd*(r-l)==curma-curmi){printf("Yes\n"); continue;} else{printf("No\n"); continue;} } } return 0; }
F题:等差区间(RMQ)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。