- UID
- 83828
- 在线时间
- 0 小时
- 最后登录
- 2016-9-11
- 注册时间
- 2012-3-24
- 宅魂
- 223 点
- 贡献
- 7 点
- 宅币
- 2259 枚
- 宅の石(入宅度)
- 0 块
- 元气(技能点)
- 5 点
- 活跃
- 0 ℃
- 听众
- 3
- 收听
- 0
该用户从未签到
序章
- 积分
- 3199
|
发表于 2012-8-9 18:31:42
|
显示全部楼层
OIer一名 目前pascal党。。正在转C++ 这是我写的线段树程序。。(总之比较好的东西。。。求技能点!!)
var
a,b,p,t,i,j,m,n,q:longint;
g,f,flag:array[0..1000000]of int64;
total:int64;
c:char;
procedure ask(p,l,r,a,b:longint);
var mid:longint;
begin
if (a<=l)and(b>=r)then
begin
inc(total,f[p]+flag[p]*(r-l+1));
exit;
end;
if flag[p]<>0 then
begin
inc(f[p],flag[p]*(r-l+1));
inc(flag[p shl 1],flag[p]);
inc(flag[(p shl 1)or 1],flag[p]);
flag[p]:=0;
end;
mid:=(l+r)shr 1;
if a<=mid then
ask(p shl 1,l,mid,a,b);
if b>mid then
ask((p shl 1)+1,mid+1,r,a,b);
end;
procedure add(p,l,r,a,b,m:longint);
var mid:longint;
function ttt:longint;
var t,q,w,e:longint;
begin
if (a>=l)and(b<=r)then
begin
ttt:=b-a+1;
exit;
end;
if (a<l)then
begin
ttt:=b-l+1;
exit;
end;
ttt:=r-a+1;
end;
begin
if (a<=l)and(b>=r)then
begin
inc(flag[p],m);
exit;
end;
if flag[p]<>0 then
begin
inc(f[p],(r-l+1)*flag[p]);
inc(flag[p shl 1],flag[p]);
inc(flag[(p shl 1)or 1],flag[p]);
flag[p]:=0;
end;
mid:=(l+r)shr 1;
inc(f[p],m*ttt);
if a<=mid then
add(p shl 1,l,mid,a,b,m);
if b>mid then
add((p shl 1)or 1,mid+1,r,a,b,m);
end;
procedure build(p,l,r:longint);
var mid:longint;
begin
if l=r then
begin
f[p]:=g[l];
exit;
end;
mid:=(l+r)shr 1;
build(p shl 1,l,mid);
build((p shl 1)or 1,mid+1,r);
f[p]:=f[p shl 1]+f[(p shl 1)or 1];
end;
begin
assign(input,'a.in');reset(input);
assign(output,'a.out');rewrite(output);
readln(n,q);
for i:=1 to n-1 do
read(g[i]);
readln(g[n]);
build(1,1,n);
for i:=1 to q do
begin
read(c);
if c='Q' then
begin
readln(a,b);
total:=0;
ask(1,1,n,a,b);
writeln(total);
end;
if c='C' then
begin
readln(a,b,m);
add(1,1,n,a,b,m);
end;
end;
close(input);
close(output);
end.
|
评分
-
查看全部评分
|