1395 스위치 with Lazy Propagation

Lazy Propagation으로 구간 합 구하기 2를 풀고 바로 다음 문제로 넘어갔다. 처음에는 모두 꺼져있고 구간이 주어질 때 키고 끄고를 반복하여 구간 내 켜져있는 스위치의 개수를 출력하는 문제이다. 

 

스위치를 두 번 키면 결국 같은 상태가 된다. 따라서 홀수일때만 노드의 값을 변경해주면 된다. 처음 그냥 구간내 개수로 변경하면 되겠지 했다가 다른 구간에서 변경이 되는 경우도 있으므로 구간 개수에서 현재 노드의 값을 빼줘야하는 것을 뒤늦게 알게 되었다.

 

void update_lazy(int idx, int l, int r) {
	if (lazy[idx] != 0) {
		if (lazy[idx] % 2)
			seg[idx] = (r * 1LL - l + 1) - seg[idx];
		if (l != r) {
			lazy[idx << 1] += lazy[idx];
			lazy[idx << 1 | 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

 

구간 합 구하기 2

구간 합 구하기 2에서 정리한 것에서 홀수일 때만 적용하는 것과 구간 개수에서 자신의 값을 빼는 것만 다르다.

 

전체 소스코드

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 1000001
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

int h = 1;
vi seg;
vi lazy;

void update_lazy(int idx, int l, int r) {
	if (lazy[idx] != 0) {
		if (lazy[idx] % 2)
			seg[idx] = (r * 1LL - l + 1) - seg[idx];
		if (l != r) {
			lazy[idx << 1] += lazy[idx];
			lazy[idx << 1 | 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

void update(int idx, int l, int r, int i, int j) {
	update_lazy(idx, l, r);
	if (r < i || j < l) return;
	if (i <= l && r <= j) {
		seg[idx] = (r * 1LL - l + 1) - seg[idx];
		if (l != r) {
			lazy[idx << 1] += 1;
			lazy[idx << 1 | 1] += 1;
		}
		return;
	}
	int mid = (l + r) >> 1;
	update(idx << 1, l, mid, i, j);
	update(idx << 1 | 1, mid + 1, r, i, j);
	seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
}

int getval(int idx, int l, int r, int i, int j) {
	update_lazy(idx, l, r);
	if (r < i || j < l) return 0;
	if (i <= l && r <= j) {
		return seg[idx];
	}
	int mid = (l + r) >> 1;
	return getval(idx << 1, l, mid, i, j) + getval(idx << 1 | 1, mid + 1, r, i, j);
}

int main() {
	SYNC;
	cin >> n >> m;
	while (h < n) h <<= 1;
	seg.resize(h << 1);
	lazy.resize(h << 1);
	fu(i, 0, m) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			cout << getval(1, 1, n, b, c) << '\n';
		}
		else {
			update(1, 1, n, b, c);
		}
	}
	return 0;
}