https://www.acmicpc.net/problem/1395
# Approach)
선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자.
해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다.
# Time Complexity)
업데이트를 진행할때 s~t구간의 스위치를 모두 토글해야한다.
각 원소를 하나하나 토글한다면 세그먼트 트리를 사용했을때 시간복잡도는최대 한번의 업데이트에 $O(log(n))$으로 전체의 쿼리에 대해 최악의 상황으로 가정한다면 $O(mnlog(n)) > 10^8$ 로 TLE를 받게 될 것이다.
따라서 lazy propagation을 이용하여 각 업데이트를 $O(log(n))$안에 해결해주어야 한다.
#Code(c++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int>
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int N = 1 << 17;
int n,m;
int seg[1<<18];
bool lazy[1<<17];
void apply(int idx, int len){
seg[idx]=len-seg[idx];
lazy[idx]=0;
if(len!=2) lazy[idx<<1]^=1,lazy[idx<<1|1]^=1;
else seg[idx<<1]^=1,seg[idx<<1|1]^=1;
}
void propagate(int idx,int len){
int logv=0,e=idx; while(e>1)e>>=1,logv++;
for(int i=logv;i>=0;i--) if(idx>>i<N&&lazy[idx>>i]) apply(idx>>i,len<<i);
}
void query(int l,int r){
int sum=0,len=1;
for(l+=N,r+=N;l<r;l>>=1,r>>=1,len<<=1) {
if(l&1){propagate(l,len);sum+=seg[l++];}
if(r&1){propagate(--r, len);sum += seg[r];}
}
cout<<sum<<endl;
}
void mark(int idx,int len){
propagate(idx,len);
int d=len-(seg[idx]<<1);
if(idx<N) lazy[idx]^=1;
else seg[idx]+=d;
while(idx>1) idx>>=1,seg[idx]+=d;
}
void update(int l,int r){
int len=1;
for(l+=N,r+=N;l<r;l>>=1,r>>=1,len<<=1) {
if(l&1) mark(l++,len);
if(r&1) mark(--r,len);
}
}
int main() {
FASTIO; cin>>n>>m;
for0(i,m) {
int o,s,t; cin>>o>>s>>t;
if(o == 1) query(s,t+1);
else update(s,t+1);
}
return 0;
}