LEM4 - WHITE BLACK

Tác giả: ladpro98

Ngôn ngữ: Pascal

program lem4;
uses    math;
type    e=record
                l,r,ans,sum:longint;
        end;
const   maxn=10004;
        fi='';
var     it:array[1..4*maxn] of e;
        lazy:array[1..4*maxn] of longint;
        n,m,i,x,y,p:longint;
        inp:text;
procedure update(k,l,r,i,j,v:longint);
var     m:longint;
begin
        if lazy[k]<>0 then
        begin
                if lazy[k]=1 then
                begin
                        it[k].sum:=r-l+1;
                        it[k].l:=it[k].sum;
                        it[k].r:=it[k].sum;
                        it[k].ans:=it[k].sum;
                end
                else
                begin
                        it[k].sum:=0;
                        it[k].l:=0;
                        it[k].r:=0;
                        it[k].ans:=0;
                end;
                if l<>r then
                begin
                        lazy[2*k]:=lazy[k];
                        lazy[2*k+1]:=lazy[k];
                end;
                lazy[k]:=0;
        end;
        if (l>r) or (r<i) or (j<l) then exit;
        if (i<=l) and (r<=j) then
        begin
                if v=1 then
                begin
                        it[k].sum:=r-l+1;
                        it[k].l:=it[k].sum;
                        it[k].r:=it[k].sum;
                        it[k].ans:=it[k].sum;
                end
                else
                begin
                        it[k].sum:=0;
                        it[k].l:=0;
                        it[k].r:=0;
                        it[k].ans:=0;
                end;
                if l<>r then
                begin
                        lazy[2*k]:=v;
                        lazy[2*k+1]:=v;
                end;
                exit;
        end;
        m:=(l+r) shr 1;
        update(2*k,l,m,i,j,v);
        update(2*k+1,m+1,r,i,j,v);
        it[k].sum:=it[2*k].sum+it[2*k+1].sum;
        if it[2*k].sum=(m-l+1) then
                it[k].l:=it[2*k].sum+it[2*k+1].l
        else    it[k].l:=it[2*k].l;
        if it[2*k+1].sum=r-m then
                it[k].r:=it[2*k+1].sum+it[2*k].r
        else    it[k].r:=it[2*k+1].r;
        it[k].ans:=max(max(it[2*k].ans,it[2*k+1].ans),it[2*k].r+it[2*k+1].l);
end;

function get(k,l,r,i,j:longint):e;
var     m:longint;
        t,p,q:e;
begin
        if (l>r) or (r<i) or (j<l) then exit;
        if lazy[k]<>0 then
        begin
                if lazy[k]=1 then
                begin
                        it[k].sum:=r-l+1;
                        it[k].l:=it[k].sum;
                        it[k].r:=it[k].sum;
                        it[k].ans:=it[k].sum;
                end
                else
                begin
                        it[k].sum:=0;
                        it[k].l:=0;
                        it[k].r:=0;
                        it[k].ans:=0;
                end;
                if l<>r then
                begin
                        lazy[2*k]:=lazy[k];
                        lazy[2*k+1]:=lazy[k];
                end;
                lazy[k]:=0;
        end;
        if (i<=l) and (r<=j) then exit(it[k]);
        m:=(l+r) shr 1;
        if m>=j then exit(get(2*k,l,m,i,j));
        if m<i then exit(get(2*k+1,m+1,r,i,j));
        p:=get(2*k,l,m,i,j);
        q:=get(2*k+1,m+1,r,i,j);
        t.sum:=p.sum+q.sum;
        if p.sum=(m-l+1) then
                t.l:=p.sum+q.l
        else    t.l:=p.l;
        if q.sum=(r-m) then
                t.r:=q.sum+p.r
        else    t.r:=q.r;
        t.ans:=max(max(p.ans,q.ans),p.r+q.l);
        exit(t);
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,n);readln(inp,m);
        update(1,1,n,1,n,1);
        for i:=1 to m do
        begin
                read(inp,p);
                if p=3 then writeln(get(1,1,n,1,n).ans)
                else
                begin
                        readln(inp,x,y);
                        update(1,1,n,x,y,p);
                end;
        end;
end.

Download