c++书写代码并通过这道题 # [jrksj r7] 铃音的第二分块 ## 题目描述 堀北铃音给了您一个长度为 $n$ 的序列 $a$，请您支持 $m$ 次操作： 1. 将 $[l,r]$ 区间中 $> x$ 的数减去 $x$。 2. 求 $[l,r]$ 区间中 $\le x$ 的数的个数。 ## 输入格式 **本题强制在线。** 第一行两个整数 $n,m$。 第二行 $n$ 个整数表示 $a$。 下面 $m$ 行，每行四个整数 $opt,l,r,x'$，$opt$ 表示操作编号，$x'$ 异或上次操作 $2$ 答案得到真实的 $x$。若此前没有操作 $2$，则不需要进行异或操作，真实的 $x$ 即为 $x'$。 ## 输出格式 对于所有操作 $2$，每行输出一个整数表示答案。 ## 样例 #1 ### 样例输入 #1 ``` 10 10 20 10 20 14 4 15 11 20 2 13 2 5 9 1 1 7 8 2 1 2 3 8 1 4 6 12 2 1 7 9 2 2 7 20 2 3 9 4 2 8 9 7 1 3 10 0 2 8 9 7

```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; struct Node { int val; int cnt; Node(int v = 0, int c = 0) : val(v), cnt(c) {} }; class SegTree { private: vector<Node> tree; int n; void merge(Node &parent, Node left, Node right) { parent.val = max(left.val, right.val); parent.cnt = left.cnt + right.cnt; if (left.val == parent.val) parent.cnt += left.cnt; if (right.val == parent.val) parent.cnt += right.cnt; } void build(int l, int r, int idx, vector<int> &arr) { if (l == r) { tree[idx] = Node(arr[l]); } else { int mid = (l + r) / 2; build(l, mid, 2 * idx + 1, arr); build(mid + 1, r, 2 * idx + 2, arr); merge(tree[idx], tree[2 * idx + 1], tree[2 * idx + 2]); } } void update(int l, int r, int idx, int pos, int val) { if (l == r) { tree[idx].val -= val; } else { int mid = (l + r) / 2; if (pos <= mid) update(l, mid, 2 * idx + 1, pos, val); else update(mid + 1, r, 2 * idx + 2, pos, val); merge(tree[idx], tree[2 * idx + 1], tree[2 * idx + 2]); } } int query(int l, int r, int idx, int ql, int qr, int val) { if (ql <= l && qr >= r) { return tree[idx].cnt - (tree[idx].val > val ? tree[idx].cnt : 0); } else { int mid = (l + r) / 2; int ans = 0; if (ql <= mid) ans += query(l, mid, 2 * idx + 1, ql, qr, val); if (qr > mid) ans += query(mid + 1, r, 2 * idx + 2, ql, qr, val); return ans; } } public: SegTree(int size) { n = size; tree.resize(4 * size); } void build(vector<int> &arr) { build(0, n - 1, 0, arr); } void update(int pos, int val) { update(0, n - 1, 0, pos, val); } int query(int l, int r, int val) { return query(0, n - 1, 0, l, r, val); } }; int main() { int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; SegTree segTree(n); segTree.build(a); int opt, l, r, x; while (m--) { cin >> opt >> l >> r >> x; --l, --r; if (opt == 1) { segTree.update(l, r, x); } else { cout << segTree.query(l, r, x) << endl; } } return 0; } ``` 这个C++代码实现了题目要求的功能。首先，定义了一个结构体`Node`来存储每个节点的信息，包括当前最大值和小于等于当前最大值的元素个数。然后，定义了一个`SegTree`类来处理区间查询和更新操作。在主函数中，读取输入并构建线段树，接着处理每个操作并输出结果。 [2024-07-18 21:08:10 | AI写代码神器 | 875点数解答]