记录编号	26250	评测结果	A
题目名称	儿童节快乐	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.000 s
提交时间	2011-07-23 13:37:16	内存使用	9.70 MiB

var
max,v,l,r,mm:array[0..500000]of longint;
n,m,i,t,a,b,x,d,c:longint;
cc:char;

function dell(a,b,x:longint):longint;
var
am,bm:longint;
begin
    if (a<=l[x]) and (r[x]<=b) then begin
        dell:=mm[x];
    end
    else begin
        am:=-1;bm:=-1;
        m:=(l[x]+r[x]) div 2;
        if a<=m then am:=dell(a,b,x*2);
        if b>m then bm:=dell(a,b,x*2+1);
        if am>=bm then begin
            dell:=am+v[x];
        end
        else begin
            dell:=bm+v[x];
        end;
    end;
end;

procedure ddd(a,b,x:longint);
var
am,bm:longint;
begin
    if l[x]=r[x] then begin
        v[x]:=0;mm[x]:=0;
    end
    else begin
        am:=-1;bm:=-1;
        m:=(l[x]+r[x]) div 2;
        if a<=m then am:=dell(a,b,x*2);
        if b>m then bm:=dell(a,b,x*2+1);
        inc(v[x*2+1],v[x]);
        inc(mm[x*2+1],v[x]);
        inc(v[x*2],v[x]);
        inc(mm[x*2],v[x]);
        v[x]:=0;
        if am>=bm then begin
            ddd(a,b,x*2);
        end
        else begin
            ddd(a,b,x*2+1);

        end;
        if mm[x*2+1]>mm[x*2] then begin
            max[x]:=max[x*2+1];
            mm[x]:=mm[x*2+1]+v[x];
        end
        else begin
            max[x]:=max[x*2];
            mm[x]:=mm[x*2]+v[x];
        end;
    end;
end;

function del(a,b,x:longint):longint;
var
am,bm:longint;
begin
    if (a<=l[x]) and (r[x]<=b) then begin
        del:=mm[x];
        if x=1 then begin
            ddd(a,b,1);
            if mm[x*2+1]>mm[x*2] then begin
                max[x]:=max[x*2+1];
                mm[x]:=mm[x*2+1]+v[x];
            end
            else begin
                max[x]:=max[x*2];
                mm[x]:=mm[x*2]+v[x];
            end;
        end;
    end
    else begin
        am:=-1;bm:=-1;
        m:=(l[x]+r[x]) div 2;
        if a<=m then am:=del(a,b,x*2);
        if b>m then bm:=del(a,b,x*2+1);
        if am>=bm then begin
            del:=am+v[x];
            if x=1 then begin
                ddd(a,b,2);
                if mm[x*2+1]>mm[x*2] then begin
                    max[x]:=max[x*2+1];
                    mm[x]:=mm[x*2+1]+v[x];
                end
                else begin
                    max[x]:=max[x*2];
                    mm[x]:=mm[x*2]+v[x];
                end;
            end;
        end
        else begin
            del:=bm+v[x];
            if x=1 then begin
                ddd(a,b,3);
                if mm[x*2+1]>mm[x*2] then begin
                    max[x]:=max[x*2+1];
                    mm[x]:=mm[x*2+1]+v[x];
                end
                else begin
                    max[x]:=max[x*2];
                    mm[x]:=mm[x*2]+v[x];
                end;
            end;
        end;
    end;
end;

procedure newadd(x:longint);
var
m:longint;
begin
    if l[x]<>r[x] then begin
        m:=(l[x]+r[x]) div 2;
        l[x*2]:=l[x];r[x*2]:=m;
        l[x*2+1]:=m+1;r[x*2+1]:=r[x];
        newadd(x*2);newadd(x*2+1);
        max[x]:=max[x*2];
    end
    else
        max[x]:=x;
end;

procedure add(a,b,c,x:longint);
var
m:longint;
begin
    if (a<=l[x])and(r[x]<=b) then begin
        inc(v[x],c);
        inc(mm[x],c);
    end
    else begin
        m:=(l[x]+r[x]) div 2;
        if a<=m then add(a,b,c,x*2);
        if b>m then add(a,b,c,x*2+1);
        if mm[x*2+1]>mm[x*2] then begin
            max[x]:=max[x*2+1];
            mm[x]:=mm[x*2+1]+v[x];
        end
        else begin
            max[x]:=max[x*2];
            mm[x]:=mm[x*2]+v[x];
        end;
    end;
end;

begin
assign(input,'happya.in');reset(input);
assign(output,'happya.out');rewrite(output);
    readln(n,m);
    x:=1;
    while x<n do begin
        x:=x*2;inc(d);
    end;
    l[1]:=1;r[1]:=x;
    newadd(1);
    for i:=1 to m do begin
        read(cc);
        if cc='I' then begin
            readln(a,b,c);
            add(a,b,c,1);
        end
        else begin
            readln(a,b);
            writeln(del(a,b,1));
        end;
    end;
close(input);close(output);
end.