문제

A binary array is an array which each element can be either 0 or 1. Aleka has a binary array B or length N. The elements of B are indexed from 1 to N.

Aleka will play with her array. She will run Q queries one after another. Each query can be one of the following type :

  • FLIP L R: Flip all bits of B from index L to R, inclusive. Flipping bit is changing the value of a bit from 0 to 1, or from 1 to 0.
  • COMBO L R: Let B' be the subarray of B only containing bits which indexed between L to R, inclusive. Find the length of the longest contiguous subarray of B' such that all elements in that subarray have the same value.

All the queries should be executed as in the input order, and for every COMBO-type query, output the answer for that query.

입력

The first line contains two integers: N Q (1 ≤ N, Q ≤ 100,000) in a line denoting the length of the array and the number of queries. The second line contains a string of N characters (of '0' or '1') representing the binary array B. The i-th character in the string corresponds to the i-th element of the binary array B ('0' represents 0, while '1' represents 1). The next Q lines each contains three integers T L R (1 ≤ T ≤ 2; 1 ≤ L ≤ R ≤ N) denoting the query. If T = 1, then this query is a FLIP query, otherwise this query is a COMBO query.

출력

For each COMBO-type query, print the answer of the query in the same order of the queries running order.

풀이 과정

최장 0 부분을 저장하는 금광 세그, 최장 1 부분을 저장하는 금광 세그를 이용한다. Flip을 여러 번 한다고 해도, 짝수 번 Flip을 하면 어차피 원래대로 돌아가기 때문에.. ( 2번, 4번, 6번... 반전하면 원래 binary array가 된다. ) 홀수 번 Flip을 했을 때 lazy를 주고, lazy를 push 할 때 그 구간에 있는 0 금광 세그와 1 금광 세그의 값들을 전부 교환해주면 반전한 효과를 얻을 수 있다! 

void push(int start, int end, int idx) {
	if (tree[idx].lazy != 0) {
		swap(&tree[idx].cnt0_left, &tree[idx].cnt1_left);
		swap(&tree[idx].cnt0_left_pos[0], &tree[idx].cnt1_left_pos[0]);
		swap(&tree[idx].cnt0_left_pos[1], &tree[idx].cnt1_left_pos[1]);

		swap(&tree[idx].cnt0_right, &tree[idx].cnt1_right);
		swap(&tree[idx].cnt0_right_pos[0], &tree[idx].cnt1_right_pos[0]);
		swap(&tree[idx].cnt0_right_pos[1], &tree[idx].cnt1_right_pos[1]);

		swap(&tree[idx].cnt0_all, &tree[idx].cnt1_all);
		swap(&tree[idx].cnt0_all_pos[0], &tree[idx].cnt1_all_pos[0]);
		swap(&tree[idx].cnt0_all_pos[1], &tree[idx].cnt1_all_pos[1]);

		if (start != end) {
			tree[idx * 2].lazy = (tree[idx * 2].lazy + 1) % 2;
			tree[idx * 2 + 1].lazy = (tree[idx * 2 + 1].lazy + 1) % 2;
		}

		tree[idx].lazy = 0;
	}
}

나머지는 https://readytojoin.tistory.com/59 와 동일하게 작성하였다. 0이나 1 부분의 최장 부분의 길이를 출력하면 되는 문제라서 출력이 간단했다.

#include <stdio.h>
#define SIZE 100005

typedef struct _Node {
	int cnt0_left;
	int cnt0_left_pos[2];
	int cnt0_right;
	int cnt0_right_pos[2];
	int cnt0_all;
	int cnt0_all_pos[2];

	int cnt1_left;
	int cnt1_left_pos[2];
	int cnt1_right;
	int cnt1_right_pos[2];
	int cnt1_all;
	int cnt1_all_pos[2];

	int lazy;
	int range;
} Node;

char str[SIZE];
Node tree[SIZE * 4];

int max(int a, int b) {
	if (a > b) return a;
	else return b;
}

Node merge(Node a, Node b) {
	Node tmp;

	// 0 - left
	if (a.cnt0_left == a.range && b.cnt0_left != 0) {
		tmp.cnt0_left = a.range + b.cnt0_left;
		tmp.cnt0_left_pos[0] = a.cnt0_left_pos[0];
		tmp.cnt0_left_pos[1] = b.cnt0_left_pos[1];
	}
	else {
		tmp.cnt0_left = a.cnt0_left;
		tmp.cnt0_left_pos[0] = a.cnt0_left_pos[0];
		tmp.cnt0_left_pos[1] = a.cnt0_left_pos[1];
	}

	// 0 - right
	if (b.cnt0_right == b.range && a.cnt0_right != 0) {
		tmp.cnt0_right = a.cnt0_right + b.range;
		tmp.cnt0_right_pos[0] = a.cnt0_right_pos[0];
		tmp.cnt0_right_pos[1] = b.cnt0_right_pos[1];
	}
	else {
		tmp.cnt0_right = b.cnt0_right;
		tmp.cnt0_right_pos[0] = b.cnt0_right_pos[0];
		tmp.cnt0_right_pos[1] = b.cnt0_right_pos[1];
	}

	// 0 - all
	if (a.cnt0_all >= b.cnt0_all && a.cnt0_all >= a.cnt0_right + b.cnt0_left) {
		tmp.cnt0_all = a.cnt0_all;
		tmp.cnt0_all_pos[0] = a.cnt0_all_pos[0];
		tmp.cnt0_all_pos[1] = a.cnt0_all_pos[1];
	}
	else if (b.cnt0_all >= a.cnt0_all && b.cnt0_all >= a.cnt0_right + b.cnt0_left) {
		tmp.cnt0_all = b.cnt0_all;
		tmp.cnt0_all_pos[0] = b.cnt0_all_pos[0];
		tmp.cnt0_all_pos[1] = b.cnt0_all_pos[1];
	}
	else { // (a.cnt0_right + b.cnt0_left >= a.cnt0_all && a.cnt0_right + b.cnt0_left >= b.cnt0_all)
		tmp.cnt0_all = a.cnt0_right + b.cnt0_left;
		if (a.cnt0_right == 0 || b.cnt0_left == 0) {
			if (a.cnt0_right == 0 && b.cnt0_left == 0) {
				// ...?
				tmp.cnt0_all_pos[0] = a.cnt0_right_pos[0];
				tmp.cnt0_all_pos[1] = b.cnt0_left_pos[1];
			}
			else if (a.cnt0_right == 0) {
				tmp.cnt0_all_pos[0] = b.cnt0_left_pos[0];
				tmp.cnt0_all_pos[1] = b.cnt0_left_pos[1];
			}
			else if (b.cnt0_left == 0) {
				tmp.cnt0_all_pos[0] = a.cnt0_right_pos[0];
				tmp.cnt0_all_pos[1] = a.cnt0_right_pos[1];
			}
		}
		else {
			tmp.cnt0_all_pos[0] = a.cnt0_right_pos[0];
			tmp.cnt0_all_pos[1] = b.cnt0_left_pos[1];
		}
	}

	// 1 - left
	if (a.cnt1_left == a.range && b.cnt1_left != 0) {
		tmp.cnt1_left = a.range + b.cnt1_left;
		tmp.cnt1_left_pos[0] = a.cnt1_left_pos[0];
		tmp.cnt1_left_pos[1] = b.cnt1_left_pos[1];
	}
	else {
		tmp.cnt1_left = a.cnt1_left;
		tmp.cnt1_left_pos[0] = a.cnt1_left_pos[0];
		tmp.cnt1_left_pos[1] = a.cnt1_left_pos[1];
	}

	// 1 - right
	if (b.cnt1_right == b.range && a.cnt1_right != 0) {
		tmp.cnt1_right = a.cnt1_right + b.range;
		tmp.cnt1_right_pos[0] = a.cnt1_right_pos[0];
		tmp.cnt1_right_pos[1] = b.cnt1_right_pos[1];
	}
	else {
		tmp.cnt1_right = b.cnt1_right;
		tmp.cnt1_right_pos[0] = b.cnt1_right_pos[0];
		tmp.cnt1_right_pos[1] = b.cnt1_right_pos[1];
	}

	// 1 - all
	if (a.cnt1_all >= b.cnt1_all && a.cnt1_all >= a.cnt1_right + b.cnt1_left) {
		tmp.cnt1_all = a.cnt1_all;
		tmp.cnt1_all_pos[0] = a.cnt1_all_pos[0];
		tmp.cnt1_all_pos[1] = a.cnt1_all_pos[1];
	}
	else if (b.cnt1_all >= a.cnt1_all && b.cnt1_all >= a.cnt1_right + b.cnt1_left) {
		tmp.cnt1_all = b.cnt1_all;
		tmp.cnt1_all_pos[0] = b.cnt1_all_pos[0];
		tmp.cnt1_all_pos[1] = b.cnt1_all_pos[1];
	}
	else { // (a.cnt0_right + b.cnt0_left >= a.cnt0_all && a.cnt0_right + b.cnt0_left >= b.cnt0_all)
		tmp.cnt1_all = a.cnt1_right + b.cnt1_left;
		if (a.cnt1_right == 0 || b.cnt1_left == 0) {
			if (a.cnt1_right == 0 && b.cnt1_left == 0) {
				// ...?
				tmp.cnt1_all_pos[0] = a.cnt1_right_pos[0];
				tmp.cnt1_all_pos[1] = b.cnt1_left_pos[1];
			}
			else if (a.cnt1_right == 0) {
				tmp.cnt1_all_pos[0] = b.cnt1_left_pos[0];
				tmp.cnt1_all_pos[1] = b.cnt1_left_pos[1];
			}
			else if (b.cnt1_left == 0) {
				tmp.cnt1_all_pos[0] = a.cnt1_right_pos[0];
				tmp.cnt1_all_pos[1] = a.cnt1_right_pos[1];
			}
		}
		else {
			tmp.cnt1_all_pos[0] = a.cnt1_right_pos[0];
			tmp.cnt1_all_pos[1] = b.cnt1_left_pos[1];
		}
	}
	
	tmp.range = a.range + b.range;
	tmp.lazy = 0;
	return tmp;
}

void bitset(int start, int end, int idx, char val) {
	if (val == '0') {
		tree[idx].cnt0_left = 1;
		tree[idx].cnt0_left_pos[0] = start;
		tree[idx].cnt0_left_pos[1] = end;
		tree[idx].cnt0_right = 1;
		tree[idx].cnt0_right_pos[0] = start;
		tree[idx].cnt0_right_pos[1] = end;
		tree[idx].cnt0_all = 1;
		tree[idx].cnt0_all_pos[0] = start;
		tree[idx].cnt0_all_pos[1] = end;

		tree[idx].cnt1_left = 0;
		tree[idx].cnt1_left_pos[0] = start;
		tree[idx].cnt1_left_pos[1] = end;
		tree[idx].cnt1_right = 0;
		tree[idx].cnt1_right_pos[0] = start;
		tree[idx].cnt1_right_pos[1] = end;
		tree[idx].cnt1_all = 0;
		tree[idx].cnt1_all_pos[0] = start;
		tree[idx].cnt1_all_pos[1] = end;

		tree[idx].lazy = 0;
		tree[idx].range = 1;
	}
	else {
		tree[idx].cnt0_left = 0;
		tree[idx].cnt0_left_pos[0] = start;
		tree[idx].cnt0_left_pos[1] = end;
		tree[idx].cnt0_right = 0;
		tree[idx].cnt0_right_pos[0] = start;
		tree[idx].cnt0_right_pos[1] = end;
		tree[idx].cnt0_all = 0;
		tree[idx].cnt0_all_pos[0] = start;
		tree[idx].cnt0_all_pos[1] = end;

		tree[idx].cnt1_left = 1;
		tree[idx].cnt1_left_pos[0] = start;
		tree[idx].cnt1_left_pos[1] = end;
		tree[idx].cnt1_right = 1;
		tree[idx].cnt1_right_pos[0] = start;
		tree[idx].cnt1_right_pos[1] = end;
		tree[idx].cnt1_all = 1;
		tree[idx].cnt1_all_pos[0] = start;
		tree[idx].cnt1_all_pos[1] = end;

		tree[idx].lazy = 0;
		tree[idx].range = 1;
	}
}

void init(int start, int end, int idx) {
	if (start == end) {
		bitset(start, end, idx, str[start]);
		return;
	}

	int mid = (start + end) / 2;
	init(start, mid, idx * 2);
	init(mid + 1, end, idx * 2 + 1);
	tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void push(int start, int end, int idx) {
	if (tree[idx].lazy != 0) {
		swap(&tree[idx].cnt0_left, &tree[idx].cnt1_left);
		swap(&tree[idx].cnt0_left_pos[0], &tree[idx].cnt1_left_pos[0]);
		swap(&tree[idx].cnt0_left_pos[1], &tree[idx].cnt1_left_pos[1]);

		swap(&tree[idx].cnt0_right, &tree[idx].cnt1_right);
		swap(&tree[idx].cnt0_right_pos[0], &tree[idx].cnt1_right_pos[0]);
		swap(&tree[idx].cnt0_right_pos[1], &tree[idx].cnt1_right_pos[1]);

		swap(&tree[idx].cnt0_all, &tree[idx].cnt1_all);
		swap(&tree[idx].cnt0_all_pos[0], &tree[idx].cnt1_all_pos[0]);
		swap(&tree[idx].cnt0_all_pos[1], &tree[idx].cnt1_all_pos[1]);

		if (start != end) {
			tree[idx * 2].lazy = (tree[idx * 2].lazy + 1) % 2;
			tree[idx * 2 + 1].lazy = (tree[idx * 2 + 1].lazy + 1) % 2;
		}

		tree[idx].lazy = 0;
	}
}

void update(int start, int end, int idx, int left, int right) {
	push(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		tree[idx].lazy = (tree[idx].lazy + 1) % 2;
		push(start, end, idx);
		return;
	}

	int mid = (start + end) / 2;
	update(start, mid, idx * 2, left, right);
	update(mid + 1, end, idx * 2 + 1, left, right);
	tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}

Node interval(int start, int end, int idx, int left, int right) {
	push(start, end, idx); 

	Node tmp;
	tmp.cnt0_left = 0; tmp.cnt0_left_pos[0] = start; tmp.cnt0_left_pos[1] = end;
	tmp.cnt0_right = 0; tmp.cnt0_right_pos[0] = start; tmp.cnt0_right_pos[1] = end;
	tmp.cnt0_all = 0; tmp.cnt0_all_pos[0] = start; tmp.cnt0_all_pos[1] = end;
	tmp.cnt1_left = 0; tmp.cnt1_left_pos[0] = start; tmp.cnt1_left_pos[1] = end;
	tmp.cnt1_right = 0; tmp.cnt1_right_pos[0] = start; tmp.cnt1_right_pos[1] = end;
	tmp.cnt1_all = 0; tmp.cnt1_all_pos[0] = start; tmp.cnt1_all_pos[1] = end;
	tmp.lazy = 0;
	tmp.range = end - start + 1;

	if (end < left || right < start) return tmp;
	if (left <= start && end <= right) return tree[idx];

	int mid = (start + end) / 2;
	return merge(interval(start, mid, idx * 2, left, right), interval(mid + 1, end, idx * 2 + 1, left, right));
}

int main(void) {
	int n, q;
	scanf("%d %d", &n, &q);
	scanf("%s", str);

	init(0, n - 1, 1);

	for (int i = 0; i < q; i++) {
		int mode, l, r;
		scanf("%d %d %d", &mode, &l, &r);

		if (mode == 1) {
			// Flip
			update(0, n - 1, 1, l - 1, r - 1);
		}
		else {
			// Combo
			Node result = interval(0, n - 1, 1, l - 1, r - 1);
			printf("%d\n", max(result.cnt0_left, max(result.cnt0_right, max(result.cnt0_all, max(result.cnt1_left, max(result.cnt1_right, result.cnt1_all))))));
		}
	}
	return 0;
}

'-- 예전 기록 > BOJ' 카테고리의 다른 글

[ BOJ ] 14495 : 피보나치 비스무리한 수열 ( SILVER 5 ) / Python  (0) 2023.05.30
[ BOJ ] 2557 : Hello World ( BRONZE 5 ) / C, C++, Python, Java  (0) 2023.05.29
[ BOJ ] 28057 : Binary Sequence and Queries ( DIAMOND 4 ) / C  (0) 2023.05.29
[ BOJ ] 18407 : 가로 블록 쌓기 ( PLATINUM 3 ) / C  (2) 2023.05.28
[ BOJ ] 3002 : 아날로그 다이얼 ( PLATINUM 2 ) / C  (0) 2023.05.01

티스토리툴바