Xếp hàng

Điểm: 0,07 (OI)

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

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

Input: stdin

Output: stdout

Nguồn bài:

USACO January 2007 - Gold Division

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hàng ngày khi lấy sữa, ~N~ con bò của bác John (~1~ ~\leq~ ~N~ ~\leq~ ~50000~) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá chênh lệch về chiều cao.

Bác John đã chuẩn bị một danh sách gồm ~Q~ (~1~ ~\leq~ ~Q~ ~\leq~ ~200000~) đoạn các con bò và chiều cao của chúng (trong phạm vi [~1~, ~10^6~]). Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữa con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này!

Input

Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~Q~.
Dòng thứ ~i~ trong số ~N~ dòng sau chứa ~1~ số nguyên duy nhất, là độ cao của con bò thứ ~i~.
Dòng thứ ~i~ trong số ~Q~ trong tiếp theo chứa ~2~ số nguyên ~A~, ~B~ (~1~ ~\leq~ ~A~ ~\leq~ ~B~ ~\leq~ ~N~), cho biết đoạn các con bò từ ~A~ đến ~B~.

Output

Gồm ~Q~ dòng, mỗi dòng chứa ~1~ số nguyên, là chênh lệch chiều cao giữa con bò thấp nhất và cao nhất thuộc đoạn tương ứng.

Sample Input

Sample Output

6
3
0

Bình luận

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

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

ta cần max và min một đoạn,... tạo 2 cây phân đoạn
mình cố gom vô 2 hàm build và query luôn, với query chỉ cần bool t đúng lấy min sai lấy max

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 5;
ll segmax[4 * maxn], segmin[4 * maxn];
int n, q, l ,r;
vector<ll> a;
void build(int node, int start, int end) {
    if (start == end) {
        segmin[node] = segmax[node] = a[end];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    segmax[node] = max(segmax[2 * node], segmax[2 * node + 1]);
    segmin[node] = min(segmin[2 * node], segmin[2 * node + 1]);
}
ll query(int node, int start, int end, int l, int r, bool t) {
    if (start > r || end < l) return (t ? 1e18 : -1e18);
    if (start >= l && end <= r) {
        return (t ? segmin[node] : segmax[node]);
    }
    int mid = (start + end) / 2;
    if (!t) return max(query(2 * node, start, mid, l, r, 0), query(2 * node + 1, mid + 1, end, l, r, 0));
    else return min(query(2 * node, start, mid, l, r, 1), query(2 * node + 1, mid + 1, end, l, r, 1));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q; a.resize(n);
    for (ll &x : a) cin >> x;
    build(1, 0, n - 1);
    while (q--) {
        cin >> l >> r;
        cout << query(1, 0, n - 1, l - 1, r - 1, 0) - query(1, 0, n - 1, l - 1, r - 1, 1) << "\n";
    }
}

-1

ngoccaidu2008 đã bình luận lúc 10, Tháng 10, 2025, 9:58

code tham khảo

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define __Hormer_Nguyen__ signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int maxn=5*1e6+5;;
int n,q,a[maxn],maxx[4*maxn],minn[4*maxn];
void segmax(int v,int l,int r)
{
    if (l==r)
    {
        maxx[v]=a[l];
        return;
    }int m=(l+r)/2;
    segmax(2*v,l,m);
    segmax(2*v+1,m+1,r);
    maxx[v]=max(maxx[2*v],maxx[2*v+1]);
}
void segmin(int v,int l,int r)
{
    if (l==r)
    {
        minn[v]=a[l];
        return;
    }int m=(l+r)/2;
    segmin(2*v,l,m);
    segmin(2*v+1,m+1,r);
    minn[v]=min(minn[2*v],minn[2*v+1]);
}
int getmin(int v,int l,int r,int x,int y)
{
    if (x>y) return 15032008;
    if (x==l && r==y) return minn[v];
    int m=(l+r)/2;
    int k=getmin(2*v,l,m,x,min(y,m));
    int k1=getmin(2*v+1,m+1,r,max(x,m+1),y);
    return min(k1,k);
}
int getmax(int v,int l,int r,int x,int y)
{
    if (x>y) return -15032008;
    if (x==l && r==y) return maxx[v];
    int m=(l+r)/2;
    int k=getmax(2*v,l,m,x,min(y,m));
    int k1=getmax(2*v+1,m+1,r,max(x,m+1),y);
    return max(k,k1);
}
__Hormer_Nguyen__
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    segmax(1,1,n);
    segmin(1,1,n);
    while (q--)
    {
        int l,r;cin>>l>>r;
        cout<<getmax(1,1,n,l,r)-getmin(1,1,n,l,r)<<endl;
    }
}

-6

THPTHD_Hieu đã bình luận lúc 14, Tháng 5, 2025, 14:18

xếp hàng làm gì v

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

4

Vinh9699 đã bình luận lúc 24, Tháng 3, 2025, 7:06 ← sửa 11 →

Dùng segment tree cơ bản nha mấy bạn 🤑😎🤯👍✌️

-12

khanhlani đã bình luận lúc 19, Tháng 6, 2024, 12:54

Lyna mãi đỉnh

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

-13

quale1tankimcuong đã bình luận lúc 11, Tháng 7, 2024, 12:19

xam xam la gioi

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

10

Marr_HH đã bình luận lúc 8, Tháng 7, 2022, 14:27 ← chỉnh sửa →

bài này phải code 2 tree ạ?

8

LamTer đã bình luận lúc 9, Tháng 7, 2022, 3:47

code 1 tree lấy cả min max luôn nha bạn

-190

MinhMinhMinhMinh đã bình luận lúc 17, Tháng 12, 2021, 4:20 ← chỉnh sửa →

a

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

69

leduykhongngu đã bình luận lúc 17, Tháng 12, 2021, 4:21

Bình luận của bạn mang tính spam và gây khiêu khích. Một lần nữa bạn sẽ bị cấm bình luận, nặng hơn là ban acc vĩnh viễn nhé.