算法分析
差分树状数组的板题
双倍经验: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;
}