Truy vấn max của đoạn con liên tiếp

Submit solution
Points: 4 (partial)
Time limit: 1.0s
Python 3 10.0s
Memory limit: 977M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho dãy số nguyên có n phần tử a1,a2,...,an và m truy vấn mỗi truy vấn có là hai giá trị L,R(1≤L≤R≤n) cần phải tìm giá trị lớn nhât của dãy con liên tục từ vị trí L đến vị trí R là tìm max của aL,aL+1,...,aR

Input

Dòng đầu gồm hai số nguyên dương n và m tương ứng với số phần tử của dãy và số truy vấn (1≤n,m≤105)

Dòng tiếp theo gồm n số nguyên là các phần tử của dãy có giá trị tuyệt đối không vượt quá 106

Các dòng cuối gồm m dòng mỗi dòng chứa hai số dương L,R(1≤L≤R≤n)

Output

Xuất ra m dòng mỗi dòng là giá trị lớn nhất của dãy con liên tục từ vị trí L đến R

Ví dụ

Input

Copy
6 3
4 7 2 8 1 -6
1 5
2 3
3 6

Output

Copy
8
7
8
tichpx

Comments


  • 1
    creator  commented on Nov. 15, 2022, 4:12 p.m. ← edit 5

    Nếu bài chỉ yêu cầu tìm max trên một đoạn (không có truy vấn cập nhật giá trị) thì ta có cách cài đặt sử dụng bảng thưa (sparse table). Xây bảng trong O(nlogn), trả lời mỗi truy vấn trong O(1).

    Copy
    vector<vector<int>> st; //st[i][j] max in range [j, j + 2^i - 1]
vector<int> vt;
int n, q;
cin >> n >> q; assert(n > 0);
vt.resize(n);
for(int i = 0; i < n; i++) cin >> vt[i];
st.resize(18, vector<int>(n)); //2^16 < 10^5 < 2^17
st[0] = vt;
for (int i = 1; (1 << i) <= n; i++)
    for (int j = 0; j + (1 << i) <= n; j++){
        //[j, j + 2^i - 1] = [j, j + 2^(i - 1) - 1] U [j + 2^(i - 1), j + 2^i - 1]
        st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
while(q--){
    int L, R, ind;
    cin >> L >> R;
    L--; R--;
    ind = (int)log2(R - L + 1);
    //2^ind <= R - L + 1 < 2^(ind + 1) -> L <= R - 2^ind + 1 <= L + 2^ind - 1 <= R
    cout << max(st[ind][L], st[ind][R - (1 << ind) + 1]) << '\n';
}

    • 0
      TICHPX  commented on Nov. 16, 2022, 1:39 a.m.

      Ngon


      • 1
        creator  commented on Nov. 18, 2022, 9:15 p.m.

        Em vừa sửa lại cách cài đặt thầy ạ :v