Description

已知一個長度為?$n$?的數(shù)組?$a\left[1\right],a\left[2\right],\dots ,a\left[n\right]$，我們進行?$q$?次詢問，每次詢問區(qū)間?$a\left[l\right],a[l+1],\dots ,a[r?1],a\left[r\right]$，數(shù)字從小到大排列后，是否會形成等差數(shù)列。等差數(shù)列的定義為，數(shù)列相鄰兩項（后一項減去前一項）的差值相等。

Input

本題有多組輸入數(shù)據(jù)。

每組輸入數(shù)據(jù)第一行輸入兩個正整數(shù)?$n$?和?$q$。第二行輸入?$n$?個正整數(shù)?$a\left[1\right],a\left[2\right],\dots ,a\left[n\right]$。最后輸入?$q$?行，每行兩個數(shù)字?$l,r$（$1\le l\le r\le n$），表示詢問區(qū)間?$a\left[l\right],\dots ,a\left[r\right]$。

$1\le n,q\le {10}^5,1\le a\left[i\right]\le {10}^6$

Output

對于每組詢問輸出一行，如果形成等差數(shù)列，輸出“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 題目大意：給定一個數(shù)列，并給出很多區(qū)間詢問，問是否是等差數(shù)列。題解：這道題目用了一個很好的判斷等差數(shù)列的思想，首先如果區(qū)間內(nèi)最大值與最小值相同，那么一定是等差數(shù)列不然的話，判斷區(qū)間和與(max+min)*n/2是否相等，如不相等那么輸出No，否則再判斷區(qū)間gcd，如果是等差數(shù)列那么它的區(qū)間gcd應該等于其公差（這里是我覺得最精華的地方），而公差我們可以用(max-min)/(n-1)來計算得到 其中區(qū)間最值用線段樹維護，區(qū)間gcd也用線段樹維護 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define int long long const int MAX = 1e5+6; const int INF = 1e9; int n,q; int A[MAX]; int stmax[MAX<<2]; int stgcd[MAX<<2]; int stmin[MAX<<2]; int sum[MAX]; int gcd(int a,int b) {if(b == 0) return a;return gcd(b,a % b); } void init(int v,int l,int r) {if(r - l == 1){stmax[v] = stmin[v] = A[l];stgcd[v] = abs(A[l+1]-A[l]);}else{init(2*v+1,l,(l+r)/2);init(2*v+2,(l+r)/2,r);stmax[v] = max(stmax[2*v+1],stmax[2*v+2]);stmin[v] = min(stmin[2*v+1],stmin[2*v+2]);stgcd[v] = gcd(stgcd[2*v+1],stgcd[2*v+2]);} } int querymin(int v,int a,int b,int l,int r) {if(l <= a && r >= b) return stmin[v];else if(b <= l || r <= a) return INF;else return min(querymin(2*v+1,a,(a+b)/2,l,r),querymin(2*v+2,(a+b)/2,b,l,r)); } int querymax(int v,int a,int b,int l,int r) {if(l <= a && r >= b) return stmax[v];else if(b <= l || r <= a) return 0;else return max(querymax(2*v+1,a,(a+b)/2,l,r),querymax(2*v+2,(a+b)/2,b,l,r)); } int querygcd(int v,int a,int b,int l,int r) {if(l <= a && r >= b) return stgcd[v];else if(b <= l || r <= a) return 0;else return gcd(querygcd(2*v+1,a,(a+b)/2,l,r),querygcd(2*v+2,(a+b)/2,b,l,r)); } main() {while(~scanf("%lld%lld",&n,&q)){sum[0] = 0;for(int i = 0;i < n;i++){scanf(" %lld",&A[i]);sum[i+1] = sum[i] + A[i];}A[n] = A[n-1];init(0,0,n);for(int i = 0;i < q;++i){int l,r;scanf("%lld%lld",&l,&r);if(r - l <= 1) {puts("Yes");continue;}int mini = querymin(0,0,n,l-1,r);int maxi = querymax(0,0,n,l-1,r);if(maxi == mini) {puts("Yes");continue;}//cout<<r<<" "<<l-1<<endl;if((sum[r] - sum[l-1])*2 != (maxi + mini) * (r-l+1)){puts("No");continue;}int d = (maxi - mini) / (r - l);if((maxi-mini)%(r-l) == 0 && querygcd(0,0,n,l-1,r-1) == d) puts("Yes");else puts("No");}}return 0;}

總結(jié)

以上是生活随笔為你收集整理的等差区间 线段树+GCD的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。