https://www.acmicpc.net/problem/1395

 

1395번: 스위치

문제 준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다. 준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다. 하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리

www.acmicpc.net

문제의 분류가 세그먼트 트리 with Lazy Propagation 이다. 밑의 문제를 풀 수 있다면, 세그먼트 트리를 구성하는 연산 기호만 잘 바꿔주면 쉽게 풀 수 있는 문제이다.

https://www.acmicpc.net/problem/10999

 

10999번: 구간 합 구하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c 또는 a, b, c, d가 주어지는데, a가 1인 경우 b번째 수부터 c번째 수에 d를 더하고, a가 2

www.acmicpc.net

#include <iostream>
using namespace std;
 
#define MAX_N 100000
#define endl '\n'
 
int seg[MAX_N*4];
bool lazy[MAX_N*4];
 
void update_lazy(int now, int start, int end) {
     if (lazy[now] == true) {
          seg[now] = (end - start + 1) - seg[now];
          if (start != end) {
               lazy[now * 2] = (lazy[now * 2]) ? false : true;
               lazy[now * 2 + 1] = (lazy[now * 2 + 1]) ? false : true;
          }
          lazy[now] = false;
     }
}
 
void update_range(int now, int left, int right, int start, int end) {
     update_lazy(now, start, end);
     if (left > end || right < start) return;
     if (left <= start && end <= right) {
          seg[now] = (end - start + 1) - seg[now];
          if (start != end) {
               lazy[now * 2] = (lazy[now * 2]) ? false : true;
               lazy[now * 2 + 1] = (lazy[now * 2 + 1]) ? false : true;
          }
          return;
     }
     int mid = (start + end) / 2;
     update_range(now * 2, left, right, start, mid);
     update_range(now * 2 + 1, left, right, mid + 1, end);
     seg[now] = seg[now * 2] + seg[now * 2 + 1];
}
 
int query(int now, int left, int right, int start, int end) {
     update_lazy(now, start, end);
     if (left > end || right < start) return 0;
     if (left <= start && end <= right) {
          return seg[now];
     }
     int mid = (start + end) / 2;
     return(
          query(now * 2, left, right, start, mid) +
          query(now * 2 + 1, left, right, mid + 1, end)
          );
}
 
int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N, Q; cin >> N >> Q;
     for (int i = 0; i < Q; i++) {
          int tag; cin >> tag;
          if (tag == 0) { // 반전
               int s, e; cin >> s >> e;
               update_range(1, s - 1, e - 1, 0, N - 1);
          }
          else { // on의 갯수
               int s, e; cin >> s >> e;
               cout << query(1, s - 1, e - 1, 0, N - 1) << endl;
          }
     }
}
저작자표시

'알고리즘 > [C++]BOJ' 카테고리의 다른 글

[백준BOJ] 6118 숨바꼭질  (0) 2019.10.05
[백준BOJ] 10999 구간 합 구하기 2  (0) 2019.10.04
[백준BOJ] 1626 두 번째로 작은 스패닝 트리  (0) 2019.10.03

+ Recent posts

티스토리툴바