Dãy cấp số cộng

Xem dạng PDF
Gửi bài giải
Điểm: 1,33 (OI)
Giới hạn thời gian: 0.9s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Sưu tầm
Dạng bài
Ngôn ngữ cho phép
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

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 28
    RussVN123  đã bình luận lúc 15, Tháng 6, 2024, 17:28 ← chỉnh sửa

    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 .


    • -3
      imdabetbaby  đã bình luận lúc 29, Tháng 12, 2024, 16:32 ← sửa 3

      .


    • -5
      englishthaonguyendethuong  đã bình luận lúc 6, Tháng 10, 2024, 15:21

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • 1
        RussVN123  đã bình luận lúc 7, Tháng 10, 2024, 8:38

        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; }


    • -5
      englishthaonguyendethuong  đã bình luận lúc 6, Tháng 10, 2024, 5:54 ← chỉnh sửa

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • 0
        RussVN123  đã bình luận lúc 7, Tháng 10, 2024, 8:35

        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


  • -10
    chithien19112008  đã bình luận lúc 17, Tháng 2, 2024, 9:27 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -3
    wipad0310  đã bình luận lúc 2, Tháng 2, 2024, 17:23

    Bài này làm được bằng segment tree không vậy mọi người :> Ý tưởng của mình là tìm giá trị lớn nhất và lớn nhất của đoạn cần truy vấn, sau đó tính tổng bằng công thức cấp số cộng và tổng của đoạn đó (mảng cộng dồn). Tất nhiên là mình vẫn chưa làm được :(


    • 0
      RussVN123  đã bình luận lúc 15, Tháng 6, 2024, 17:31 ← chỉnh sửa

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


  • -31
    chunguyen2k8  đã bình luận lúc 1, Tháng 2, 2024, 1:53

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -4
      yuriFiona_  đã bình luận lúc 1, Tháng 2, 2024, 2:25 ← chỉnh sửa

      anh nguyen ton noi chi phai


  • -13
    Winboy423minhkhoi  đã bình luận lúc 23, Tháng 7, 2023, 2:16

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -4
      dawacola  đã bình luận lúc 1, Tháng 3, 2024, 11:12

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


  • -21
    tuanminhdt  đã bình luận lúc 29, Tháng 6, 2023, 3:51 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -85
    nthquan_1505  đã bình luận lúc 27, Tháng 3, 2023, 2:51

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.