https://www.acmicpc.net/problem/1395
세그먼트 트리 lazy전파 유형입니다.
N만 작으면 비트마스크로 해결할 수 있을 것이라 생각했는데..
N도 너무 크고.. 흠.. 잘생각이 나지않았습니다.
스위치의 상태를 체크하려면 항상 그 범위만큼의 시간이 필요합니다.
하지만 lazy를 사용하면 해당 범위의 아래 부분은 나중에 업데이트를 하면 됩니다.
그리고 해당 범위의 노드에서 스위치 개수를 뒤집는 방법은
tree[node] = end - start + 1 - tree[node];
이용하면 됩니다.
범위의 개수에서 현재 on개수를 빼면 off개수가 나오기 때문이죠!
아래는 코드입니다.
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include <iostream> #include <vector> #include <cmath> #define mp make_pair #define MOD 86400 #define INF 0x7fffffff #define MAX_SIZE (int)1e5 using namespace std; //ios::sync_with_stdio(false); cin.tie(0); typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<int, int> vii; typedef vector<ll, ll> vll; void update_lazy(vi &tree, vi &lazy, int node, int start, int end) { if (lazy[node]) { tree[node] = end - start + 1 - tree[node]; if (start != end) { lazy[node * 2] = !lazy[node * 2]; lazy[node * 2 + 1] = !lazy[node * 2 + 1]; } lazy[node] = 0; } } int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) { update_lazy(tree, lazy, node, start, end); if (right < start || end < left) { return tree[node]; } else if (left <= start && end <= right) { tree[node] = end - start + 1 - tree[node]; if (start != end) { lazy[node * 2] = !lazy[node * 2]; lazy[node * 2 + 1] = !lazy[node * 2 + 1]; } return tree[node]; } int mid = (start + end) / 2; return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right); } int sum_query(vi &tree, vi &lazy, int node, int start, int end, int left, int right) { update_lazy(tree, lazy, node, start, end); if (right < start || end < left) { return 0; } else if (left <= start && end <= right) { return tree[node]; } int mid = (start + end) / 2; return sum_query(tree, lazy, node * 2, start, mid, left, right) + sum_query(tree, lazy, node * 2 + 1, mid + 1, end, left, right); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; int tree_size = ceil(log2(n)) + 1; vi st(1 << tree_size); vi lazy(1 << tree_size); for (int i = 0, cmd, a, b; i < m; i++) { cin >> cmd >> a >> b; if (cmd) { cout << sum_query(st, lazy, 1, 1, n, a, b) << '\n'; } else { update_range(st, lazy, 1, 1, n, a, b); } } return 0; } | cs |
'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글
[12844] XOR (0) | 2017.08.26 |
---|---|
[2517] 달리기 (0) | 2017.08.16 |
[10999] 구간 합 구하기 2 (0) | 2017.08.15 |
[2042] 구간 합 구하기 (0) | 2017.08.15 |