Description
Input
Output
每次x=1时，每行一个整数，表示这次旅行的开心度
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9
Source
SPOJ2713 gss4 数据已加强
Solution
显然是一道线段树,开根号直接暴力就可以了,对于任意一个数最多开5次就变为1,之后就不要在开根了,打一个Tag记录一下。
type
tree=record
s,q,l,r:int64;
end;
var
n,m,k,x,y,i:longint;
f:array [..] of tree;
a:array [..] of longint;
procedure build(x,l,r:longint);
begin
f[x].l:=l;f[x].r:=r;
if l=r then
begin
f[x].s:=a[l];
if (f[x].s=) or (f[x].s=)
then f[x].q:=
else f[x].q:=;
exit;
end;
build(x<<,l,(l+r) >> );
build(x<<+,(l+r) >> +,r);
f[x].s:=f[x<<].s+f[x<<+].s;
f[x].q:=f[x<<].q and f[x<<+].q;
end; function plus(x,l,r:longint):int64;
var
mid:longint;
begin
plus:=;
if (f[x].l<=l) and (f[x].r>=r) then exit(f[x].s);
mid:=(f[x].l+f[x].r)>>;
if mid>=r
then plus:=plus+plus(x<<,l,r);
if mid<l
then plus:=plus+plus(x<<+,l,r);
if (mid>=l) and (mid<r)
then begin plus:=plus(x<<,l,r)+plus(x<<+,l,r) end;
end; procedure sq(x,l,r:longint);
var
mid:longint;
begin
if f[x].q=
then exit;
if (f[x].l=f[x].r) then
begin
f[x].s:=trunc(sqrt(f[x].s));
if (f[x].s=) or (f[x].s=)
then f[x].q:=;
exit;
end;
mid:=(f[x].l+f[x].r)>>;
if mid>=r
then sq(x<<,l,r);
if mid<l
then sq(x<<+,l,r);
if (mid>=l) and (mid<r)
then begin sq(x<<,l,r);sq(x<<+,l,r) end;
f[x].q:=f[x<<].q and f[x<<+].q;
f[x].s:=f[x<<].s+f[x<<+].s;
end; begin
read(n);
for i:= to n do
begin
read(a[i]);
end;
build(,,n);
read(m);
for i:= to m do
begin
read(k,x,y);
case k of
:writeln(plus(,x,y));
:sq(,x,y);
end;
end;
end.