Bài toán
Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.
Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị.
Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]
Độ phức tạp
O ((m+q) log n)
#include <stdio.h>
int T[1230997];
int lazy[1230997];
int n, m;
int max(int a, int b){ return a>b?a:b; }
void diffuse(int node, int ll, int rr){
if (lazy[node]==0) return;
T[node] += lazy[node];
if (ll!=rr){ // not child
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node]; }
lazy[node]=0;
}
int query(int node, int ll, int rr, int u, int v){
diffuse(node, ll, rr);
if (rr<u or v<ll or ll>rr) return -1000111000;
if (u<=ll and ll<=rr and rr<=v) return T[node];
int q1 = query(node*2, ll, (ll+rr)/2, u, v);
int q2 = query(node*2+1, (ll+rr)/2+1, rr, u, v);
return max(q1, q2);
}
void update(int node, int ll, int rr, int u, int v, int value){
diffuse(node, ll, rr);
if (rr<u or v<ll or ll>rr) return;
if (u<=ll and rr<=v) {
T[node]+=value;
if (ll==rr) return;
lazy[node*2] += value;
lazy[node*2+1] += value; }
else {
update(node*2, ll, (ll+rr)/2, u, v, value);
update(node*2+1, (ll+rr)/2+1, rr, u, v, value);
T[node]=max(T[node*2], T[node*2+1]);
}
}
main(){
int p, q, w;
scanf("%d%d", &n, &m);
while(m--){
scanf("%d%d%d", &p, &q, &w);
update(1, 1, n, p, q, w); }
scanf("%d", &m);
while (m--){
scanf("%d%d", &p, &q);
printf("%d\n", query(1, 1, n, p, q));
}
}
Nhận xét
Bài tập này có thể giải quyết bằng BIT.
Mô tả
hàm Diffuse (node, ll, rr)
Đưa T[node] về giá trị thực của nó. Tức là T[node] += lazy[node]. Và sau cùng phải gán lazy[node] = 0.
Để được phép gán lazy[node] = 0 thì phải lazy hai con của nó trước, sau đó mới được reset lazy[node].
hàm Query (node, ll, rr, u, v)
Tính số lớn nhất trong khoảng u..v.
Trước hết cần đọc giá trị đúng của T[node]. Muốn vậy, phải Diffuse(node).
Xét ba trường hợp: "không liên quan", "nằm lọt trong vùng", và "giao".
hàm Update (node, ll, rr, u, v, value)
Cộng value vào tất cả phần tử trong khoảng u..v.
Trước hết cần Diffuse (node). Sau đó xét ba trường hợp: "không liên quan", "nằm lọt trong vùng", và "giao".
Lưu ý là sau khi gọi hàm này, T[node] phải được đưa về giá trị đúng của nó (vì lời gọi nó sẽ sử dụng T[node]).