jzoj4216. 【NOIP2015模拟9.12】平方和

Description

给出一个N个整数构成的序列,有M次操作,每次操作有一下三种:
①Insert Y X,在序列的第Y个数之前插入一个数X;
②Add L R X,对序列中第L个数到第R个数,每个数都加上X;
③Query L R,询问序列中第L个数到第R个数的平方和。

Input

第一行一个正整数N,表示初始序列长度。
第二行N个整数Ai,表示初始序列中的数。
第三行一个正整数M,表示操作数。
接下来M行,每行一种操作。

Output

对于每一个Query操作输出答案。由于答案可能很大,请mod 7459后输出。

Sample Input

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

Sample Output

14
38
304
样例解释:
第二次操作后的序列:1,5,2,3,4,5。
第四次操作后的序列:1,5,2,3,11,12。

Data Constraint

30%的数据满足N≤1,000,M≤1,000。
另外20%的数据满足N≤100,000,M≤100,000,且不存在Insert操作。
100%的数据满足N≤100,000,M≤100,000,且Add和Insert操作中|X|≤1000,|Ai|≤1000。
Source / Author: 常州高级中学 sum
想法:
在线splay维护,太弱了打不动
其实只不过是在对一棵线段树搞来搞去
离线做法:
(x+k)^2=x^2+2kx+k^2
还有一个区间修改的加法tag
insert操作?
维护一下每个区间有值的数的个数
构造一个最终序列
在维护个数的线段树上二分出每个树在线段树上的实际位置,
方便查询
打了1个多小时,调试了5个小时,目前为止搞起来最难的题
8000++
标程:
const
maxn=7459;
var
a,b:array[1..100000] of int64;
tree,add,tree1,tree2,ins:array[1..800000] 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];
add[x]:=0;
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;
add[x]:=0;
end;
end;
procedure change(x,head,tail,l,r:longint;y:int64);
var
mid,z:longint;
begin
if (l=head)and(r=tail) then
begin
if bz then
begin
tree1[x]:=y;
tree[x]:=y*y mod maxn;
exit;
end;
add[x]:=(add[x]+y)mod maxn;
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
mid:=(head+tail)div 2;
if (tree2[x+x]>0)then
begin
tree[x+x]:=((tree[x+x]+tree1[x+x]*2mod maxn*add[x] mod maxn)mod maxn+add[x] mod maxn*add[x] mod maxn*tree2[x+x] mod maxn)mod maxn;
tree1[x+x]:=(tree1[x+x]+add[x]*tree2[x+x]+maxn)mod maxn;
add[x+x]:=(add[x+x]+add[x]+maxn)mod maxn;
end;
if (tree2[x+x+1]>0) then
begin
tree[x+x+1]:=((tree[x+x+1]+tree1[x+1+x]*2mod maxn*add[x] mod maxn)mod maxn+add[x] mod maxn*add[x] mod maxn*tree2[x+x+1] mod maxn)mod maxn;
tree1[x+x+1]:=(tree1[x+x+1]+add[x]*tree2[1+x+x]+maxn)mod maxn;
add[x+x+1]:=(add[x+x+1]+add[x])mod maxn;
end;
add[x]:=0;
if r<=mid then change(x*2,head,mid,l,r,y) else
if l>mid then change(x*2+1,mid+1,tail,l,r,y) else
begin
change(x*2,head,mid,l,mid,y);
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;
procedure find(x,head,tail,l,r:longint);
var
mid:longint;
begin
if (head=l)and(tail=r)then
begin
ans:=ans+tree[x];
ans1:=ans1+tree1[x];
end
else
begin
mid:=(head+tail)div 2;
if (tree2[x+x]>0)then
begin
tree[x+x]:=((tree[x+x]+tree1[x+x]*2mod maxn*add[x] mod maxn)mod maxn+add[x] mod maxn*add[x] mod maxn*tree2[x+x] mod maxn)mod maxn;
tree1[x+x]:=(tree1[x+x]+add[x]*tree2[x+x]+maxn)mod maxn;
add[x+x]:=(add[x+x]+add[x]+maxn)mod maxn;
end;
if (tree2[x+x+1]>0) then
begin
tree[x+x+1]:=((tree[x+x+1]+tree1[x+1+x]*2mod maxn*add[x] mod maxn)mod maxn+add[x] mod maxn*add[x] mod maxn*tree2[x+x+1] mod maxn)mod maxn;
tree1[x+x+1]:=(tree1[x+x+1]+add[x]*tree2[1+x+x]+maxn)mod maxn;
add[x+x+1]:=(add[x+x+1]+add[x])mod maxn;
end;
add[x]:=0;
if r<=mid then find(x*2,head,mid,l,r)
else
begin
if l>mid then find(x*2+1,mid+1,tail,l,r)
else
begin
find(x*2,head,mid,l,mid);
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;

function ef(x,head,tail,wz:longint):longint;
var
mid:longint;
begin
if wz=0 then exit(wz);
if head=tail then exit(head);
mid:=(head+tail) div 2;
if tree2[x+x]>=wz then
begin
exit(ef(x*2,head,mid,wz));
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);
readln(n);
for i:=1 to n do read(a[i]);
n1:=n;
readln(m);
for i:=1 to m do
begin
readln(s[i]);
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.

相关文章

相关标签/搜索