# jzoj4216. 【NOIP2015模拟9.12】平方和

Description

①Insert Y X，在序列的第Y个数之前插入一个数X；
③Query L R，询问序列中第L个数到第R个数的平方和。

Input

Output

Sample Input

5
1 2 3 4 5
5
Query 1 3
Insert 2 5
Query 2 4
Query 1 6

Sample Output

14
38
304

Data Constraint

30%的数据满足N≤1,000，M≤1,000。

Source / Author: 常州高级中学 sum

(x+k)^2=x^2+2kx+k^2

insert操作？

8000++

const
maxn=7459;
var
a,b:array[1..100000] of int64;
s:array[1..100000] of string;
wz,c,k,k1,i,n,m,n1:longint;
x,y,ans,z,ans1:int64;
s1,s2,s3,s4,s5:string;
bz:boolean;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
procedure maketree(x,l,r:longint);
var
mid:longint;
begin
if l=r then
begin
tree[x]:=b[l]*b[l];
tree1[x]:=b[l];
end
else
begin
mid:=(l+r)shr 1;
maketree(2*x,l,mid);
maketree(2*x+1,mid+1,r);
tree[x]:=(tree[2*x]+tree[2*x+1])mod maxn;
tree1[x]:=(tree1[2*x]+tree1[2*x+1])mod maxn;
end;
end;
var
mid,z:longint;
begin
begin
if bz then
begin
tree1[x]:=y;
tree[x]:=y*y mod maxn;
exit;
end;
tree[x]:=((tree[x]+tree1[x]*2mod maxn*y mod maxn)mod maxn+y mod maxn*y mod maxn*tree2[x] mod maxn)mod maxn;
tree1[x]:=(tree1[x]+y*tree2[x]+maxn)mod maxn;
end
else
begin
if (tree2[x+x]>0)then
begin
end;
if (tree2[x+x+1]>0) then
begin
end;
if l>mid then change(x*2+1,mid+1,tail,l,r,y) else
begin
change(x*2+1,mid+1,tail,mid+1,r,y);
end;
tree[x]:=tree[x*2]+tree[x*2+1];
tree[x]:=tree[x]mod maxn;
tree1[x]:=tree1[x*2]+tree1[x*2+1];
tree1[x]:=tree1[x]mod maxn;
end;
end;
var
mid:longint;
begin
begin
ans:=ans+tree[x];
ans1:=ans1+tree1[x];
end
else
begin
if (tree2[x+x]>0)then
begin
end;
if (tree2[x+x+1]>0) then
begin
end;
else
begin
if l>mid then find(x*2+1,mid+1,tail,l,r)
else
begin
find(x*2+1,mid+1,tail,mid+1,r);
end;
end;
end;
end;
procedure maketree1(x,l,r:longint);
var
mid:longint;
begin
if l=r then
begin
tree2[x]:=1;
end
else
begin
mid:=(l+r)shr 1;
maketree1(2*x,l,mid);
maketree1(2*x+1,mid+1,r);
tree2[x]:=(tree2[2*x]+tree2[2*x+1]);
end;
end;
procedure change1(x,l,r,wz,y:longint);
var
mid:longint;
begin
if l=r then tree2[x]:=tree2[x]+y
else
begin
mid:=(l+r)div 2;
if (wz<=mid) then change1(x*2,l,mid,wz,y)
else change1(x*2+1,mid+1,r,wz,y);
tree2[x]:=tree2[x]+y;
end;
end;

var
mid:longint;
begin
if wz=0 then exit(wz);
if tree2[x+x]>=wz then
begin
end
else
begin
exit(ef(x*2+1,mid+1,tail,wz-tree2[x+x]));
end;
end;
begin
//assign(input,’a.in’);reset(input);
//assign(output,’a.out’);rewrite(output);
for i:=1 to n do read(a[i]);
n1:=n;
for i:=1 to m do
begin
if s[i][1]=’I’ then inc(n);
end;
for i:=1 to n do
change1(1,1,n,i,1);
for i:=m downto 1 do
begin
if s[i][1]=’I’ then
begin
wz:=pos(’ ‘,s[i]);
s1:=copy(s[i],wz+1,length(s[i])-wz);
wz:=pos(’ ‘,s1);
s2:=copy(s1,1,wz-1);
s3:=copy(s1,wz+1,length(s1)-wz);
val(s2,x);
val(s3,y);
ins[i]:=ef(1,1,n,x);
change1(1,1,n,ins[i],-1);
end;
end;
fillchar(b,sizeof(b),0);
for i:=1 to n1 do
begin
k:=ef(1,1,n,i);
change(1,1,n,k,k,a[i]);
end;
for i:=1 to m do
begin
case s[i][1] of
‘A’:begin
wz:=pos(’ ‘,s[i]);
s1:=copy(s[i],wz+1,length(s[i])-wz);
wz:=pos(’ ‘,s1);
s2:=copy(s1,1,wz-1);
s3:=copy(s1,wz+1,length(s1)-wz);
val(s2,x);
wz:=pos(’ ‘,s3);
s4:=copy(s3,1,wz-1);
s5:=copy(s3,wz+1,length(s3)-wz);
val(s4,y);
val(s5,z);
k:=ef(1,1,n,x);
k1:=ef(1,1,n,y);
change(1,1,n,k,k1,z);
end;
‘I’:begin
wz:=pos(’ ‘,s[i]);
s1:=copy(s[i],wz+1,length(s[i])-wz);
wz:=pos(’ ‘,s1);
s2:=copy(s1,1,wz-1);
s3:=copy(s1,wz+1,length(s1)-wz);
val(s2,x);
val(s3,y);
change1(1,1,n,ins[i],1);
bz:=true;
change(1,1,n,ins[i],ins[i],y);
bz:=false;
end;
‘Q’:begin
wz:=pos(’ ‘,s[i]);
s1:=copy(s[i],wz+1,length(s[i])-wz);
wz:=pos(’ ‘,s1);
s2:=copy(s1,1,wz-1);
s3:=copy(s1,wz+1,length(s1)-wz);
val(s2,x);
val(s3,y);
ans:=0;
k:=ef(1,1,n,x);
k1:=ef(1,1,n,y);
find(1,1,n,k,k1);
ans:=(ans+maxn) mod maxn;
writeln(ans);

```end;
end;
end;```

end.