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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
class SegmentTreeNode { private: unique_ptr<SegmentTreeNode> left = nullptr, right = nullptr; ll start = 0, end = 0; ll val = 0; public: SegmentTreeNode(ll value, ll start_, ll end_): val(value), start(start_), end(end_) {} SegmentTreeNode(ll start_, ll end_): start(start_), end(end_) {} static unique_ptr<SegmentTreeNode> buildTree(const vector<ll>& nums, ll i, ll j) { if (i == j) { return make_unique<SegmentTreeNode>(nums[i], i, j); } else { ll mid = i + (j - i) / 2; auto ret = make_unique<SegmentTreeNode>(i, j); ret->left = buildTree(nums, i, mid); ret->right = buildTree(nums, mid + 1, j); ret->val = ret->left->val + ret->right->val; return ret; } } ll queryRange(ll i, ll j) const { if (i == start && j == end) { return val; } else { ll mid = start + (end - start) / 2; if (j <= mid) { return left->queryRange(i, j); } else if (i > mid) { return right->queryRange(i, j); } else { return left->queryRange(i, mid) + right->queryRange(mid + 1, j); } } } void update(ll index, ll value) { if (start == index && index == end) { val = value; } else { ll mid = start + (end - start) / 2; if (mid >= index) { left->update(index, value); } else { right->update(index, value); } val = left->val + right->val; } } };
int main() { ll T; cin >> T;
for (ll iCase = 1; iCase <= T; ++iCase) { ll N, Q; cin >> N >> Q; vector<ll> nums(N); for (ll i = 0; i < N; ++i) { cin >> nums[i]; } for (ll i = 0; i < N; ++i) { if (i % 2 == 1) nums[i] *= -1; } auto positiveNegtive = SegmentTreeNode::buildTree(nums, 0, nums.size() - 1); for (ll i = 0; i < N; ++i) { nums[i] *= (i+1); } auto multiTree = SegmentTreeNode::buildTree(nums, 0, nums.size() - 1); ll ans = 0; for (ll q = 0; q < Q; ++q) { string op; cin >> op; ll start, end; cin >> start >> end; if (op == "Q") { ans += ((start % 2 == 0) ? -1 : 1 ) * (multiTree->queryRange(start-1,end -1) - (start - 1) * positiveNegtive->queryRange(start-1, end-1)); } else { ans += 0; positiveNegtive->update(start-1, ((start % 2 == 0) ? -1 : 1) * end); multiTree->update(start-1, ((start % 2 == 0) ? -1 : 1) * start * end); } }
cout << "Case #" << iCase << ": " << ans << endl; }
return 0; }
|