Dãy cấp số cộng

View as PDF
Submit solution
Points: 1.33 (partial)
Time limit: 0.9s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Sưu tầm
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một dãy cấp số cộng là một dãy số mà 2 cặp phần tử liên tiếp bất kỳ có hiệu bằng nhau và khác 0. Trường hợp dãy số chỉ gồm 2 số khác nhau vẫn tính là một dãy cấp số cộng

Ví dụ:

  • 2, 5 là dãy cấp số cộng.
  • 8, 3 là dãy cấp số cộng.
  • 1, 2, 3, 4, 5 là dãy cấp số cộng.
  • 11, 8, 5, 2 là dãy cấp số cộng.
  • 1, 2, 4, 5, 7 không phải là dãy cấp số cộng.

Cho một dãy số A gồm N số nguyên dương. Cho Q truy vấn dạng (x, y). Mỗi truy vấn yêu cầu kiểm tra xem đoạn từ x tới y có phải là hoán vị của một dãy cấp số cộng không.

Input

  • Dòng đầu chứa 2 số nguyên ~N~, ~Q~.
  • Số thứ ~i~ trong ~N~ số ở dòng thứ 2 là ~A_{i}~.
  • Dòng thứ ~i~ trong ~Q~ dòng tiếp theo chứa 2 số nguyên ~x~, ~y~ mô tả truy vấn thứ ~i~.

Output

Gồm ~Q~ dòng.

  • Dòng thứ ~i~ trong ~Q~ dòng sẽ trả lời cho truy vấn thứ ~i~.
  • In ra YES nếu đoạn từ ~x~ tới ~y~ là hoán vị của một dãy cấp số cộng. Ngược lại thì ghi ra NO.

Giới hạn

11 test có ~N~, ~Q \le 1000~.

10 test có ~N \le 1000~, ~Q \le 10^{6}~.

10 test có ~N \le 10^{5}~, ~Q \le 10^{5}~.

~A_{i} \le 10^{9}~

Sample Input

5 2
1 3 2 5 4
1 5
2 4

Sample Output

YES
NO

Comments

Please read the guidelines before commenting.


  • 4
    thieen  commented on Nov. 1, 2025, 2:55 p.m.

    helo


  • 35
    RussVN123  commented on June 15, 2024, 5:28 p.m. ← edited

    Spoil cho bài này

    Để làm bài này thì cần xét các yếu tố sau 1.tổng đoạn L-R phải bằng cấp số cộng r-l+1 phần tử với u1=minL-R và u2=maxL-R 2.Các phần tử chỉ xuất hiện đúng 1 lần duy nhất -> để làm thì chỉ cần tạo mảng b là vị trí gần nhất bên trái có giá trị = a[i] . Lấy max L-R mảng b thì nếu lớn hơn bằng l thì sẽ có trùng . cuối cùng.(a[i]-minLR)%công sai =0 (l<=i<=r). Nghĩa là kiểm tra mỗi a[i] có thể được tạo thành từ minLR không , vì các số tạo thành cấp số cộng phải bằng minLR + d*x. Để kiểm tra cái trên ta cần phân tích tiếp: (a[i]-minLR) % công sai =0 => a[i]%công sai =minLR % công sai. Ta có thể kiểm tra bằng cách lấy đại 1 số trong đoạn L R và check ( đây là đk thứ 1 ). Nhưng mà 1 số đúng thì ko có nghĩa cả dãy đúng. Nên ta cần kiểm tra nhanh các số còn lại ( gọi công sai là d) : a[i]%d=a[i+1]%d=a[i+2]%d=...=a[i+n]%d. Tiếp tục biến đổi thì a[i]%d=a[i+1]%d => (a[i]-a[i+1])%d =0 ( tương tự là cặp a[i+1] và a[i+2]). Như vậy cần check xem các abs(a[i]-a[i+1])có chia hết d hay không và cần kiểm r-l cặp có i trong khoảng L->R-1. Để kiểm nhanh thì chỉ cần lấy GCD là được vì nếu có thỏa hết thì các abs sẽ luôn là bội của d .


    • -5
      imdabetbaby  commented on Dec. 29, 2024, 4:32 p.m. ← edit 3

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -10
      englishthaonguyendethuong  commented on Oct. 6, 2024, 3:21 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • 3
        RussVN123  commented on Oct. 7, 2024, 8:38 a.m.

        Code mình đây, nếu bạn muốn tham khảo:

        include <bits/stdc++.h>

        using namespace std; const int maxn=1e5+1; int n,q,x,y,pospre[maxn]; long long pre[maxn],a[maxn],pregcd[maxn],pow2[21],rgcd[maxn][21],rmin[maxn][21],rmax[maxn][21],check[maxn][21]; long long get(int l,int r,int type,long long rmq[][21]) { long long res; if (type==0) res=0; if (type==1) res=1e10; int k = log2(r-l+1); if (type==0) res=max(rmq[l+pow2[k]-1][k],rmq[r][k]); if (type==1) res=min(rmq[l+pow2[k]-1][k],rmq[r][k]); if (type==2) res=gcd(rmq[l+pow2[k]-1][k],rmq[r][k]); return res; } int main() { iosbase::syncwithstdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>q; map<int,int> mp; pre[0]=0; pow2[0]=1; pregcd[n]=1; rgcd[n][0]=1; for (int i=1;i<=20;++i) pow2[i]=pow2[i-1]2; for (int i=1;i<=n;++i) cin>>a[i]; for (int i=1;i<=n;++i) { pospre[i]=mp[a[i]]; pre[i]=pre[i-1]+a[i]; if (i<n) pregcd[i]=abs(a[i]-a[i+1]); rmin[i][0]=a[i]; rmax[i][0]=a[i]; check[i][0]=pospre[i]; rgcd[i][0]=pregcd[i]; mp[a[i]]=i; } for (int k=1;k<=18;++k) for (int i=1;i<=n;++i) if (i-pow2[k]>=0) { rmin[i][k]=min(rmin[i][k-1],rmin[i-pow2[k-1]][k-1]); rmax[i][k]=max(rmax[i][k-1],rmax[i-pow2[k-1]][k-1]); check[i][k]=max(check[i][k-1],check[i-pow2[k-1]][k-1]); rgcd[i][k]=gcd(rgcd[i][k-1],rgcd[i-pow2[k-1]][k-1]); } for (int i=1;i<=q;++i) { int l,r; long long val,ds,f1,f2; long double d,tong,minv,maxv; cin>>x>>y; l=x; r=y; f1 =get(l,r,1,rmin); f2 =get(l,r,0,rmax); minv = static_cast<long double>(f1); maxv = static_cast<long double>(f2); tong=(r-l+1)(minv+maxv)/2.0; d=(maxv-minv)/(r-l); if (d==0 || r-l+1<2 ) { cout<<"NO\n"; continue; } if (get(l,r,0,check)>=l) { cout<<"NO\n"; continue; } if (tong!=pre[r]-pre[l-1]) { cout<<"NO\n"; continue; } ds = (f2-f1)/(r-l); if (ds!=d) { cout<<"NO\n"; continue ;} // dk : A i (l<=i<=r) %d==minv%d val=f1%ds; // check a i %d == a i+1 %d hay khong -> a i - a i+1 % d==0 if (get(l,r-1,2,rgcd)%ds!=0) { cout<<"NO\n"; continue ;} // check 1 so bat ky trong doan l r co a i %d = minv % d hay khong if (a[r]%ds!=val) { cout<<"NO\n"; continue ;} cout<<"YES\n"; } return 0; }


    • -8
      englishthaonguyendethuong  commented on Oct. 6, 2024, 5:54 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


      • 2
        RussVN123  commented on Oct. 7, 2024, 8:35 a.m.

        Bạn xem điều kiện 1 á bạn, tổng trên là 2+5+8+14+17, còn tổng cấp số cộng với u1=2 và un=17 thì là 2+5+8+11+14+17


  • -12
    chithien19112008  commented on Feb. 17, 2024, 9:27 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -5
    wipad0310  commented on Feb. 2, 2024, 5:23 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 1
      RussVN123  commented on June 15, 2024, 5:31 p.m. ← edited

      Được bạn ạ. Bạn có thể xem sol của mình bên trên.


  • -37
    chunguyen2k8  commented on Feb. 1, 2024, 1:53 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -5
      yuriFiona_  commented on Feb. 1, 2024, 2:25 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -13
    Winboy423minhkhoi  commented on July 23, 2023, 2:16 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -4
      dawacola  commented on March 1, 2024, 11:12 a.m.

      Bài này làm như nào vậy bạn


  • -23
    tuanminhdt  commented on June 29, 2023, 3:51 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -99
    nthquan_1505  commented on March 27, 2023, 2:51 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.