BOJ 1395 - 스위치

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

문제 태그

Segment Tree Lazy Propagation

문제 풀이

문제를 보자. 거의 Segment Tree Lazy Propagation 연습문제라고 해도 될 정도로 기본적인 연산을 요구하고 있다. 구간의 값을 바꾸는 연산과 구간의 값을 구하는 연산. 

값을 바꾸는 연산은 구간 내의 1을 모두 0으로 바꾸고 0을 모두 1로 바꾸는 연산이다. 이때 기존의 s~e 구간을 담당하고 있는 구간의 값이 val이라면 연산을 한 후 새로운 값은 e-s+1-val 로 쉽게 구할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
ll arr[1010101];
 
struct nod{
    ll val,laz;
};
nod tree[1010101];
 
void lz(ll nod,ll s,ll e){
    if(tree[nod].laz%2){
        tree[nod].val=(e-s+1-tree[nod].val);
        if(s!=e){
            tree[nod*2].laz+=tree[nod].laz;
            tree[nod*2+1].laz+=tree[nod].laz;
        }
        tree[nod].laz=0;
    }
}
 
ll upt(ll l,ll r,ll s,ll e,ll nod){
    lz(nod,s,e);
    if(r<s||e<l) return tree[nod].val;
    if(l<=s&&e<=r){
        tree[nod].laz++;
        lz(nod,s,e);
        return tree[nod].val;
    }
    return tree[nod].val=upt(l,r,s,(s+e)/2,nod*2)+upt(l,r,(s+e)/2+1,e,nod*2+1);
}
 
ll sol(ll l,ll r,ll s,ll e,ll nod){
    lz(nod,s,e);
    if(r<s||e<l) return 0;
    if(l<=s&&e<=r) return tree[nod].val;
    return sol(l,r,s,(s+e)/2,nod*2)+sol(l,r,(s+e)/2+1,e,nod*2+1);
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++){
        ll a,b,c;
        scanf("%lld %lld %lld",&a,&b,&c);
        if(a) printf("%lld\n",sol(b,c,1,n,1));
        else upt(b,c,1,n,1);
    }
 
}