Truy vấn số nhỏ nhất trên dãy số - LCOJ: Luyện Code Online Judge

QMIN - Truy vấn số nhỏ nhất trên dãy số

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho dãy số nguyên gồm ~n~ phần tử ~a_1, a_2, …, a_n~ và ~Q~ truy vấn. Mỗi truy vấn có dạng một cặp số nguyên ~u, v~. Với mỗi truy vấn ~u, v~, bạn cần trả lời câu hỏi số nhỏ nhất trong các số từ số thứ ~u~ tới số thứ ~v~ là bao nhiêu?

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~Q~;
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, …, a_n~;
~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~.

Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.

Giới hạn:

~1 ≤ n ≤ 10^6; 1 ≤ u ≤ v ≤ n; 1 ≤ Q ≤ 10^5; |a_i| ≤ 10^9~.

Output

Ghi trên một dòng ~Q~ số nguyên, mỗi số là câu trả lời cho một truy vấn (theo đúng thứ tự), hai số liên tiếp cách nhau một dấu cách.

Sample

Input #1

5 3
2 -1 5 3 -3
1 3
3 4
1 5

Output #1

-1 3 -3

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

các bạn có thể sử dụng segmentTree để giải quyết bài tập này

code tham khảo (C++)

#include <bits/stdc++.h>
#define int long long 
using namespace std; 
const int maxn = 1e6; 
int n, q, u, v, que; 
int a[maxn], st[maxn << 2];
void build(int id, int l, int r) {  
    if(l == r) {
        st[id] = a[l]; 
        return; 
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid); 
    build(id << 1 | 1, mid + 1, r); 
    st[id] = min(st[id << 1], st[id << 1 | 1]); 
}
int query(int id, int l, int r, int u, int v) {
    if(r < u || v < l) return 1e18; 
    if(u <= l && r <= v) return st[id]; 
    int mid = (l + r) >> 1; 
    return min(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v)); 
}
int32_t main() {
    ios::sync_with_stdio(true); 
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i]; 
    build(1, 1, n); 
    while(q--) {
        cin >> u >> v; 
        cout << query(1, 1, n, u, v) << " ";
    }
}

0

toilamanh23 đã bình luận lúc 2, Tháng 1, 2026, 1:56

test 4,5,6 là gì ạ mk bị RTE đoạn này

0

teocs đã bình luận lúc 11, Tháng 12, 2025, 8:24 ← chỉnh sửa →

hi