BOJ 1395 - 스위치 (P3)

오랜만에 쉬운거. (사실 처음이다)

http://boj.kr/1395

1395번: 스위치

 

풀이) Lazy propagation

스위치가 켜져있으면 1, 꺼져있으면 -1이라고 하자.

그럼 갱신 쿼리는 끝난다. 구간을 반전시킨다는 것은 구간 내 정점에 -1을 곱하는 것과 같기 때문이다.

이제 값이 1인 스위치의 개수를 구해야 한다.

 

[l,r]의 구간의 크기 (r - l + 1)를 s라 하고, [l,r]에서 꺼진 스위치(-1)의 개수가 k개, 켜진 개수가 s-k개라 하자.

이때 [l,r]의 구간 합(=sum)은 s-2k가 된다.

 

즉 s-2k=sum이므로

k = (s-sum)/2

우리가 구해야 하는 값은 켜진 개수인 s-k이므로

s-k = s - (s-sum)/2 = (s+sum)/2

s = r-l+1이므로 (r-l+1+sum)/2를 출력하면 된다.

시간복잡도는 O(QlogN)

 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n, q;
struct Node{
    ll diff=0, lazy=1;
};
struct lazy_seg{
    vector<Node> tree;
    lazy_seg(): tree(404040){}
    void init(ll node, ll s, ll e){
        if(s==e){
            tree[node].diff = -1;
            return;
        }
        init(node*2,s,s+e>>1); init(node*2+1, (s+e>>1)+1, e);
        tree[node].diff = tree[node*2].diff+tree[node*2+1].diff;
    }
    void prop(ll node, ll s, ll e){
        auto [diff, lazy] = tree[node];
        if(lazy==1)return;    //x*1=x
        ll range = e-s+1;
        tree[node].diff = -tree[node].diff;
        if(s!=e)tree[node*2].lazy *= -1, tree[node*2+1].lazy *= -1;
        tree[node].lazy=1;
    }
    void revert(ll node, ll l, ll r, ll s=1, ll e=n){   //reverse인데 귀찮아서 안바꿈
        prop(node,s,e);
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            tree[node].diff = -tree[node].diff;
            if(s==e)return;
            tree[node*2].lazy *= -1;
            tree[node*2+1].lazy *= -1;
            return;
        }
        ll mid = s+e>>1;
        revert(node*2,l,r,s,mid); revert(node*2+1,l,r,mid+1,e);
        tree[node].diff = tree[node*2].diff+tree[node*2+1].diff;
    }
    ll query(ll node, ll l, ll r, ll s=1, ll e=n){
        prop(node,s,e);
        if(e<l or r<s)return 0;
        if(l <= s and e <= r)return tree[node].diff;
        ll mid = s+e>>1;
        return query(node*2,l,r,s,mid)+query(node*2+1,l,r,mid+1,e);
    }
} lazyseg;
int main(){
    fast;
    cin>>n>>q;
    lazyseg.init(1,1,n);
    while(q--){
        ll a,b,c;
        cin>>a>>b>>c;
        if(a==0){
            lazyseg.revert(1,b,c);
        }
        else{
            ll s = c-b+1;
            ll sum = lazyseg.query(1,b,c);
            cout<<(s+sum)/2<<"\n";
        }
    }
}

날먹. 근데 P3풀어도 1점도 안오르는게 말이 되냐