Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #222 - QMAX2 - Nhập môn Interval Tree (but after NKLINEUP)
Ngày: 21-11-2011
Cập nhật: 21-11-2011
Người gửi: khanhptnk
Ngôn ngữ: Pascal
Xem: 1061

Điểm: 4.4/5 (24 Phiếu)


uses math;
 
const finp = '';
      fout = '';
      MAXN = 50001;
 
var fi, fo : text;
    add, val : array [0..5 * MAXN] of longint;
    n, m : longint;
    i, kind, x, y, v : longint;
 
procedure down(i, con1, con2 : longint);  inline;
begin
     inc(add[con1], add[i]);
     inc(add[con2], add[i]);
     inc(val[con1], add[i]);
     inc(val[con2], add[i]);
     add[i] := 0;
end;
 
procedure up(i, con1, con2: longint);  inline;
begin
     val[i] := max(val[con1], val[con2]);
end;
 
procedure update(i, l, r, d, c, v : longint);
var g, con1, con2 : longint;
begin
     if (l = d) and (r = c) then
        begin
             inc(add[i], v);
             inc(val[i], v);
             exit;
        end;
 
     g := (l + r) shr 1;
     con1 := i shl 1;
     con2 := con1 + 1;
 
     down(i, con1, con2);
 
     if (d <= g) then update(con1, l, g, d, min(g, c), v);
     if (c > g) then update(con2, g + 1, r, max(g + 1, d), c, v);
 
     up(i, con1, con2);
end;
 
function get(i, l, r, d, c : longint) : longint;
var g, con1, con2, ans : longint;
begin
     if (l = d) and (r = c) then
        exit(val[i]);
 
     g := (l + r) shr 1;
     con1 := i shl 1;
     con2 := con1 + 1;
 
     down(i, con1, con2);
 
     ans := -1000000000;
 
     if (d <= g) then ans := max(ans, get(con1, l, g, d, min(g, c)));
     if (c > g) then ans := max(ans, get(con2, g + 1, r, max(g + 1, d), c));
 
     exit(ans);
end;
 
begin
     assign(fi, finp);
     reset(fi);
     assign(fo, fout);
     rewrite(fo);
 
     read(fi, n, m);
     for i := 1 to m do
         begin
              read(fi, kind, x, y);
              if (kind = 0) then
                 begin
                      read(fi, v);
                      update(1, 1, n, x, y, v);
                 end
              else
                  writeln(fo, get(1, 1, n, x, y));
         end;
 
     close(fo);
     close(fi);
end.