给n个数字，q个询问，问每次循环的那部分数字排序后能否构成等差数列
区间内无相同元素 且 相邻两项差构成的数列的GCD ×（R-L）= (区间最大值-区间最小值） 正向推就是说，差的gcd就是公差 4 5 6 7和4 5 6 4都是gcd = 1 也就是说，当出现重复元素的时候，会出错，那么特判这一种，每个点记录上一次出现这个数字的位置，那么一旦区间包括这两个（且不相连）就不可能是等差，且，这个位置能接受的最左侧位置，不可能再它前面那个位置所接受的左边，这就可以On求出每个点的可能最左边到哪里 但是反向推，如果不成立，就是非等差（待证明）
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> using namespace std; int n,q; const int maxn = 1e5+10; typedef pair<int,int> pii; int ans,a[maxn],stgcd[maxn][30],stmax[maxn][30],stmin[maxn][30],tmax,tmin; int pre[maxn],book[maxn*10]; int gcd(int a,int b){ return (b == 0)? a : gcd(b,a%b); } void getst(){ for(int i = n ; i > 0; i--){ for(int j = 1 ; i + (1 << j)-1 <= n ;j++){ stmax[i][j] = max(stmax[i][j-1],stmax[i+(1 << (j-1) )][j-1]); stmin[i][j] = min(stmin[i][j-1],stmin[i+(1 << (j-1) )][j-1]); if(i > 1){ if(stgcd[i][j-1] == 0 || stgcd[i+(1 << (j-1) )][j-1] == 0) stgcd[i][j] = 0; else stgcd[i][j] = gcd(stgcd[i][j-1],stgcd[i+(1 << (j-1) )][j-1]); } } } } pii qur(int l ,int r){ int k = (int) floor(log2(r-l+1)); return make_pair(max(stmax[l][k],stmax[r-(1<<k)+1][k]),min(stmin[l][k],stmin[r-(1<<k)+1][k])); } int qurgcd(int l ,int r){ int k = (int) floor(log2(r-l+1)); if(stgcd[l][k] == 0||stgcd[r-(1<<k)+1][k]==0) return 0; return gcd(stgcd[l][k],stgcd[r-(1<<k)+1][k]); } int sov(int l,int r){ pii tmp = qur(l,r); tmax = tmp.first; tmin = tmp.second; //cout << tmax << " "<< tmin <<" "<<r <<" "<<l <<endl; if((tmax-tmin)%(r-l)) return 0; int kk = (tmax-tmin)/(r-l); //printf("kk = %d\n",kk); if(qurgcd(l+1,r) == kk) return 1; return 0; } void init(){ memset(book,0,sizeof(book)); for(int i = 1; i <= n ; i++){ scanf("%d",&a[i]); stmax[i][0] = stmin[i][0] = a[i]; if(book[a[i]] == i-1) pre[i] = pre[i-1]; else pre[i] = max(book[a[i]],pre[i-1]); book[a[i]] = i; if(i > 1) stgcd[i][0] = max(a[i]-a[i-1],a[i-1]-a[i]); } getst(); //cout <<"gcd = "<<stmin[9][0] <<" "<<stmin[9][1] <<" "<<stmin[7][2]<<endl; for(int i = 1; i <= q; i++){ int l,r; scanf("%d%d",&l,&r); if(l == r || l +1 == r) printf("Yes\n"); else if(l <= pre[r]) printf("No\n"); else if( sov(l,r)) printf("Yes\n"); else printf("No\n"); } } int main(){ while(~scanf("%d%d",&n,&q)){ init(); } } /* 10 10 1 3 2 5 4 4 5 6 4 8 6 10 */