1395 - 스위치

 

1395번: 스위치

 

#include <stdio.h>

typedef long long ll;

const ll LN = 1e5;

ll tree[LN * 3 + 10];
ll lazy[LN * 3 + 10];

ll N, M;

void propagate(ll n, ll s, ll e) {
  if (lazy[n] % 2) {
    tree[n] = (e - s + 1) - tree[n];

    if (s != e) {
      ++lazy[n * 2];
      ++lazy[n * 2 + 1];
    }

    lazy[n] = 0;
  }
}

void update(ll n, ll s, ll e, ll qs, ll qe) {
  propagate(n, s, e);

  if (qe < s || e < qs) { return; }
  if (qs <= s && e <= qe) {
    tree[n] = (e - s + 1) - tree[n];

    if (s != e) {
      ++lazy[n * 2];
      ++lazy[n * 2 + 1];
    }

    return;
  }

  ll m = (s + e) / 2;

  update(n * 2, s, m, qs, qe);
  update(n * 2 + 1, m + 1, e, qs, qe);

  tree[n] = tree[n * 2] + tree[n * 2 + 1];
}

ll query(ll n, ll s, ll e, ll qs, ll qe) {
  propagate(n, s, e);

  if (qe < s || e < qs) { return 0; }
  if (qs <= s && e <= qe) { return tree[n]; }

  ll m = (s + e) / 2;

  return query(n * 2, s, m, qs, qe) + query(n * 2 + 1, m + 1, e, qs, qe);
}

void init() {
  scanf("%lld %lld", &N, &M);
}

void cal() {
  for (ll m = 0; m < M; ++m) {
    ll O, S, T;

    scanf("%lld %lld %lld", &O, &S, &T);

    if (O) {
      printf("%lld\n", query(1, 1, N, S, T));
    } else {
      update(1, 1, N, S, T);
    }
  }
}

int main(void) {
  // freopen("1395.txt", "r", stdin);

  init();

  cal();

  return 0;
}

 

범위 내 스위치 반전을 하는 방법 = 범위 - 현재 켜진 스위치 갯수

 

이것만 기억하면 쉬운 문제