segmenttree.cpp (5) anotherstyle

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