用c++和segment tree解决下述问题Doing Exercises 描述 As we all know, the lines of students doing exercises between classes are always unsatisfactory to teachers. Today, a teacher wants to require something new. Firstly, he lets some students of N classes correspondingly form n lines. Then, he randomly selects a class to add some of its remaining students to its line, or selects a class to let some students leave its line, or lets the monitors from some adjacent classes report the total number of students in all these classes. This is very annoying for the monitors. Can you write a program to help them complete the reporting task? 输入 The first line is an integer T (T<50), the number of test cases. For each test case, its first line is an integer N (1<=N<=50000), representing the number of classes, and its second line include N integers (a1, a2, a3, ... , an), and ai (1<=ai<=100) means the number of students in the line of class i at the beginning. Then, each next line will be an order. There are 4 kinds of orders: (1) "Add x i" means adding x students to the line of class i; (2) "Sub x i" means that x students leave the line of class i; (3) "Query i j" means that the monitors from class i to class j report the teacher the total number (sum) of students in their classes at that moment (i<j); (4) "End" means ending the exercises, which will only appear at the end of each test case. The number of orders will not exceed 40000. The number of students in any line will never below 0. 输出 For each test case, you must print "Case i:" in the first line. Then for each Query, print the result in one line.
时间: 2024-03-16 07:48:09 浏览: 45
以下是使用 C++ 和线段树解决此问题的示例代码:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 50010;
int n, m;
int a[maxn];
struct node {
int l, r;
int sum;
} tree[maxn * 4];
void build(int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
if (l == r) {
tree[p].sum = a[l];
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
void update(int p, int x, int v) {
if (tree[p].l == x && tree[p].r == x) {
tree[p].sum += v;
return;
}
int mid = (tree[p].l + tree[p].r) / 2;
if (x <= mid) update(p * 2, x, v);
else update(p * 2 + 1, x, v);
tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
int query(int p, int l, int r) {
if (tree[p].l >= l && tree[p].r <= r) return tree[p].sum;
int mid = (tree[p].l + tree[p].r) / 2, ans = 0;
if (l <= mid) ans += query(p * 2, l, r);
if (r > mid) ans += query(p * 2 + 1, l, r);
return ans;
}
int main() {
int T;
scanf("%d", &T);
for (int kase = 1; kase <= T; kase++) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, 1, n);
char op[10];
printf("Case %d:\n", kase);
while (~scanf("%s", op)) {
if (op[0] == 'E') break;
int x, y;
scanf("%d%d", &x, &y);
if (op[0] == 'Q') {
printf("%d\n", query(1, x, y));
} else if (op[0] == 'A') {
update(1, x, y);
} else if (op[0] == 'S') {
update(1, x, -y);
}
}
}
return 0;
}
```
首先,我们定义了线段树节点结构体 `node`,包含线段树节点的左、右端点和区间和。`build` 函数用于建立线段树,`update` 函数用于更新某个节点的值,`query` 函数用于查询某个区间的和。
在主函数中,我们先输入测试用例的数量 `T`,然后对于每个测试用例,输入班级数量 `n` 和每个班级的学生数量。之后,我们不断读入命令,如果是查询命令,则调用 `query` 函数查询区间和并输出,如果是加操作,则调用 `update` 函数增加一个节点的值,如果是减操作,则调用 `update` 函数减少一个节点的值,如果是结束命令,则退出循环。
最后,我们输出每个测试用例的查询结果。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)