백준 1395 - 스위치(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1395

 

느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.

 

 

처리할 일의 개수가 10^5이기에 모든 경우를 계속 갱신한다면 시간 초과가 생길 것입니다.

따라서, 바꾸는 정보를 기억해 놨다가 나중에 바꿔주는 느리게 갱신되는 방법을 사용해야 합니다.

 

단체로 바꿨을 때, 켜지는 전구의 수는 '해당 구간 전체 전구 수 - 현재 켜진 전구 수' 입니다. 

lazy 배열의 값이 홀수일 때만, 전구의 상태를 바꿔주면 된다는 것을 유의해주면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int N, M;
long long basic_Tree[100001 * 4];
long long Tree[100001 * 4];
long long lazy[100001 * 4];

long long segment_tree(int node, int st, int fin) {
	if (st == fin) return basic_Tree[node] = 1;
	int mid = (st + fin) / 2;
	long long left = segment_tree(node * 2, st, mid);
	long long right = segment_tree(node * 2 + 1, mid + 1, fin);
	return basic_Tree[node] = (left + right);
}

void change_lazy(int node, int left, int right) {
	if (lazy[node] % 2 == 1) {
		Tree[node] = basic_Tree[node] - Tree[node];
		if (left != right) {
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
}

void change_tree(int node, int st, int fin, int left, int right) {
	change_lazy(node, st, fin);
	if (left > fin || right < st) return;
	if (left <= st && fin <= right) {
		Tree[node] = basic_Tree[node] - Tree[node];
		if (st != fin) {
			lazy[node * 2] += 1;
			lazy[node * 2 + 1] += 1;
		}
		return;
	}
	int mid = (st + fin) / 2;
	change_tree(node * 2, st, mid, left, right);
	change_tree(node * 2 + 1, mid + 1, fin, left, right);
	Tree[node] = Tree[node * 2] + Tree[node * 2 + 1];
}

long long get_sum(int node, int st, int fin, int left, int right) {
	change_lazy(node, st, fin);
	if (left > fin || right < st) return 0;
	if (left <= st && right >= fin) return Tree[node];
	int mid = (st + fin) / 2;
	long long left_sum = get_sum(node * 2, st, mid, left, right);
	long long right_sum = get_sum(node * 2 + 1, mid + 1, fin, left, right);
	return (left_sum + right_sum);
}


void solve() {
	segment_tree(1, 0, N - 1);
	for (int i = 1; i <= M; i++) {
		int a, x, y;
		scanf("%d %d %d", &a, &x, &y);
		if (a == 0) { // x ~ y 까지 상태 반전
			change_tree(1, 0, N - 1, x - 1, y - 1);
		}
		else { // x ~ y 까지 커져있는 스위치 개수
			cout << get_sum(1, 0, N - 1, x - 1, y - 1) << "\n";
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.