???? ?? ??? ?????? - Sogang ICPC Team, 2020 Winter
2 likes811 views
Lazy Propagation on Segment Trees Sogang ICPC Team C 2020 ?? ?? ???
![Lazy Propagation
Sogang ICPC Team 12
40 ll a[1000001], tree[1048576 * 2], lazy[1048576 * 2];
41
42 void _propagate(int x, int s, int e) {
43 if (!lazy[x]) return;
44 tree[x] += (e - s + 1) * lazy[x];
45 if (s != e) {
46 lazy[x * 2] += lazy[x];
47 lazy[x * 2 + 1] += lazy[x];
48 }
49 lazy[x] = 0;
50 }
lazy?? ???? ??? ??? ???](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-13-320.jpg)
![Lazy Propagation
Sogang ICPC Team 13
40 ll a[1000001], tree[1048576 * 2], lazy[1048576 * 2];
41
42 void _propagate(int x, int s, int e) {
43 if (!lazy[x]) return;
44 tree[x] += (e - s + 1) * lazy[x];
45 if (s != e) {
46 lazy[x * 2] += lazy[x];
47 lazy[x * 2 + 1] += lazy[x];
48 }
49 lazy[x] = 0;
50 }
?? x? ?? ?????? ?? ?? ??? ??? ??????? ???](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-14-320.jpg)
![Lazy Propagation
Sogang ICPC Team 14
52 ll _sum(int x, int s, int e, int l, int r) {
53 _propagate(x, s, e);
54 if (l > e || r < s) return 0;
55 if (l <= s && e <= r) return tree[x];
56 int m = (s + e) / 2;
57 return _sum(x * 2 , s, m, l, r) +
58 _sum(x * 2 + 1, m + 1, e, l, r);
59 }
? ??? ??? ? propagation? ? ?? ??](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-15-320.jpg)
![Lazy Propagation
Sogang ICPC Team 15
61 void _update(int x, int s, int e, int l, int r, ll dv) {
62 _propagate(x, s, e);
63 if (l > e || r < s) return;
64 if (l <= s && e <= r) {
65 tree[x] += (e - s + 1) * dv;
66 if (s != e) {
67 lazy[x * 2] += dv;
68 lazy[x * 2 + 1] += dv;
69 }
70 return;
71 }
72 int m = (s + e) / 2;
73 _update(x * 2 , s, m, l, r, dv);
74 _update(x * 2 + 1, m + 1, e, l, r, dv);
75 tree[x] = tree[x * 2] + tree[x * 2 + 1];
76 }
????? ?? propagation? ? ?? ??](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-16-320.jpg)
![Lazy Propagation
Sogang ICPC Team 16
61 void _update(int x, int s, int e, int l, int r, ll dv) {
62 _propagate(x, s, e);
63 if (l > e || r < s) return;
64 if (l <= s && e <= r) {
65 tree[x] += (e - s + 1) * dv;
66 if (s != e) {
67 lazy[x * 2] += dv;
68 lazy[x * 2 + 1] += dv;
69 }
70 return;
71 }
72 int m = (s + e) / 2;
73 _update(x * 2 , s, m, l, r, dv);
74 _update(x * 2 + 1, m + 1, e, l, r, dv);
75 tree[x] = tree[x * 2] + tree[x * 2 + 1];
76 }
?? ???? ??? ???? ?? ?? ??? ?? ???? ?? ?? lazy?
?????? ???](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-17-320.jpg)
![JuQueen #
10277
Sogang ICPC Team 26
40 struct mii {
41 ll mn, mx;
42 };
43
44 mii tree[8388608 * 2];
45 int lazy[8388608 * 2];
46
47 int inf = 987654321;
48 int c, n, o;
source code
first, second? ????? struct? ?? ???. ??? ??? ?? ???， ， ，](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-27-320.jpg)
![JuQueen #
10277
Sogang ICPC Team 27
50 void _propagate(int x, int s, int e) {
51 if (!lazy[x]) return;
52 tree[x].mn += lazy[x];
53 tree[x].mx += lazy[x];
54 if (s != e) {
55 lazy[x * 2] += lazy[x];
56 lazy[x * 2 + 1] += lazy[x];
57 }
58 lazy[x] = 0;
59 }
source code
Propagation C ???? ??? ??? ?? ??](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-28-320.jpg)
![JuQueen #
10277
Sogang ICPC Team 28
61 ll _minimum(int x, int s, int e, int l, int r) {
62 _propagate(x, s, e);
63 if (l > e || r < s) return inf;
64 if (l <= s && e <= r) return tree[x].mn;
65 int m = (s + e) / 2;
66 return min(_minimum(x * 2, s, m, l, r),
67 _minimum(x * 2 + 1, m + 1, e, l, r));
68 }
source code
?? ??? ??? ????? propagation? ?? ??](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-29-320.jpg)
![JuQueen #
10277
Sogang ICPC Team 29
70 ll _maximum(int x, int s, int e, int l, int r) {
71 _propagate(x, s, e);
72 if (l > e || r < s) return 0;
73 if (l <= s && e <= r) return tree[x].mx;
74 int m = (s + e) / 2;
75 return max(_maximum(x * 2, s, m, l, r),
76 _maximum(x * 2 + 1, m + 1, e, l, r));
77 }
source code
???? ???? ???? ??? ??](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-30-320.jpg)
![JuQueen #
10277
Sogang ICPC Team 30
79 void _update(int x, int s, int e, int l, int r, ll dv) {
80 _propagate(x, s, e);
81 if (l > e || r < s) return;
82 if (l <= s && e <= r) {
83 tree[x].mn += dv;
84 tree[x].mx += dv;
85 if (s != e) {
86 lazy[x * 2] += dv;
87 lazy[x * 2 + 1] += dv;
88 }
89 return;
90 }
91 int m = (s + e) / 2;
92 _update(x * 2 , s, m, l, r, dv);
93 _update(x * 2 + 1, m + 1, e, l, r, dv);
94 tree[x].mn = min(tree[x * 2].mn, tree[x * 2 + 1].mn);
95 tree[x].mx = max(tree[x * 2].mx, tree[x * 2 + 1].mx);
96 }
source code](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-31-320.jpg)
![JuQueen #
10277
Sogang ICPC Team 32
118 string op;
119 cin >> op;
120 if (op[0] == 's') { // ￣state￣
121 int x;
122 cin >> x;
123 cout << minimum(x, x) << 'n';
124 } else if (op[0] == 'g') { // ￣groupchange￣
source code
?? ??? ??? ?? ?? ?? ?? ????? ??? ??? ?? ????](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-33-320.jpg)
![JuQueen #
10277
Sogang ICPC Team 33
124 } else if (op[0] == 'g') { // ￣groupchange￣
125 int a, b, s;
126 cin >> a >> b >> s;
127
128 ll mn = minimum(a, b), mx = maximum(a, b);
129 if (s > 0 && s + mx > n) {
130 update(a, b, n - mx);
131 cout << n - mx << 'n';
132 } else if (s < 0 && s + mn < 0) {
133 update(a, b, -mn);
134 cout << -mn << 'n';
135 } else {
136 update(a, b, s);
137 cout << s << 'n';
138 }
139 } else { // ￣change￣
source code
?? ??/??? ??? ??? ? ?? ?? ??? ?? ??? ????](https://image.slidesharecdn.com/study1-200118175530/85/Sogang-ICPC-Team-2020-Winter-34-320.jpg)
More Related Content
What's hot (20)
Similar to ???? ?? ??? ?????? - Sogang ICPC Team, 2020 Winter (20)
More from Suhyun Park (6)
???? ?? ??? ?????? - Sogang ICPC Team, 2020 Winter
- 1. #1！ ??????????????? Lazy Propagation on Segment Trees by Suhyun Park Sogang ICPC Team C 2020 ?? ?? ??? acm.sogang.ac.kr
- 2. ?????! Sogang ICPC Team 1 ＾??￣ ???? ?? ???? ?????!
- 3. ?????! Sogang ICPC Team 2 ??... ? ??? C @shiftpsh / shiftpsh.com ? Sogang ICPC Team ?? ??? C 2019? ? ICPC 2019 Seoul Regional? ? Redshift? ?? C 8? ? solved.ac? ?? ??!
- 4. ＾??￣ ???? ???? ??... Sogang ICPC Team 3 ＾??￣ ???? ???? ?? ????? ????? ? ???? ? ? ???? ?? ? ???? ???? ? ??? ?? ★ ??? ? ????? ?? ??? ??? ?? C ?? ?? ??? ????? PS? ?? ????? ? ??? ??? ???? ?????
- 5. ＾??￣ ???? ???? ??... Sogang ICPC Team 4 ??? ?? ?? ? solved.ac ???? ?? ??? ??? ? ????? ?? ? ? ?? ?? ???? ?? ? ??? ??? ????? ????? C ??? ????? ??? ? ??? ICPC ?? ＾?? ??￣? ??? ??? ????
- 6. ＾??￣ ???? ???? ??... Sogang ICPC Team 5 ＾??￣? ?? ?? ???? ???? ? ?? ????? ??? ????? ?????? ?? ??? ?????? ????? ???? C ?? ? ?? ?? ??? ?? ?? ????? ? ??? ??? ???? ? ?? ??? ?? ??? ??? ? ?? ＾??￣ C ?? ?? ?? ?????? ? ??? ??? ??? ??? C ? ?? ?
- 7. ＾??￣ ???? ???? ??... Sogang ICPC Team 6 ?? ?? ? ?? ???? ? ??? ?? ? ?? ???? ???? ?? ? ????? ? ????? ???? ?? ??? ???? ????? ??? ??? ?? C ???? ????? ? solved.ac ??? ??? ??
- 8. Remarks on Segment Trees Sogang ICPC Team 7 1C10 1C5 6C10 1C3 4C5 6C8 9C10 1C2 3 4 5 6C7 8 9 10 1 2 6 7 f (x, s, e, ， ， ， ) = f ( 2x, s, ? s + e 2 ? , ， ， ， ) + f ( 2x + 1, ? s + e 2 ? + 1, e, ， ， ， )
- 9. Remarks on Segment Trees Sogang ICPC Team 8 1C10 1C5 6C10 1C3 4C5 6C8 9C10 1C2 3 4 5 6C7 8 9 10 1 2 6 7 A5 ， ， ， A9 ? ??
- 10. Remarks on Segment Trees Sogang ICPC Team 9 ? Al ， ， ， Ar ? ? ?? = O (log n) ? Ai ???? = O (log n)
- 11. Lazy Propagation Sogang ICPC Team 10 ? Al ， ， ， Ar ? ? ?? ? Al ， ， ， Ar ???? ? ? ??? ???? ??? ??? ?? C ???? ??????? ?? ? ?? O ((r ? l) log n) ★ ??? O (n log n)
- 12. Lazy Propagation Sogang ICPC Team 11 ?? ? ?? O (n log n)? ??? ?? ??? ★ ????? ? ?? ?? ???? ??? ?? ★ ??? ?? ? ???? ??? ?????? ??? ? ???? ??????
- 13. Lazy Propagation Sogang ICPC Team 12 40 ll a[1000001], tree[1048576 * 2], lazy[1048576 * 2]; 41 42 void _propagate(int x, int s, int e) { 43 if (!lazy[x]) return; 44 tree[x] += (e - s + 1) * lazy[x]; 45 if (s != e) { 46 lazy[x * 2] += lazy[x]; 47 lazy[x * 2 + 1] += lazy[x]; 48 } 49 lazy[x] = 0; 50 } lazy?? ???? ??? ??? ???
- 14. Lazy Propagation Sogang ICPC Team 13 40 ll a[1000001], tree[1048576 * 2], lazy[1048576 * 2]; 41 42 void _propagate(int x, int s, int e) { 43 if (!lazy[x]) return; 44 tree[x] += (e - s + 1) * lazy[x]; 45 if (s != e) { 46 lazy[x * 2] += lazy[x]; 47 lazy[x * 2 + 1] += lazy[x]; 48 } 49 lazy[x] = 0; 50 } ?? x? ?? ?????? ?? ?? ??? ??? ??????? ???
- 15. Lazy Propagation Sogang ICPC Team 14 52 ll _sum(int x, int s, int e, int l, int r) { 53 _propagate(x, s, e); 54 if (l > e || r < s) return 0; 55 if (l <= s && e <= r) return tree[x]; 56 int m = (s + e) / 2; 57 return _sum(x * 2 , s, m, l, r) + 58 _sum(x * 2 + 1, m + 1, e, l, r); 59 } ? ??? ??? ? propagation? ? ?? ??
- 16. Lazy Propagation Sogang ICPC Team 15 61 void _update(int x, int s, int e, int l, int r, ll dv) { 62 _propagate(x, s, e); 63 if (l > e || r < s) return; 64 if (l <= s && e <= r) { 65 tree[x] += (e - s + 1) * dv; 66 if (s != e) { 67 lazy[x * 2] += dv; 68 lazy[x * 2 + 1] += dv; 69 } 70 return; 71 } 72 int m = (s + e) / 2; 73 _update(x * 2 , s, m, l, r, dv); 74 _update(x * 2 + 1, m + 1, e, l, r, dv); 75 tree[x] = tree[x * 2] + tree[x * 2 + 1]; 76 } ????? ?? propagation? ? ?? ??
- 17. Lazy Propagation Sogang ICPC Team 16 61 void _update(int x, int s, int e, int l, int r, ll dv) { 62 _propagate(x, s, e); 63 if (l > e || r < s) return; 64 if (l <= s && e <= r) { 65 tree[x] += (e - s + 1) * dv; 66 if (s != e) { 67 lazy[x * 2] += dv; 68 lazy[x * 2 + 1] += dv; 69 } 70 return; 71 } 72 int m = (s + e) / 2; 73 _update(x * 2 , s, m, l, r, dv); 74 _update(x * 2 + 1, m + 1, e, l, r, dv); 75 tree[x] = tree[x * 2] + tree[x * 2 + 1]; 76 } ?? ???? ??? ???? ?? ?? ??? ?? ???? ?? ?? lazy? ?????? ???
- 18. Lazy Propagation Sogang ICPC Team 17 89 ll sum(int l, int r) { 90 return _sum(1, 1, 1000000, l, r); 91 } 92 93 void update(int l, int r, ll dv) { 94 _update(1, 1, 1000000, l, r, dv); 95 } 96 97 void initialize() { 98 _initialize(1, 1, 1000000); 99 } _initialize? ???? ??? ??? ???? ??
- 19. ?? ? ??? 2 # 10999 Sogang ICPC Team 18 ? n ＋ 106 ? m + k ＋ 20000 ?????
- 20. ?? ? ??? 2 # 10999 Sogang ICPC Team 19 115 while (q--) { 116 int op, l, r; 117 cin >> op >> l >> r; 118 if (op == 1) { 119 ll dv; 120 cin >> dv; 121 update(l, r, dv); 122 } else { // op == 2 123 cout << sum(l, r) << 'n'; 124 } 125 } source code
- 21. JuQueen # 10277 Sogang ICPC Team 20 ??? 4, 587, 520?? ???? ??? ???? ????? ?? ??. N ??? ??? ???? ? CPU x? ??? s???? ?? ? CPU a ， ， ， b? ??? s???? ?? ? CPU x? ?? ?? ?? ? ??? ? ? ??. ??? ? ???? ????? ????, ?? ??? ?? ?? ??? ???? ??? ?? ? ? ???? 0??? N ??? ???? ??? ???? ??? ??? ??? ????.
- 22. JuQueen # 10277 Sogang ICPC Team 21 ??? ? ???? ????? ????, ?? ??? ?? ?? ??? ???? ??? ?? ? ? ???? 0??? N ??? ???? ??? ???? ??? ??? ??? ????. ? ?? ???? 1, 2, 3, 4? N = 6???, ?? 4??? ???? ??? ???? 2 ??? ???? ???
- 23. JuQueen # 10277 Sogang ICPC Team 22 CPU a ， ， ， b? ?? ??? ???? mn, ???? mx? ??, s?? ????? ??? ? mx + s > N ???? N ? mx??? ?? ? ?? ? mn + s < 0???? mn??? ?? ? ?? ? ? ? ???? s?? ?? ? ??
- 24. JuQueen # 10277 Sogang ICPC Team 23 ? ?? ??? ? ? ?? ????? ?? ? ??? l ， ， ， r??? ??? ??? ? ??? l ， ， ， r??? ??? ??? ? ??? l ， ， ， r? ?? s?? ????? ??? ?? i? ???? ??? ?? l = r = i
- 25. JuQueen # 10277 Sogang ICPC Team 24 A = {a0, a1, ， ， ， , an} A＞ = {a0 + d, a1 + d, ， ， ， , an + d} ??? ?? max a＞（A＞ ( a＞ ) = max a（A (a) + d min a＞（A＞ ( a＞ ) = min a（A (a) + d ? ?? ★ ?? ???? ??. ? ?? ??
- 26. JuQueen # 10277 Sogang ICPC Team 25 ? ??? l ， ， ， r??? ??? ??? ? ??? l ， ， ， r??? ??? ??? ， ， ， ? ?? ?? ???? ??? ?? ?min, max? ? ??? ? ??? l ， ， ， r? ?? s?? ????? ， ， ， ? ?? ?? lazy propagate ?? ???!
- 27. JuQueen # 10277 Sogang ICPC Team 26 40 struct mii { 41 ll mn, mx; 42 }; 43 44 mii tree[8388608 * 2]; 45 int lazy[8388608 * 2]; 46 47 int inf = 987654321; 48 int c, n, o; source code first, second? ????? struct? ?? ???. ??? ??? ?? ???， ， ，
- 28. JuQueen # 10277 Sogang ICPC Team 27 50 void _propagate(int x, int s, int e) { 51 if (!lazy[x]) return; 52 tree[x].mn += lazy[x]; 53 tree[x].mx += lazy[x]; 54 if (s != e) { 55 lazy[x * 2] += lazy[x]; 56 lazy[x * 2 + 1] += lazy[x]; 57 } 58 lazy[x] = 0; 59 } source code Propagation C ???? ??? ??? ?? ??
- 29. JuQueen # 10277 Sogang ICPC Team 28 61 ll _minimum(int x, int s, int e, int l, int r) { 62 _propagate(x, s, e); 63 if (l > e || r < s) return inf; 64 if (l <= s && e <= r) return tree[x].mn; 65 int m = (s + e) / 2; 66 return min(_minimum(x * 2, s, m, l, r), 67 _minimum(x * 2 + 1, m + 1, e, l, r)); 68 } source code ?? ??? ??? ????? propagation? ?? ??
- 30. JuQueen # 10277 Sogang ICPC Team 29 70 ll _maximum(int x, int s, int e, int l, int r) { 71 _propagate(x, s, e); 72 if (l > e || r < s) return 0; 73 if (l <= s && e <= r) return tree[x].mx; 74 int m = (s + e) / 2; 75 return max(_maximum(x * 2, s, m, l, r), 76 _maximum(x * 2 + 1, m + 1, e, l, r)); 77 } source code ???? ???? ???? ??? ??
- 31. JuQueen # 10277 Sogang ICPC Team 30 79 void _update(int x, int s, int e, int l, int r, ll dv) { 80 _propagate(x, s, e); 81 if (l > e || r < s) return; 82 if (l <= s && e <= r) { 83 tree[x].mn += dv; 84 tree[x].mx += dv; 85 if (s != e) { 86 lazy[x * 2] += dv; 87 lazy[x * 2 + 1] += dv; 88 } 89 return; 90 } 91 int m = (s + e) / 2; 92 _update(x * 2 , s, m, l, r, dv); 93 _update(x * 2 + 1, m + 1, e, l, r, dv); 94 tree[x].mn = min(tree[x * 2].mn, tree[x * 2 + 1].mn); 95 tree[x].mx = max(tree[x * 2].mx, tree[x * 2 + 1].mx); 96 } source code
- 32. JuQueen # 10277 Sogang ICPC Team 31 98 ll minimum(int l, int r) { 99 return _minimum(1, 0, c - 1, l, r); 100 } 101 102 ll maximum(int l, int r) { 103 return _maximum(1, 0, c - 1, l, r); 104 } 105 106 void update(int l, int r, ll dv) { 107 _update(1, 0, c - 1, l, r, dv); 108 } source code ?? ??? ?? ??? ????? ?????? ? ??? ?? ??? ?? ???? ???? ?
- 33. JuQueen # 10277 Sogang ICPC Team 32 118 string op; 119 cin >> op; 120 if (op[0] == 's') { // ￣state￣ 121 int x; 122 cin >> x; 123 cout << minimum(x, x) << 'n'; 124 } else if (op[0] == 'g') { // ￣groupchange￣ source code ?? ??? ??? ?? ?? ?? ?? ????? ??? ??? ?? ????
- 34. JuQueen # 10277 Sogang ICPC Team 33 124 } else if (op[0] == 'g') { // ￣groupchange￣ 125 int a, b, s; 126 cin >> a >> b >> s; 127 128 ll mn = minimum(a, b), mx = maximum(a, b); 129 if (s > 0 && s + mx > n) { 130 update(a, b, n - mx); 131 cout << n - mx << 'n'; 132 } else if (s < 0 && s + mn < 0) { 133 update(a, b, -mn); 134 cout << -mn << 'n'; 135 } else { 136 update(a, b, s); 137 cout << s << 'n'; 138 } 139 } else { // ￣change￣ source code ?? ??/??? ??? ??? ? ?? ?? ??? ?? ??? ????
- 35. JuQueen # 10277 Sogang ICPC Team 34 139 } else { // ￣change￣ 140 int x, s; 141 cin >> x >> s; 142 143 ll val = minimum(x, x); 144 if (s > 0 && s + val > n) { 145 update(x, x, n - val); 146 cout << n - val << 'n'; 147 } else if (s < 0 && s + val < 0) { 148 update(x, x, -val); 149 cout << -val << 'n'; 150 } else { 151 update(x, x, s); 152 cout << s << 'n'; 153 } 154 } 155 } source code ????.
- 36. Lazy Propagation Not on Segment Trees Sogang ICPC Team 35 Lazy propagation? ????? ???? ??? ???? ??? ???
- 37. Pixel Triangles # 16572 Sogang ICPC Team 36 2, 000 〜 2, 000 ??? ?? ?? ????, ? ??(?)? ?? ?? ???? ??? ????. ?? ?? ?? 1?, ?? ?? ?? 1???. ? ? ?? ???? ??? ??? ??. ? ?? ???? 3?? ??? A, B, C ? ??? P (A, B, C)? ????. ? P (A, B, C) = {(x, y) | A ＋ x, B ＋ y, 0 ＋ (x ? A) + (y ? B) ＋ C ? 1} ?? ?? ???? ??? ?? ???? n ＋ 4, 000, 000? ???? ?, ?? ????? ?? ??? ??? ????.
- 38. Pixel Triangles # 16572 Sogang ICPC Team 37 P (1, 2, 3) = {(x, y) | 1 ＋ x, 2 ＋ y, 0 ＋ (x ? 1) + (y ? 2) ＋ 3 ? 1}
- 39. Pixel Triangles # 16572 Sogang ICPC Team 38 P (3, 1, 2) = {(x, y) | 3 ＋ x, 1 ＋ y, 0 ＋ (x ? 3) + (y ? 1) ＋ 2 ? 1}
- 40. Pixel Triangles # 16572 Sogang ICPC Team 39 P (5, 5, 1) = {(x, y) | 5 ＋ x, 5 ＋ y, 0 ＋ (x ? 5) + (y ? 5) ＋ 1 ? 1}
- 41. Pixel Triangles # 16572 Sogang ICPC Team 40 ? ? ????? ???? ??? ??? 9?? ??
- 42. Pixel Triangles # 16572 Sogang ICPC Team 41 ??? ??? ? P (0, 0, 2000)? 4, 000, 000? ?? ? bool ??? ????? ?????? ?? ??? ?? 4, 000, 000 〜 2, 000 (2, 000 + 1) 2 Lazy propagation? ????? ??? ??? ? ????
- 43. Pixel Triangles # 16572 Sogang ICPC Team 42 ???? ?? ? ???? ???? ??? ?? ???? 0 3 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1
- 44. Pixel Triangles # 16572 Sogang ICPC Team 43 ?? ??? ?? ???, ? ?? ???? ???, ?? ???? ?? ? − 2?? ??? ?? ??? ?? ?? 0 3 2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1
- 45. Pixel Triangles # 16572 Sogang ICPC Team 44 ??? ???? ???? ? ????? ?? ??(?)? 0 3 2 1 0 0 2 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1
- 46. Pixel Triangles # 16572 Sogang ICPC Team 45 ??? ???? ???? ? ????? ?? ??(?)? 0 3 2 1 0 0 2 1 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1
- 47. Pixel Triangles # 16572 Sogang ICPC Team 46 ??? ???? ???? ? ????? ?? ??(?)? 0 3 2 1 0 0 2 1 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0 0 1
- 48. Pixel Triangles # 16572 Sogang ICPC Team 47 ??? ??? 1 ??? ?? ?? ?? 9?! 0 3 2 1 0 0 2 1 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0 0 1 ??? ??
- 49. 1?? ???? Sogang ICPC Team 48 ? ?? ? ??? 2 # 10999 ? JuQueen # 10277 ? Pixel Triangles # 16572 1. ??? # 1395 2. XOR # 12844 3. ???? ???? 1, 2, ， ， ， , R ? L + 1?? ? # 17353 4. ??? ?? 13 # 13925 5. Range GCD # 12858