Yuki 230 Splarraay ｽﾌﾟﾗﾚｪｰｲ ( bitset )

No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ - yukicoder

題意：
初始時有一個長度為 N 的陣列。現在 a, b 兩人玩遊戲，有 Q 個操作依序被進行，第 i 個操作可以用 ( x[ i ], l[ i ], r[ i ] ) 描述：
x = 0 : 令 ca 為 arr[ l, r ] 中 a 塗色數，cb 為 arr[ l, r ] 中 b 塗色數，則多的那方得到 max( ca, cb ) 分數。
x = 1: 覆蓋 arr[ l, r ] 為顏色 a
x = 2: 覆蓋 arr[ l, r ] 為顏色 b
最後雙方的分數再各自加上結束時的己方顏色數量。
問最後雙方的分數各為何。

制約：
N, Q ≤ 1e5

解法：
bitset 暴力。

時間 / 空間複雜度：
O( N * Q / 32 )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );

int N;
int Q;

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  cin >> Q;
  long long ans_a = 0, ans_b = 0;
  bitset< MAXN > acol, bcol, mask;
  for( int qi = 0; qi < Q; ++qi ) {
    int x, l, r;
    cin >> x >> l >> r;
    mask.reset();
    mask.flip();
    mask >>= MAXN - ( r - l + 1 );
    mask <<= l;
    if( x == 0 ) {
      int ca = ( acol & mask ).count();
      int cb = ( bcol & mask ).count();
      if( ca > cb ) {
        ans_a += ca;
      } else if( cb > ca ) {
        ans_b += cb;
      }
    } else if( x == 1 ) {
      acol |= mask;
      bcol &= ~mask;
    } else {
      bcol |= mask;
      acol &= ~mask;
    }
  }
  ans_a += acol.count();
  ans_b += bcol.count();
  cout << ans_a << " " << ans_b << endl;
  return 0;
}