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;
}

Download