BOJ 1395 | 스위치

일단 이 문제는 $O(N^2/64)$로 뚫린다고 합니다. Bitset으로 날먹할 수 있습니다.

스위치의 값은 0과 1 중 하나라는 점이 중요 포인트입니다. query() 가 합을 구하도록 되어 있으니 구간 합 세그트리를 구성해야 합니다.

lazy는 boolean 값을 담도록 합니다. 0이면 반전시킬 필요가 없고, 1이면 반전시켜야 합니다.

update()는 tag_condition일 때 lazy를 반전시키고, push() 합니다.

push()는 리프 노드일 때는 tree[node]를 반전시키고, 리프 노드가 아니라면 자식 노드에 먼저 전파한 뒤, 자식 노드의 lazy 값을 반영해서 tree[node] 값을 재구성합니다.

tree[node] = tree[node*2] + tree[node*2+1] 이지만 왼쪽 자식노드의 lazy가 1이라면 다음과 같을 것입니다.

tree[node] = (mid-s+1) - tree[node*2] + tree[node*2+1]

lazy를 전파한 후 tree[node]를 구해야 한다는 부분이 생각이 많이 필요합니다.

아래는 코드입니다.

코드

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define ll long long
#define pll pair<ll, ll>
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

class SegTree{
private:
	vector<ll> tree;
	vector<ll> lazy;
public:
	SegTree(int N){
		tree.resize(N*4);
		lazy.resize(N*4);
	}
	
	ll init(vector<ll> &nums, ll node, ll s, ll e){
		if (s == e) return tree[node] = nums[s];
		
		return tree[node] = init(nums, node*2, s, (s+e)/2) + init(nums, node*2+1, (s+e)/2+1, e);
	}
	
	void update(ll node, int s, int e, int l, int r){
		push(node, s, e);
		if (e < l || r < s) return; // break condition
		if (s >= l && e <= r){ // tag condition
			lazy[node] ^= 1;
			push(node, s, e);
			return;
		}
		
		update(node*2, s, (s+e)/2, l, r);
		update(node*2+1, (s+e)/2+1, e, l, r);
		tree[node] = tree[node*2] + tree[node*2+1];
	}
	
	void push(ll node, ll s, ll e){
		if (lazy[node] != 0){
			if (s != e){
				tree[node] = 0;
				lazy[node*2] ^= 1;
				lazy[node*2+1] ^= 1;
				
				ll mid = (s+e)/2;
				if (lazy[node*2]) tree[node] += (mid-s+1) - tree[node*2];
				else tree[node] += tree[node*2];
				
				if (lazy[node*2+1]) tree[node] += (e-mid) - tree[node*2+1];
				else tree[node] += tree[node*2+1];
			}
			else{
				tree[node] ^= 1;
			}
			lazy[node] = 0;
		}
	}
	
	ll query(ll node, int s, int e, int l, int r){
		push(node, s, e);
		if (s > r || l > e) return 0;
		if (l <= s && e <= r) return tree[node];
		
		return query(node*2,s,(s+e)/2,l,r) + query(node*2+1,(s+e)/2+1,e,l,r);
	}
	
};

int main(){
	FASTIO;
	int N, Q; cin >> N >> Q;
	SegTree SG(N);
	
	for (int i = 0; i < Q; i++){
		ll o, x, y; cin >> o >> x >> y;
		if (o == 0){
			SG.update(1, 1, N, x, y);
		}
		else{
			cout << SG.query(1, 1, N, x, y) << endl;
		}
	}
}