等差区间
题目链接：http://dutacm.club:7217/codesheaven/problem.php?id=1094
题目大意：给出n个数及q个区间，询问每个区间内数字升序排列后是否为等差数列.
数学
若想知道区间内数是否能够成等差数列，显然要求出区间内的最值（即数列首项和末项）.
注意到若区间内数能成等差数列，则需满足下列中的一项：
- 公差为零；
- 公差不为零，则数列内无相同元素，那么公差为相邻两数差的最大公因数.
可以rmq等维护区间最值，区间最大公因数，以及区间内元素上一次出现的最近位置（用来判断区间内有无相同元素），时间复杂度为O（nlgn+q）.
代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #define Min(a,b) (a<b?a:b) 6 #define Max(a,b) (a>b?a:b) 7 #define N 100005 8 using namespace std; 9 int n,q,a[N],maxn,minn,mgcd,mpre,l,r; 10 int dmax[N][18],dmin[N][18],dgcd[N][18],dpre[N][18],p[1000005]; 11 int gcd(int a,int b){return b?gcd(b,a%b):a;} 12 void init(){ 13 memset(p,0,sizeof(p)); 14 for(int i=1;i<=n;++i){ 15 scanf("%d",&a[i]); 16 dmax[i][0]=dmin[i][0]=a[i]; 17 dpre[i][0]=p[a[i]]; 18 p[a[i]]=i; 19 } 20 for(int j=1;(1<<j)<=n+1;++j){ 21 for(int i=1;i+(1<<j)<=n+1;++i){ 22 dmax[i][j]=Max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]); 23 dmin[i][j]=Min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]); 24 dpre[i][j]=Max(dpre[i][j-1],dpre[i+(1<<(j-1))][j-1]); 25 } 26 } 27 for(int i=1;i<n;++i)dgcd[i][0]=abs(a[i]-a[i+1]); 28 for(int j=1;(1<<j)<=n;++j) 29 for(int i=1;i+(1<<j)<=n;++i) 30 dgcd[i][j]=gcd(dgcd[i][j-1],dgcd[i+(1<<(j-1))][j-1]); 31 } 32 void get(int l,int r){ 33 int len=log(r-l+1.0)/log(2.0); 34 maxn=Max(dmax[l][len],dmax[r+1-(1<<len)][len]); 35 minn=Min(dmin[l][len],dmin[r+1-(1<<len)][len]); 36 mpre=Max(dpre[l][len],dpre[r+1-(1<<len)][len]); 37 len=log(r-l)/log(2.0); 38 mgcd=gcd(dgcd[l][len],dgcd[r-(1<<len)][len]); 39 } 40 int main(void){ 41 while(~scanf("%d%d",&n,&q)){ 42 init(); 43 while(q--){ 44 scanf("%d%d",&l,&r); 45 if(r-l<=1){ 46 puts("Yes"); 47 continue; 48 } 49 get(l,r); 50 if(maxn==minn||(mpre<l&&maxn-minn==mgcd*(r-l)))puts("Yes"); 51 else puts("No"); 52 } 53 } 54 }