iliya785

Segment Tree with set on segment and RSQ

Aug 9th, 2014
247
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 1.05 KB | None | 0 0
  1. uses
  2.     math;
  3.  
  4. var
  5.     t,sum:array[0..1000000] of int64;
  6.     i,n,m,l,r,x:longint;
  7.     c:char;
  8.    
  9. procedure upd(v,l,r:longint);
  10. var
  11.     m:longint;
  12. begin
  13.     if t[v] > -1 then
  14.         begin
  15.             t[v + v] := t[v];
  16.             t[v + v + 1]:=t[v];
  17.             m:=(l + r) shr 1;
  18.             sum[v + v]:=t[v] * (m - l + 1);
  19.             sum[v + v + 1]:=t[v] * (r - m);
  20.             t[v]:=-1;
  21.         end;
  22. end;
  23.    
  24. procedure update(v,l,r,x,y:longint;color:int64);
  25. var
  26.     m:longint;
  27. begin
  28.     if x > y then   exit;
  29.     if (l = x) and (r = y) then
  30.         begin
  31.             t[v] := color;
  32.             sum[v] := color * (r - l + 1);
  33.         end
  34.     else
  35.         begin
  36.             m:=(l + r) shr 1;
  37.             upd(v, l ,r);
  38.             update(v + v, l, m, x, min(m, y), color);
  39.             update(v + v + 1, m + 1, r, max(m + 1, x), y ,color);
  40.             sum[v]:=sum[v + v] + sum[v + v + 1];
  41.         end;
  42. end;
  43.  
  44. function sum_q(v,l,r,x,y:longint):int64;
  45. var
  46.     m:longint;
  47. begin
  48.     if x > y then   exit(0);
  49.     if (l = x) and (r = y) then
  50.         exit(sum[v])
  51.     else
  52.         begin
  53.             upd(v, l , r);
  54.             m:=(l + r) shr 1;
  55.             exit(sum_q(v + v, l, m, x, min(y, m)) + sum_q(v + v + 1, m + 1, r, max(m + 1,x), y));
  56.         end;
  57. end;
  58.  
  59. Begin
  60. end.
Advertisement
Add Comment
Please, Sign In to add comment