社区讨论

线段树为什么是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 条回复,欢迎继续交流。

正在加载回复...