PS/Study

Lazy Propagation

ekwoo 2019. 5. 17. 11:04
반응형

Segment Tree 공부를 하며 Lazy Propagation에 대해 조금 알게 되었습니다.

 

LightSwitching-USACO-2008-NOV-Gold(https://www.acmicpc.net/problem/1395)

 

Lazy Propagation 이해는 https://www.acmicpc.net/blog/view/26 여기서...

 

소스코드

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
#include <cstdio>
using namespace std;
int tr[400000], lz[400000];
 
void lz_pro(int w, int x, int y) {
    if (!lz[w]) return;
    tr[w]=(y-x+1)-tr[w];
    if (x!=y) lz[w*2]^=1, lz[w*2+1]^=1;
    lz[w]=0;
}
 
int up(int S, int E, int w, int x, int y) {
    lz_pro(w,x,y);
    if (y<S || E<x) return tr[w];
    if (S<=x && y<=E) {
        lz[w]^=1;
        lz_pro(w,x,y);
        return tr[w];
    }
    int mid=(x+y)>>1;
    return tr[w] = up(S,E,w*2,x,mid)+up(S,E,w*2+1,mid+1,y);
}
 
int out(int S, int E, int w, int x, int y) {
    lz_pro(w, x, y);
    if (y<S || E<x) return 0;
    if (S<=x && y<=E) return tr[w];
    int mid=(x+y)>>1;
    return out(S,E,w*2,x,mid)+out(S,E,w*2+1,mid+1,y);
}
 
int main() {
    int n, m, q, s, e;
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&q,&s,&e);
        if(q) printf("%d\n", out(s,e,1,1,n));
        else up(s,e,1,1,n);
    }
    return 0;
}
/*
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
*/
 cs

 

반응형
저작자표시 (새창열림)