[jzoj]4216.【NOIP2015模拟9.12】平方和
2024-10-09 14:45:07
Link
https://jzoj.net/senior/#main/show/4216
Description
给出一个N个整数构成的序列，有M次操作，每次操作有一下三种：
①Insert Y X，在序列的第Y个数之前插入一个数X；
②Add L R X，对序列中第L个数到第R个数，每个数都加上X；
③Query L R，询问序列中第L个数到第R个数的平方和。
Solution
我不会告诉你这道题我打了10000+byte，并且改了2个月，50多个小时，删掉代码重打了5次。这道题用splay来弄是十分简单的一道裸体。但是我这种渣渣只能用可行的线段树。别人一次能打对，我仍要检查许多线段树的细节，并且打了N多个操作。可能是我代码风格不好吧。但为了方便检查也只好这样了。
30分
显然，暴力去做，可以拿到拿烂的部分分。
50分
在30分的基础上，数据增大， 但是没有Insert的操作，所以是线段树裸题。
100分
大佬肯定是一眼切。这是道Splay练手题目，可以看看gmh大神的题解，异常详细。请允许我打个广告。http://blog.csdn.net/gmh77
Splay以后我会推进并且更改这个博文。现在我只会线段树。
对于前两个操作，显然就是线段树裸题，毋庸置疑的。
但是，因为有了Insert操作，导致我们线段树的下标代表的数不一样。既然在线不可以，离线总是可以的。
①线段树1（前缀和）维护位置
在原本序列的第i个数和i-1个数之间（包括i），插入了多少个数。
最终用线段树1维护了出来之后，我们很容易的知道了原本序列的数他在最终序列的位置。这是值得你思考的地方
②线段树2维护最终序列
我们知道了原本序列每一个数在最终序列对应的位置，那么理所当然地可以再种一棵线段树2来维护插入的数的最终位置。
一开始把原序列的数，在最终序列对应位置，标记在线段树那个位置上，0表示当前位置不选，反之。这样一个前缀和就知道最终序列第i个位置之前（包括i）一共出现了多少个数。
那么每次插入一个数，我们二分出一个i，满足i最小，设1~i前缀和为sum。则满足sum=插入在哪个位置之前-1。这个位置，便是你当前插入的数在最终序列的位置。愉快地记录下来。
前缀和用线段树2维护。
这里二分也可以使用线段树二分，*度哗啦啦一大堆。
如果正着做必然会错。倒着做才是对的。这是你值得思考的。
③线段树3,4,5维护最终序列
我们可以用正常线段树来做了，因为我们可以通过最终位置来确定其对应的线段树下标。
但是平方和又是一个棘手的问题。
分解一下。
(a+b)²=a²+b²+2ab。
显然，每次加一个数，b就是这个加的数。
a²为原本的平方和，故用线段树3来维护他。
2ab，其中如果有多个a，那么就是2b(a1+a2+a3.....+an)，那么维护线段树4维护a的和即可。
还有b²，显然b是已知的，b²直接算即可。但是可能有多个a，那么维护个数即可。
为什么维护个数？因为有的位置预留了出来但是并没有插入一个数。
所以就是当前平方和=2*和*加的数+加的数的平方*个数
和在维护平方和之后再更新。
细节很多，需要处理，二分有两种，一种是靠右边，一种是靠左边。需要谨慎使用。
不知道哪里错了最好对拍一下，说不定你就知道了。反正我拍了1天
Code
var
ch:char;
i,j:longint;
n,m,ll,rr,now,len,lll,rrr,midd,lenn:int64;
p,b,r:array[..] of int64;
a:array[..,..] of int64;
num,add:array[..] of int64;
tree:array[..,..] of int64;
procedure build1(root,l,r:longint);
var
mid:longint;
begin
num[root]:=r-l+;
if l=r then
exit; mid:=(l+r) shr ;
build1(root*,l,mid);
build1(root*+,mid+,r); num[root]:=num[root*]+num[root*+];
end; procedure change1(root,l,r:longint);
var
mid:longint;
begin
if (l=r) and (l=ll) then
begin
inc(num[root]);
exit;
end; mid:=(l+r) shr ; if ll<=mid then
change1(root*,l,mid)
else
change1(root*+,mid+,r); num[root]:=num[root*]+num[root*+];
end; procedure find1(root,l,r,x,y:longint);
var
mid:longint;
begin
if (l=x)and(r=y) then
begin
now:=now+num[root]; exit;
end; mid:=(l+r) shr ;
if y<=mid then
find1(root*,l,mid,x,y)
else
if x>mid then
find1(root*+,mid+,r,x,y)
else
begin
find1(root*,l,mid,x,mid);
find1(root*+,mid+,r,mid+,y);
end; num[root]:=num[root*]+num[root*+];
end; procedure build2(root,l,r:longint);
var
mid:longint;
begin
num[root]:=r-l+;
if l=r then
exit; mid:=(l+r) shr ;
build2(root*,l,mid);
build2(root*+,mid+,r); num[root]:=num[root*]+num[root*+];
end; procedure change2(root,l,r:longint);
var
mid:longint;
begin
if (l=r) and (l=ll) then
begin
dec(num[root]);
exit;
end; mid:=(l+r) shr ;
if ll<=mid then
change2(root*,l,mid)
else
change2(root*+,mid+,r); num[root]:=num[root*]+num[root*+];
end; procedure find2(root,l,r,x,y:longint);
var
mid:longint;
begin
if (l=x)and(r=y) then
begin
now:=now+num[root]; exit;
end; mid:=(l+r) shr ;
if y<=mid then
find2(root*,l,mid,x,y)
else
if x>mid then
find2(root*+,mid+,r,x,y)
else
begin
find2(root*,l,mid,x,mid);
find2(root*+,mid+,r,mid+,y);
end; num[root]:=num[root*]+num[root*+];
end; procedure change_ttt(root,l,r,ttt:longint);
var
mid:longint;
begin
if (l=r) and (l=ttt) then
begin
tree[root,]:=p[ttt];
tree[root,]:=p[ttt]*p[ttt];
tree[root,]:=; exit;
end; if tree[root*,]> then
begin
tree[root*,]:=tree[root*,]+tree[root*,]*add[root]*+sqr(add[root])*tree[root*,];
tree[root*,]:=tree[root*,]+add[root]*tree[root*,];
add[root*]:=add[root*]+add[root];
end; if tree[root*+,]> then
begin
tree[root*+,]:=tree[root*+,]+tree[root*+,]*add[root]*+sqr(add[root])*tree[root*+,];
tree[root*+,]:=tree[root*+,]+add[root]*tree[root*+,];
add[root*+]:=add[root*+]+add[root];
end; add[root]:=; mid:=(l+r) shr ;
if ttt<=mid then
change_ttt(root*,l,mid,ttt)
else
change_ttt(root*+,mid+,r,ttt); tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
end;
procedure find_tot(root,l,r,x,y:longint);
var
mid:longint;
begin
if (l=x)and(r=y) then
begin
now:=now+tree[root,]; exit;
end; if tree[root*,]> then
begin
tree[root*,]:=tree[root*,]+tree[root*,]*add[root]*+sqr(add[root])*tree[root*,];
tree[root*,]:=tree[root*,]+add[root]*tree[root*,];
add[root*]:=add[root*]+add[root];
end; if tree[root*+,]> then
begin
tree[root*+,]:=tree[root*+,]+tree[root*+,]*add[root]*+sqr(add[root])*tree[root*+,];
tree[root*+,]:=tree[root*+,]+add[root]*tree[root*+,];
add[root*+]:=add[root*+]+add[root];
end; add[root]:=; mid:=(l+r) shr ;
if y<=mid then
find_tot(root*,l,mid,x,y)
else
if x>mid then
find_tot(root*+,mid+,r,x,y)
else
begin
find_tot(root*,l,mid,x,mid);
find_tot(root*+,mid+,r,mid+,y);
end; tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
end; procedure change(root,l,r,x,y:longint);
var
mid:longint;
begin
if (l=x)and(r=y) then
begin
add[root]:=add[root]+a[i,];
tree[root,]:=tree[root,]+tree[root,]*a[i,]*+sqr(a[i,])*tree[root,];
tree[root,]:=tree[root,]+a[i,]*tree[root,];
exit;
end; if tree[root*,]> then
begin
tree[root*,]:=tree[root*,]+tree[root*,]*add[root]*+sqr(add[root])*tree[root*,];
tree[root*,]:=tree[root*,]+add[root]*tree[root*,];
add[root*]:=add[root*]+add[root];
end; if tree[root*+,]> then
begin
tree[root*+,]:=tree[root*+,]+tree[root*+,]*add[root]*+sqr(add[root])*tree[root*+,];
tree[root*+,]:=tree[root*+,]+add[root]*tree[root*+,];
add[root*+]:=add[root*+]+add[root];
end; add[root]:=; mid:=(l+r)div ;
if y<=mid then
change(root*,l,mid,x,y)
else
if x>mid then
change(root*+,mid+,r,x,y)
else
begin
change(root*,l,mid,x,mid);
change(root*+,mid+,r,mid+,y);
end; tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
end; procedure find(root,l,r,x,y:longint);
var
mid:longint;
begin
if (l=x)and(r=y) then
begin
now:=now+tree[root,]; exit;
end; if tree[root*,]> then
begin
tree[root*,]:=tree[root*,]+tree[root*,]*add[root]*+sqr(add[root])*tree[root*,];
tree[root*,]:=tree[root*,]+add[root]*tree[root*,];
add[root*]:=add[root*]+add[root];
end; if tree[root*+,]> then
begin
tree[root*+,]:=tree[root*+,]+tree[root*+,]*add[root]*+sqr(add[root])*tree[root*+,];
tree[root*+,]:=tree[root*+,]+add[root]*tree[root*+,];
add[root*+]:=add[root*+]+add[root];
end; add[root]:=; mid:=(l+r) shr ;
if y<=mid then
find(root*,l,mid,x,y)
else
if x>mid then
find(root*+,mid+,r,x,y)
else
begin
find(root*,l,mid,x,mid);
find(root*+,mid+,r,mid+,y);
end; tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
tree[root,]:=tree[root*,]+tree[root*+,];
end; function erfen(ppp:longint):longint;
var
ll,rr,midd:longint;
begin
ll:=;
rr:=len;
while ll<rr do
begin
midd:=(ll+rr) shr ; now:=;
find_tot(,,len,,midd); if now>=ppp then
rr:=midd
else
ll:=midd+;
end; exit(ll);
end; begin
readln(n);
for i:= to n do
read(b[i]); len:=n; readln(m); build1(,,n); for i:= to m do
begin
read(ch);
if ch='I' then
begin
while ch<>' ' do
read(ch);
a[i,]:=; readln(a[i,],a[i,]);
ll:=;
rr:=n;
while ll<rr do
begin
midd:=(ll+rr) shr ; now:=;
find1(,,n,,midd);
if now>=a[i,] then
rr:=midd
else
ll:=midd+;
end; change1(,,n); inc(len);
end
else
if ch='A' then
begin
while ch<>' ' do
read(ch); a[i,]:=; readln(a[i,],a[i,],a[i,]);
end
else
begin
while ch<>' ' do
read(ch); a[i,]:=; readln(a[i,],a[i,]);
end;
end; fillchar(num,sizeof(num),); for i:= to len do
p[i]:=maxlongint; build2(,,len); lenn:=len-n; for i:=m downto do
if a[i,]= then
begin
ll:=;
rr:=len;
while ll<rr do
begin
midd:=(ll+rr) shr ; now:=;
find2(,,len,,midd);
if now<a[i,] then
ll:=midd+
else
rr:=midd;
end; r[lenn]:=ll;
p[ll]:=a[i,];
change2(,,len); dec(lenn);
end; lenn:=;
for i:= to len do
if p[i]=maxlongint then
begin
inc(lenn);
p[i]:=b[lenn];
change_ttt(,,len,i);
end; lenn:=;
for i:= to m do
begin
if a[i,]= then
begin
inc(lenn);
change_ttt(,,len,r[lenn]);
end
else
if a[i,]= then
begin
lll:=erfen(a[i,]);
rrr:=erfen(a[i,]); change(,,len,lll,rrr);
end
else
begin
lll:=erfen(a[i,]);
rrr:=erfen(a[i,]); now:=;
find(,,len,lll,rrr); writeln(now mod );
end;
end;
end.
最新文章
- python获取路径
- Ubuntu每次启动都显示System program problem detected的解决办法
- input value的值不可改变
- Apache MINA 框架之默认session管理类实现
- C#之异步编程
- mybatis系列笔记(1)---mybatis入门
- C#语法——await与async的正确打开方式
- iOS -- Effective Objective-C 阅读笔记 (7)
- 【Docker】-NO.132.Docker.1 -【Docker 修改容器端口】
- Android为TV端助力 转载：内存泄露与内存溢出的区别
- Laravel Eloquent ORM 时如何查询表中指定的字段
- HighCharts-动态配置csv格式数据
- python去掉字符串'\xa0'
- php代码执行顺序
- 使用工厂方法配置bean的两种方式
- 集合之LinkedList
- linux普通用户获取管理员权限
- Codeforces Round #402 (Div. 2) A,B,C,D,E
- log4j 日志配置和jar包下载
- 20155117王震宇 2016-2017-2 《Java程序设计》第八周学习总结