Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- type treap = record
- ls,rs,y,cost,sz,minimal,min,value,color,sum,a,b:int64;
- rev:int64;
- end;
- var t:array[0..222222] of treap;
- a,perm:array[0..222222] of int64;
- n,m,left,right,count,root,color,test:int64;
- ch:Char;
- i:longint;
- function min(a,b:int64):int64;
- begin
- if a<b then min:=a else min:=b;
- end;
- procedure swap(var t,y:int64);
- var u:int64;
- begin
- u:=t; t:=y; y:=u;
- end;
- function szof(x:int64):int64;
- begin
- if x > 0 then szof:=t[x].sz else szof:=0;
- end;
- function smin(x:int64):int64;
- begin
- if x = 0 then smin:=round(1e18) else
- smin:=t[x].min;
- end;
- function ssum(x:int64):int64;
- var res:int64;
- begin
- if x > 0 then
- begin
- if t[x].color=-1 then ssum:=t[x].sum else
- ssum:=t[x].color*szof(x);
- end else ssum:=0;
- end;
- procedure recalc(x:int64);
- begin
- if x > 0 then t[x].sz:=szof(t[x].ls)+szof(t[x].rs)+1;
- if x > 0 then
- begin
- t[x].sum:=t[x].cost+ssum(t[x].ls)+ssum(t[x].rs);
- end;
- end;
- procedure push(x:int64);
- begin
- if (x>0) and (t[x].color<>-1) then
- begin
- //swap(t[x].ls,t[x].rs);
- t[x].cost:=t[x].color;
- t[t[x].ls].color:=t[x].color;
- t[t[x].rs].color:=t[x].color;
- t[x].color:=-1;
- end;
- end;
- procedure merge(var x:int64; l,r:int64);
- begin
- if (l=0) then x:=r else
- if (r=0) then x:=l else
- begin
- push(l); push(r);
- if t[l].y>t[r].y then
- begin
- x:=l;
- merge(t[x].rs,t[x].rs,r);
- end else
- begin
- x:=r;
- merge(t[x].ls,l,t[x].ls);
- end;
- end;
- recalc(x);
- end;
- procedure split(x:int64; key:int64; var l,r:int64);
- var cur:int64;
- begin
- if x = 0 then
- begin
- l:=0;
- r:=0;
- exit;
- end;
- push(x);
- cur:=1+szof(t[x].ls);
- if cur<=key then
- begin
- l:=x;
- split(t[x].rs,key-cur,t[x].rs,r);
- end else
- begin
- r:=x;
- split(t[x].ls,key,l,t[x].ls);
- end;
- recalc(x);
- end;
- procedure print(x:int64);
- begin
- if x = 0 then exit;
- push(x);
- print(t[x].ls);
- write(t[x].cost,' ');
- print(t[x].rs);
- end;
- procedure shuffle(x:int64);
- var l,r:int64;
- i:longint;
- begin
- randomize;
- for i:= 1 to x do
- begin
- l:=random(100000)+1;
- r:=random(100000)+1;
- swap(perm[l],perm[r]);
- end;
- end;
- procedure insert(pos:int64; x:int64);
- var m,l,c,r:int64;
- begin
- count:=count+1;
- t[count].rev:=0;
- t[count].cost:=x;
- t[count].y:=perm[count];
- t[count].ls:=0;
- t[count].rs:=0;
- t[count].sz:=1;
- t[count].min:=x;
- t[count].value:=x;
- t[count].color:=-1;
- split(root,pos,l,r);
- merge(m,l,count);
- merge(root,m,r);
- end;
- procedure erase(pos:int64);
- var l,r,m,r1:int64;
- begin
- split(root,pos-1,l,r);
- split(r,l,m,r1);
- merge(root,l,r1);
- end;
- procedure reverse(l,r:int64);
- var left,right,l1,m:int64;
- begin
- split(root,r,left,right);
- split(left,l-1,l1,m);
- t[m].rev:=t[m].rev xor 1;
- merge(left,l1,m);
- merge(root,left,right);
- end;
- function getsum(l,r:int64):int64;
- var t1,t2,t3,t4,ans:int64;
- begin
- split(root,r,t1,t2);
- split(t1,l-1,t3,t4);
- ans:=t[t4].sum;
- merge(t1,t3,t4);
- merge(root,t1,t2);
- getsum:=ans;
- end;
- procedure coloring(l,r,color:int64);
- var ll,rr,m,ll1:int64;
- begin
- split(root,r,ll,rr);
- split(ll,l-1,ll1,m);
- t[m].color:=color;
- merge(ll,ll1,m);
- merge(root,ll,rr);
- end;
- begin
- assign(input,'sum.in');
- reset(input);
- assign(output,'sum.out');
- rewrite(output);
- for i:= 1 to 100000 do perm[i]:=i;
- shuffle(100000*8);
- readln(m,test);
- n:=0;
- count:=0;
- root:=0;
- for i:= 1 to m do
- begin
- // read(a[i]);
- a[i]:=0;
- insert(count,a[i]);
- end;
- coloring(1,n,0);
- for i:= 1 to test do
- begin
- read(ch);
- if ch = 'A' then
- begin
- readln(left,right,color);
- coloring(left,right,color);
- end else
- begin
- readln(left,right);
- writeln(getsum(left,right));
- end;
- end;
- end.
Add Comment
Please, Sign In to add comment