[백준] 1395 스위치

문제

준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다.

준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다.

하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리하도록 결정하였다.

입력

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O가 0이면 Si번 스위치부터 Ti번 스위치까지 스위치 상태를 반전시키는 일이고 1이면 Si번 스위치부터 Ti번 스위치까지 중 켜져 있는 상태의 스위치 개수를 묻는 일이다. 단, 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.

출력

입력에서 켜진 스위치 개수에 대한 답을 한 줄에 하나씩 출력한다.

 

 

게으른전파를 이용한 세그먼트 트리 문제입니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };

ll N, M, O, S, T;
ll seg[400004], lazy[400004];

ll toggle(ll k) { //0을1로 1을0으로
	return k == 0 ? 1 : 0;
}

void lazy_update(ll l, ll r, ll n) { //게으른 전파
	if (lazy[n]) {
		seg[n] = (r - l + 1) - seg[n];
		if (l != r) {
			lazy[n * 2] = toggle(lazy[n * 2]);
			lazy[n * 2 + 1] = toggle(lazy[n * 2 + 1]);
		}
		lazy[n] = 0;
	}
}

ll update(ll l, ll r, ll n, ll f, ll t) {
	lazy_update(l, r, n); //전파후,
	if (r < f || t < l) { //범위 밖
		return seg[n];
	}
	if (f <= l && r <= t) { //범위 안
		if (l != r) {
			lazy[2 * n] = toggle(lazy[n * 2]);
			lazy[2 * n + 1] = toggle(lazy[n * 2 + 1]);
		}
		return seg[n] = (r - l + 1) - seg[n];
	}
	ll mid = (l + r) / 2;
	return seg[n] = update(l, mid, n * 2, f, t) + update(mid + 1, r, n * 2 + 1, f, t);
}
ll query(ll l, ll r, ll n, ll f, ll t) {
	lazy_update(l, r, n); //전파 후,
	if (r < f || t < l) { //범위 밖
		return 0;
	}
	if (f <= l && r <= t)return seg[n];

	ll mid = (l + r) / 2;
	auto ret= query(l, mid, n * 2, f, t) + query(mid + 1, r, n * 2 + 1, f, t);
	return ret;
}
int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		cin >> O >> S >> T;
		if (O == 0) {
			update(1,N,1,S,T);
		}
		if (O == 1) {
			cout << query(1, N, 1, S, T) << "\n";
		}
	}
}