算法分析

差分树状数组的板题

双倍经验：ABC035C

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

int main() {
    int n, q;
    cin >> n >> q;

    BIT<int> d(n+1);
    rep(qi, q) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            --l;
            d.add(l); d.add(r, -1);
        }
        else {
            int i;
            cin >> i;
            --i;
            int ans = d.sum(i)&1;
            cout << ans << '\n';
        }
    }

    return 0;
}