## Editorial for WHITE BLACK

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

uses math;
const fi='';
maxn=10010;
var n,m,i,x,y,z:longint;
a,g,h,f:array[1..maxn shl 2] of longint;

procedure put(x,val:longint);
begin
f[x]:=val; g[x]:=val; h[x]:=val;
end;

var mid:longint;
begin
if (l=x) and (r=y) then
begin
a[node]:=z;
if z=1 then put(node,r-l+1)
else put(node,0);
end
else
begin
mid:=(l+r) shr 1;
if a[node]<>0 then
begin
a[node shl 1]:=a[node];
a[node shl 1+1]:=a[node];
put(node shl 1,(mid-l+1)*(2-a[node]));
put(node shl 1+1,(r-mid)*(2-a[node]));
a[node]:=0;
end;
if x<=mid then add(node shl 1,l,mid,x,min(y,mid),z);
if mid<y then add(node shl 1+1,mid+1,r,max(x,mid+1),y,z);
if g[node shl 1]=mid-l+1 then g[node]:=mid-l+1+g[node shl 1+1]
else g[node]:=g[node shl 1];
if h[node shl 1+1]=r-mid then h[node]:=h[node shl 1]+r-mid
else h[node]:=h[node shl 1+1];
f[node]:=max(f[node shl 1],f[node shl 1+1]);
f[node]:=max(f[node],h[node shl 1]+g[node shl 1+1]);
end;
end;

begin
assign(input,fi); reset(input);
for i:=1 to m do
begin
if z=3 then writeln(f[1])
else
begin
end;
end;
close(input);
end.


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);
update(1,1,n,1,n,1);
for i:=1 to m do
begin
if p=3 then writeln(get(1,1,n,1,n).ans)
else
begin
update(1,1,n,x,y,p);
end;
end;
end.


{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=10000; snode=262144; var m,n:longint; f1,f2:text; left,right,maxkq,color:array[1..snode] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure update(u,v,k:longint); procedure visit(i,l,r:longint); var mid:longint; begin if (v<l) or (r<u) then exit; if (u<=l) and (r<=v) then begin color[i]:=k; if k=1 then begin left[i]:=r-l+1; right[i]:=r-l+1; maxkq[i]:=r-l+1; end else begin left[i]:=0; right[i]:=0; maxkq[i]:=0; end; exit; end; mid:=(l+r) shr 1; if color[i]=1 then begin color[i shl 1]:=1; left[i shl 1]:=mid-l+1; right[i shl 1]:=mid-l+1; maxkq[i shl 1]:=mid-l+1; color[i shl 1+1]:=1; left[i shl 1+1]:=r-mid; right[i shl 1+1]:=r-mid; maxkq[i shl 1+1]:=r-mid; end else if color[i]=2 then begin color[i shl 1]:=2; left[i shl 1]:=0; right[i shl 1]:=0; maxkq[i shl 1]:=0; color[i shl 1+1]:=2; left[i shl 1+1]:=0; right[i shl 1+1]:=0; maxkq[i shl 1+1]:=0; end; color[i]:=0; visit(i shl 1,l,mid); visit(i shl 1+1,mid+1,r); left[i]:=left[i shl 1]; if color[i shl 1]=1 then left[i]:=left[i]+left[i shl 1+1]; right[i]:=right[i shl 1+1]; if color[i shl 1+1]=1 then right[i]:=right[i]+right[i shl 1]; maxkq[i]:=max(max(maxkq[i shl 1],maxkq[i shl 1+1]),right[i shl 1]+left[i shl 1+1]); if (color[i shl 1]=color[i shl 1+1]) then color[i]:=color[i shl 1]; end; begin visit(1,1,n); end; procedure ans; var i,k,u,v:longint; begin for i:=1 to m do begin read(f1,k); if k=3 then writeln(f2,maxkq[1]) else begin read(f1,u,v); update(u,v,k); end; end; end; begin openF; read(f1,n,m); color[1]:=1; left[1]:=n; right[1]:=n; maxkq[1]:=n; ans; closeF; end.  #### Code mẫu của hieult #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //#include<conio.h> #define ep 0.000001 #define maxn 10011 #define mod 1000000000 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define fi first #define se second double const PI=4*atan(1); double const oo = 1e19; using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; struct tree{ int maxleft, maxright, length; tree(){}; tree(int _ml, int _mr, int _l){ maxleft = _ml, maxright = _mr, length = _l; } }; tree empty = tree(0, 0, 0); int n, m, number, u, v; tree f[maxn * 4]; void update(int l, int r, int i, int so){ if(u > r || v < l) return; int t = (r - l + 1) * so; if(u <= l && v >= r){ f[i] = tree(t, t, t); return; } // if(f[i].length == t) return; int mid = (l + r) / 2; if(f[i].length == 0){ f[i + i] = empty; f[i + i + 1] = empty; } if(f[i].length == r - l + 1){ f[i + i] = tree(mid - l + 1, mid - l + 1, mid - l + 1); f[i + i + 1] = tree(r - mid, r - mid, r - mid); } update(l, mid, i + i, so); update(mid + 1, r, i + i + 1, so); f[i].length = max(f[i + i].length, max(f[i + i + 1].length, f[i + i].maxright + f[i + i + 1].maxleft)); if(f[i + i].maxleft == mid - l + 1) f[i].maxleft = f[i + i + 1].maxleft + mid - l + 1; else f[i].maxleft = f[i + i].maxleft; if(f[i + i + 1].maxright == r - mid) f[i].maxright = f[i + i].maxright + r - mid; else f[i].maxright = f[i + i + 1].maxright; } int main(){ //freopen("input.in","r",stdin); //freopen("output.out","w",stdout); scanf("%d %d",&n,&m); for(int i = 1; i <= n; i++) { u = 1, v = i; update(1, n, 1, 1); } //printf("%d.......\n",f[1].length); for(int i = 0; i < m; i++){ scanf("%d",&number); if(number == 3) printf("%d\n",f[1].length); else{ scanf("%d %d",&u,&v); number = 2 - number; update(1, n, 1, number); } } // getch(); }  #### Code mẫu của ll931110 {$MODE DELPHI}
Program LEM4_2;
Uses math;
Const
input  = '';
output = '';
maxn = 10000;
maxv = 20000;
Type
rec = record
left,right,val,sign: integer;
end;
Var
fi,fo: text;
n,m,q,u,v: integer;
a: array[1..8 * maxn] of rec;
k: array[-1..1] of integer;

Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);

Assign(fo, output);
Rewrite(fo);
End;

Procedure setval(i,low,high: integer);
Var
t: integer;
Begin
t:= a[i].sign;
a[i].val:= (high - low + 1) * t * k[t];
a[i].left:= a[i].val;
a[i].right:= a[i].val;
End;

Procedure update(i,low,high: integer);
Var
mid: integer;
Begin
If (v < low) or (high < u) then exit;
If (u <= low) and (high <= v) then
Begin
If q = 1 then a[i].sign:= 1 else a[i].sign:= -1;
setval(i,low,high);
exit;
End;

mid:= (low + high) div 2;
If a[i].sign <> 0 then
Begin
a[2 * i].sign:= a[i].sign;
a[2 * i + 1].sign:= a[i].sign;
a[i].sign:= 0;

setval(2 * i,low,mid);
setval(2 * i + 1,mid + 1,high);
End;

update(2 * i,low,mid);
update(2 * i + 1,mid + 1,high);

a[i].left:= a[2 * i].left;
If (a[2 * i].left = mid - low + 1)
and (a[2 * i + 1].left > 0) then a[i].left:= a[2 * i].left + a[2 * i + 1].left;

a[i].right:= a[2 * i + 1].right;
If (a[2 * i + 1].right = high - mid)
and (a[2 * i].right > 0) then a[i].right:= a[2 * i + 1].right + a[2 * i].right;

a[i].val:= max(a[2 * i].val,a[2 * i + 1].val);
If a[i].val < a[2 * i].right + a[2 * i + 1].left
then a[i].val:= a[2 * i].right + a[2 * i + 1].left;
End;

Procedure solve;
Var
i,t: integer;
Begin
k[-1]:= maxv;
k[1]:= 1;

q:= 1;
u:= 1;
v:= n;
update(1,1,n);

For i:= 1 to m do
Begin

If q = 3 then
Begin
t:= a[1].val;
If t < 0 then writeln(fo, 0) else writeln(fo, t);
End
else
Begin
update(1,1,n);
End;
End;
End;

Procedure closefile;
Begin
Close(fo);
Close(fi);
End;

Begin
openfile;
solve;
closefile;
End.


#### Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
class SegmentTree {
private:
struct Node {
int len,left,right,range;
Node() {
len=left=right=range=0;
}
Node(int col,int len) {
this->len=len;
left=right=range=col==1?len:0;
}
bool fullSeg(void) const {
return (left==len && right==len);
}
Node operator + (const Node &x) const {
Node res;
res.len=len+x.len;
res.left=fullSeg()?left+x.left:left;
res.right=x.fullSeg()?right+x.right:x.right;
res.range=max(max(range,x.range),right+x.left);
return (res);
}
};
vector<Node> tree;
vector<int> lazy;
int n;
void pushdown(int i,int l,int r) {
if (lazy[i]<0) return;
int m=(l+r)>>1;
lazy[2*i]=lazy[2*i+1]=lazy[i];
tree[2*i]=Node(lazy[i],m-l+1);
tree[2*i+1]=Node(lazy[i],r-m);
lazy[i]=-1;
}
void update(int i,int l,int r,int u,int v,int c) {
if (l>v || r<u || l>r || v<u) return;
if (u<=l && r<=v) {
tree[i]=Node(c,r-l+1);
lazy[i]=c;
return;
}
pushdown(i,l,r);
int m=(l+r)>>1;
update(2*i,l,m,u,v,c);
update(2*i+1,m+1,r,u,v,c);
tree[i]=tree[2*i]+tree[2*i+1];
}
public:
SegmentTree() {
n=0;
}
SegmentTree(int n) {
this->n=n;
tree.assign(4*n+7,Node());
lazy.assign(4*n+7,-1);
update(1,1,n,1,n,1);
}
void update(int l,int r,int c) {
update(1,1,n,l,r,c);
}
int maxSeg(void) const {
return (tree[1].range);
}
};
int n,q;
void process(void) {
scanf("%d%d",&n,&q);
SegmentTree myit(n);
REP(zz,q) {
int t,l,r;
scanf("%d",&t);
if (t==3) printf("%d\n",myit.maxSeg());
else {
scanf("%d%d",&l,&r);
myit.update(l,r,t==1);
}
}
}
int main(void) {
process();
return 0;
}


#### Code mẫu của khuc_tuan

#include <iostream>

using namespace std;

#define maxn 10010

int N, Q;
int C[maxn * 4], L[maxn * 4], R[maxn * 4], M[maxn * 4];

void init( int node, int left, int right) {
L[node] = R[node] = M[node] = right - left + 1;
C[node] = 0;
if(left<right) {
int m = (left+right)/2;
init( node*2, left, m);
init( node*2+1,m+1,right);
}
}

void fill( int node, int left, int right, int x, int y, int color, int temp) {
if(x<=left && right<=y) {
C[node] = color;
L[node] = R[node] = M[node] = (color==0) ? (right - left + 1) : 0;
return;
}
if(temp==-1 && C[node]!=-1) temp = C[node];
int mid = (left+right)/2;

C[node] = -1;

if(x<=mid) fill( 2*node, left, mid, x, y, color, temp);
else if(temp!=-1) fill( 2*node, left, mid, left, mid, temp, temp);

if(mid<y) fill( 2*node+1, mid+1, right, x, y, color, temp);
else if(temp!=-1) fill( 2*node+1, mid+1, right, mid+1, right, temp, temp);

M[node] = max( max( M[2*node], M[2*node+1]), R[2*node] + L[2*node+1]);

if(L[2*node]==mid-left+1) L[node] = L[2*node] + L[2*node+1];
else L[node] = L[2*node];

if(R[2*node+1]==right-mid) R[node] = R[2*node+1] + R[2*node];
else R[node] = R[2*node+1];

}

int main() {
scanf("%d%d", &N, &Q);
init( 1, 1, N);
for(int i=0;i<Q;++i) {
int code, a, b;
scanf("%d", &code);
if(code==3) printf("%d\n", max( L[1], max( M[1], R[1])));
else {
scanf("%d%d", &a, &b);
fill( 1, 1, N, a, b, code-1, -1);
}
}
return 0;
}