Truy vấn max (Trại hè MB 2019)

Tác giả:

Dạng bài

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hệ thống quản lý nhân sự của công ty \(X\) cần quản lý thông tin về lương của \(n\) nhân viên đánh số từ \(1\) tới \(n\). Lương
khởi điểm của tất cả các nhân viên là \(0\) và hệ thống cần cung cấp hai lệnh:

Lệnh cập nhật \(S(i, k)\): Đặt lương cho nhân viên \(i\) là \(k (1 < i < n; 0 < k < 10^9)\)
Lệnh truy vấn \(Q(i, j)\): Cho biết lương của nhân viên hưởng lương cao nhất trong số các nhân viên từ \(i\) tới \(j\)
\((1\le i \le j \le n)\)

Yêu cầu: Cho một dãy \(m\) lệnh thuộc một trong hai loại trên, hãy trả lời tất cả các lệnh truy vấn

Input

Vào từ file văn bản QUERY.INP
Dòng 1 chứa hai số nguyên dương \(n, m \le 10^5\).
\(m\) dòng tiếp theo, mỗi dòng chứa thông tin về một lệnh, đầu tiên là một ký tự \(\in\) {\(S\), \(Q\)}:
- Nếu ký tự đầu dòng là \(S\), tiếp theo là hai số nguyên \(j, k\) cho biết lệnh đó là \(S(i, k)\).
- Nếu ký tự đầu dòng là \(Q\), tiếp theo là hai số nguyên \(i, j\) cho biết lệnh đó là \(Q(i, j)\)

Output

Ghi ra file văn bản QUERY.OUT
Tương ứng với mỗi lệnh truy vấn \(Q\) trong file dữ liệu, ghi ra trên một dòng một số nguyên là câu trả lời cho truy
vấn đó.

Example

Test 1

Input

Output

5
7

Bình luận

1

truongngoclamCB1 11:01 p.m. 11 Tháng 8, 2024

Seg Tree hả mọi người ?

-2

CODE C++ Cho Ai Cần

#include<bits/stdc++.h>
using namespace std;
#define N 1e6
#define ll long long
int a[N+5];
ll st[N*4+20];
void capnhat(int id, int l, int r, int p, int gtri)
{
    if(p<l || r<p) return;
    if(l==r)
    {
        st[id]=gtri;
        return;
    }
    int m=(l+r)/2;
    capnhat(id*2,l,m,p,gtri);
    capnhat(id*2+1,m+1,r,p,gtri);
    st[id]=max(st[id*2],st[id*2+1]);
}
ll Tinh(int id,int l,int r,int u, int v)
{
    if(l>v || r<u) return 0;
    if(l>=u && r<=v) return st[id];
    int m=(l+r)/2;
    ll t1=Tinh(id*2,l,m,u,v);
    ll t2=Tinh(id*2+1,m+1,r,u,v);
    return max(t1,t2);
}
int n, q;
char type;
int x, y;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n >> q;
    for(; q>=1;q--)
    {
        cin >> type >> x >> y;
        if(type=='S') capnhat(1,1,n,x,y);
        else cout << Tinh(1,1,n,x,y) << '\n';
    }
    return 0;
}

1

kingofgame 10:20 p.m. 4 Tháng 4, 2024

https://ideone.com/rGhJW9 sol cho ai cần