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

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ử \(a_1, a_2, ...,a_n\) và \(m\) truy vấn mỗi truy vấn có là hai giá trị \(L, R (1 \leq L \leq R \leq 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 \(a_L, a_{L+1}, ..., a_R\)

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 \leq n,m \leq 10^5)\)

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á \(10^6\)

Các dòng cuối gồm \(m\) dòng mỗi dòng chứa hai số dương \(L, R (1 \leq L \leq R \leq 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

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

Output

8
7
8

tichpx

Comments

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).

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