1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
static constexpr int N = 1e5 + 1;
struct Node {
int l, r, cnt1;
bool flip;
} tr[N << 2];
void pushup(int u) {
tr[u].cnt1 = tr[u << 1].cnt1 + tr[u << 1 | 1].cnt1;
}
void build(vector<int>& nums, int u, int l, int r) {
tr[u] = {l, r, 0};
if (l == r) {
tr[u].cnt1 = nums[l - 1];
} else {
int mid = (l + r) >> 1;
build(nums, u << 1, l, mid), build(nums, u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void reverse(int u) {
tr[u].cnt1 = tr[u].r - tr[u].l + 1 - tr[u].cnt1;
tr[u].flip = !tr[u].flip;
}
void update(int u, int L, int R) {
if (L <= tr[u].l && tr[u].r <= R) {
reverse(u);
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (tr[u].flip) {
reverse(u << 1), reverse(u << 1 | 1);
tr[u].flip = false;
}
if (L <= mid) update(u << 1, L, R);
if (mid < R) update(u << 1 | 1, L, R);
pushup(u);
}
}
public:
vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
int n = nums1.size();
build(nums1, 1, 1, n);
vector<long long> ans;
long long sum = accumulate(nums2.begin(), nums2.end(), 0ll);
for (auto &q : queries) {
if (q[0] == 1) update(1, q[1] + 1, q[2] + 1);
else if (q[0] == 2) sum += 1ll * q[1] * tr[1].cnt1;
else ans.push_back(sum);
}
return ans;
}
};
|