社区讨论
线段树为什么是80?
P1198[JSOI2008] 最大数参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi4g6xbp
- 此快照首次捕获于
- 2025/11/18 18:45 4 个月前
- 此快照最后确认于
- 2025/11/18 18:45 4 个月前
CPP
type tree=record
l,r,lc,rc,ma:longint;
end;
const maxm=200001;
var i,j,n,m,d,x,y,tot,l,temp:longint;
s:string;
t:array[0..maxm*2] of tree;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure jian(x,y:longint);
var temp:longint;
begin
inc(tot);
temp:=tot;
t[temp].l:=x; t[temp].r:=y;
if x<>y then
begin
t[temp].lc:=tot+1; jian(x,(x+y) shr 1);
t[temp].rc:=tot+1; jian((x+y) shr 1+1,y);
end;
end;
procedure jia(k,x,y:longint);
begin
if (t[k].l=t[k].r) and (t[k].l=X) then
begin
t[k].ma:=y;
exit;
end;
if (x>=t[t[k].lc].l) and (x<=t[t[k].lc].r) then
begin
jia(t[k].lc,x,y);
t[k].ma:=max(t[t[k].rc].ma,t[t[k].lc].ma);
end;
if (x>=t[t[k].rc].l) and (x<=t[t[k].rc].r) then
begin
jia(t[k].rc,x,y);
t[k].ma:=max(t[t[k].rc].ma,t[t[k].lc].ma);
end;
end;
function maa(k,l,r:longint):longint;
var tt,temp:longint;
begin
temp:=0;
if (t[k].l>=l) and (t[k].r<=r) then exit(t[k].ma);
tt:=t[k].lc;
if not((t[tt].l>r) or (t[tt].r<l)) then temp:=max(temp,maa(tt,l,r));
tt:=t[k].rc;
if not((t[tt].l>r) or (t[tt].r<l)) then temp:=max(temp,maa(tt,l,r));
exit(temp);
end;
begin
readln(m,d);
jian(1,maxm);
for i:=1 to m do
begin
readln(s);
if s[1]='A' then
begin
delete(s,1,2);
val(s,n);
inc(x);
jia(1,x,(n+y) mod d);
end
else
begin
delete(s,1,2);
val(s,l);
temp:=maa(1,x-l+1,x);
y:=temp;
writeln(temp);
end;
end;
end.
求大神帮忙。
回复
共 1 条回复,欢迎继续交流。
正在加载回复...