Kiểu code này nên được dùng để code những bài phức tạp hơn.
Bài toán
Thực hiện các truy vấn tăng một đoạn L,R lên X đơn vị, và tìm giá trị lớn nhất trong khoảng L,R.
Độ phức tạp
Lên đến logarit cơ số 2 của n.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <iostream>
using namespace std;
#define f1(i,n) for (int i=1; i<=n; i++)
#define N 200005
int n, m;
int Lazy[N], Max[N];
struct node {
int ll, rr, Index;
node(int L, int R, int ID): ll(L),rr(R),Index(ID) {}
node left(){ return node(ll, (ll+rr)/2, Index*2); }
node right(){ return node((ll+rr)/2+1, rr, Index*2+1); }
int& lazy(){ return Lazy[Index]; }
void access(){
if (lazy()!=0) {
if (ll!=rr) left().lazy()+=lazy(), right().lazy()+=lazy();
Max[Index]+=lazy();
lazy()=0;
}
}
void update(int L, int R, int X){
access();
if (ll>R || rr<L || L>R) return;
if (L<=ll && ll<=rr && rr<=R) { lazy()+=X; access(); }
else {
left().update(L, R, X);
right().update(L, R, X);
Max[Index]=max(Max[Index*2], Max[Index*2+1]);
}
}
int get_max(int L, int R){
access();
if (ll>R || rr<L || L>R) return -0x3c3c3c3c;
if (L<=ll && ll<=rr && rr<=R) return Max[Index];
return max(left().get_max(L, R), right().get_max(L, R));
}
};
main(){
ios :: sync_with_stdio(false);
cin >> n >> m;
f1(i,m) {
int ch, x, y, z;
cin >> ch;
if (ch==0) { cin >> x >> y >> z; node(1,n,1).update(x, y, z); }
else { cin >> x >> y; cout << node(1,n,1).get_max(x,y) << '\n'; }
}
}
Nhận xét
Code này đã được dùng để nộp cho mọt bài tập trên SPOJ.
Tham khảo
vn.spoj.com/problems/QMAX2