Lazy Propagation

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

 

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

 

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

 

소스코드

#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 */