Guest User

Untitled

a guest
Dec 18th, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 3.76 KB | None | 0 0
  1. type treap = record
  2.      ls,rs,y,cost,sz,minimal,min,value,color,sum,a,b:int64;
  3.      rev:int64;
  4.      end;
  5.  
  6. var t:array[0..222222] of treap;
  7.     a,perm:array[0..222222] of int64;
  8.     n,m,left,right,count,root,color,test:int64;
  9.     ch:Char;
  10.     i:longint;
  11. function min(a,b:int64):int64;
  12. begin
  13.  if a<b then min:=a else min:=b;
  14. end;
  15.  
  16. procedure swap(var t,y:int64);
  17. var u:int64;
  18. begin
  19.  u:=t; t:=y; y:=u;
  20. end;
  21.  
  22. function szof(x:int64):int64;
  23. begin
  24.  if x > 0 then szof:=t[x].sz else szof:=0;
  25. end;
  26.  
  27. function smin(x:int64):int64;
  28. begin
  29.  if x = 0 then smin:=round(1e18) else
  30.  smin:=t[x].min;
  31. end;
  32.  
  33. function ssum(x:int64):int64;
  34. var res:int64;
  35. begin
  36.  if x > 0 then
  37.   begin
  38.    if t[x].color=-1 then ssum:=t[x].sum else
  39.    ssum:=t[x].color*szof(x);
  40.   end else ssum:=0;
  41. end;
  42.  
  43.  
  44. procedure recalc(x:int64);
  45. begin
  46.  if x > 0 then t[x].sz:=szof(t[x].ls)+szof(t[x].rs)+1;
  47.  if x > 0 then
  48.   begin
  49.    t[x].sum:=t[x].cost+ssum(t[x].ls)+ssum(t[x].rs);
  50.   end;
  51. end;
  52.  
  53. procedure push(x:int64);
  54. begin
  55.  if (x>0) and (t[x].color<>-1) then
  56.   begin
  57.    //swap(t[x].ls,t[x].rs);
  58.    t[x].cost:=t[x].color;
  59.    t[t[x].ls].color:=t[x].color;
  60.    t[t[x].rs].color:=t[x].color;
  61.    t[x].color:=-1;
  62.   end;
  63.  
  64. end;
  65.  
  66. procedure merge(var x:int64; l,r:int64);
  67. begin
  68.  if (l=0) then x:=r else
  69.  if (r=0) then x:=l else
  70.   begin
  71.     push(l); push(r);
  72.    if t[l].y>t[r].y then
  73.     begin
  74.      x:=l;
  75.      merge(t[x].rs,t[x].rs,r);
  76.     end else
  77.     begin
  78.      x:=r;
  79.      merge(t[x].ls,l,t[x].ls);
  80.     end;
  81.   end;
  82.  recalc(x);
  83. end;
  84.  
  85. procedure split(x:int64; key:int64; var l,r:int64);
  86. var cur:int64;
  87. begin
  88.  if x = 0 then
  89.   begin
  90.    l:=0;
  91.    r:=0;
  92.    exit;
  93.   end;
  94.  push(x);
  95.  cur:=1+szof(t[x].ls);
  96.  if cur<=key then
  97.   begin
  98.    l:=x;
  99.    split(t[x].rs,key-cur,t[x].rs,r);
  100.   end else
  101.   begin
  102.    r:=x;
  103.    split(t[x].ls,key,l,t[x].ls);
  104.   end;
  105.  recalc(x);
  106. end;
  107.  
  108. procedure print(x:int64);
  109. begin
  110.  if x = 0 then exit;
  111.  push(x);
  112.  print(t[x].ls);
  113.  write(t[x].cost,' ');
  114.  print(t[x].rs);
  115. end;
  116.  
  117. procedure shuffle(x:int64);
  118. var l,r:int64;
  119.    i:longint;
  120. begin
  121.  randomize;
  122.  for i:= 1 to x do
  123.   begin
  124.    l:=random(100000)+1;
  125.    r:=random(100000)+1;
  126.    swap(perm[l],perm[r]);
  127.   end;
  128. end;
  129.  
  130. procedure insert(pos:int64; x:int64);
  131. var m,l,c,r:int64;
  132. begin
  133.  count:=count+1;
  134.  t[count].rev:=0;
  135.  t[count].cost:=x;
  136.  t[count].y:=perm[count];
  137.  t[count].ls:=0;
  138.  t[count].rs:=0;
  139.  t[count].sz:=1;
  140.  t[count].min:=x;
  141.  t[count].value:=x;
  142.  t[count].color:=-1;
  143.  split(root,pos,l,r);
  144.  merge(m,l,count);
  145.  merge(root,m,r);
  146. end;
  147.  
  148. procedure erase(pos:int64);
  149. var l,r,m,r1:int64;
  150. begin
  151.  split(root,pos-1,l,r);
  152.  split(r,l,m,r1);
  153.  merge(root,l,r1);
  154. end;
  155.  
  156. procedure reverse(l,r:int64);
  157. var left,right,l1,m:int64;
  158. begin
  159.  split(root,r,left,right);
  160.  split(left,l-1,l1,m);
  161.  t[m].rev:=t[m].rev xor 1;
  162.  merge(left,l1,m);
  163.  merge(root,left,right);
  164. end;
  165.  
  166. function getsum(l,r:int64):int64;
  167. var t1,t2,t3,t4,ans:int64;
  168. begin
  169.  split(root,r,t1,t2);
  170.  split(t1,l-1,t3,t4);
  171.  ans:=t[t4].sum;
  172.  merge(t1,t3,t4);
  173.  merge(root,t1,t2);
  174.  getsum:=ans;
  175. end;
  176.  
  177. procedure coloring(l,r,color:int64);
  178. var ll,rr,m,ll1:int64;
  179. begin
  180.  split(root,r,ll,rr);
  181.  split(ll,l-1,ll1,m);
  182.  t[m].color:=color;
  183.  merge(ll,ll1,m);
  184.  merge(root,ll,rr);
  185. end;
  186.  
  187. begin
  188.  assign(input,'sum.in');
  189.  reset(input);
  190.  assign(output,'sum.out');
  191.  rewrite(output);
  192.  for i:= 1 to 100000 do perm[i]:=i;
  193.  shuffle(100000*8);
  194.  readln(m,test);
  195.  n:=0;
  196.  count:=0;
  197.  root:=0;
  198.  for i:= 1 to m do
  199.   begin
  200.   // read(a[i]);
  201.   a[i]:=0;
  202.    insert(count,a[i]);
  203.   end;
  204.  coloring(1,n,0);
  205.  for i:= 1 to test do
  206.   begin
  207.    read(ch);
  208.    if ch = 'A' then
  209.     begin
  210.      readln(left,right,color);
  211.      coloring(left,right,color);
  212.     end else
  213.     begin
  214.      readln(left,right);
  215.      writeln(getsum(left,right));
  216.     end;
  217.   end;
  218.  
  219. end.
Add Comment
Please, Sign In to add comment