Xếp hàng

Points: 0.07 (partial)

Time limit: 3.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

USACO January 2007 - Gold Division

Problem type

Allowed languages

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

Comments

Comments

Please read the guidelines before commenting.

0

dailamsiu commented on Dec. 29, 2025, 8:52 a.m.

sao cu tle vay nhi

1
TranThienPhuc2657 commented on Dec. 29, 2025, 10:23 a.m. ← edit 2 →
Mình có đọc qua bài bạn, thì mình thấy bài bạn không sai về ý tưởng, nhưng mà hàm get của bạn kém tối ưu ở chỗ:

return {min(get(id*2,l,m,u,v).first,get(id*2+1,m+1,r,u,v).first), max(get(id*2,l,m,u,v).second,get(id*2+1,m+1,r,u,v).second)};

Ở đây, bạn gọi truy hồi get(id*2,l,m,u,v) và get(id*2+1,m+1,r,u,v) hai lần, một hàm get(id,l,r,u,v) bạn gọi truy hồi bốn lần (hai nhánh con, mỗi nhánh con hai lần), thay vì thể ta có thể chỉ cần gọi hai lần truy hồi bình thường bằng cách lưu trước kết quả hai hàm get đó vào hai cái pair rồi sau đó mới return.

Đồng thời mình xin phép mở rộng thêm cho bạn một ý tưởng khác nhanh hơn như sau:

Do là mảng ban đầu không đổi, cho nên là bạn có thể cài đặt bảng thưa (RMQ), prepare trong ~\mathcal{O}(n \log n)~ và mỗi truy vấn thực hiện trong ~\mathcal{O}(1)~.

Chúc bạn làm bài tốt!

0

dailamsiu commented on Feb. 13, 2026, 11:34 a.m.

cam on ban

vominhmanh10 commented on Nov. 8, 2025, 11:48 a.m. ← edited →

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 commented on Oct. 10, 2025, 9:58 a.m.

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 commented on May 14, 2025, 2:18 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

4

Vinh9699 commented on March 24, 2025, 7:06 a.m. ← edit 11 →

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

-12

khanhlani commented on June 19, 2024, 12:54 p.m.

Lyna mãi đỉnh

This comment is hidden due to too much negative feedback. Show it anyway.

-13

quale1tankimcuong commented on July 11, 2024, 12:19 p.m.

xam xam la gioi

This comment is hidden due to too much negative feedback. Show it anyway.

10

Marr_HH commented on July 8, 2022, 2:27 p.m. ← edited →

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

8

LamTer commented on July 9, 2022, 3:47 a.m.

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

-192

MinhMinhMinhMinh commented on Dec. 17, 2021, 4:20 a.m. ← edited →

a

This comment is hidden due to too much negative feedback. Show it anyway.

70

leduykhongngu commented on Dec. 17, 2021, 4:21 a.m.

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