• API
• FAQ
• Tools
• Archive
daily pastebin goal
8%
SHARE
TWEET

# Untitled

a guest Dec 18th, 2018 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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);
195.  n:=0;
196.  count:=0;
197.  root:=0;
198.  for i:= 1 to m do
199.   begin
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
208.    if ch = 'A' then
209.     begin