第八回 アルゴリズム実技検定 J問題

PAST008J

反転するペアは独立しているのがポイント． \(mod 2\) で区間和を求めればよい． これは segtree で実装できる．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

ll op(ll a, ll b){ return a+b; }

ll e() { return 0; }

int main() {

  ll n, q;

  cin >> n >> q;

  segtree<ll, op, e> st(n+1);

  rep(qi,q){

    ll t, k ; cin >> t >> k;

    --k;

    if(t == 1){

      ll x = 0;

      if(k < n){

        x ^= 1;

        k = 2*n-1 - k;

      }

      ll ans = k;

      x ^= (st.prod(k-n+1, n+1)%2);

      if(x) ans = 2*n-1 - k;

      cout << ans+1 << endl;

    }else{

      st.set(k+1, st.get(k+1) + 1);

    }

  }

  return 0;

}