LEM4 - WHITE BLACK
Tác giả: khuc_tuan
Ngôn ngữ: C++
#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;
}