GDPU 竞赛技能实践天码行空6

本文主要是介绍GDPU 竞赛技能实践天码行空6，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。

中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

输入
第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令

输出
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

输入样例1

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

输出样例1

Case 1:
6
33
59

👨‍🏫 参考地址

💖 线段树版 Main.java

在这里插入图片描述

import java.util.Scanner;class SegmentTree
{// 定义内部类 Node，表示线段树的节点class Node{int l, r, sum;// 区间为 [l,r],区间和为 sum// Node 类的构造函数，用于初始化节点的起始和结束位置以及和Node(int a, int b){this.l = a;this.r = b;this.sum = 0;}}//	数组存树，tree[i] 的左儿子为 tree[2i],右儿子为 tree[2i+1]Node[] tree; // 线段树数组，存储线段树的节点int[] workers; // 工兵营地人数数组，存储每个工兵营地的人数// SegmentTree 类的构造函数，初始化线段树和工兵营地人数数组SegmentTree(int n){tree = new Node[4 * n]; // 线段树数组的大小是工兵营地数量的 4 倍workers = new int[n + 1]; // 工兵营地人数数组的大小是工兵营地数量加一}// 构造线段树的方法/*** @param l   区间左边界* @param r   区间右边界* @param cur 当前区间的根节点*/void build(int l, int r, int cur){tree[cur] = new Node(l, r); // 初始化线段树的节点// 如果起始位置和结束位置相同，表示到达叶子节点，将叶子节点的和设置为对应工兵营地的人数if (l == r)tree[cur].sum = workers[l];else{// 如果不是叶子节点，则递归构造左右子树，并将当前节点的和设置为左右子树和的和int mid = (l + r) / 2;build(l, mid, cur * 2);build(mid + 1, r, cur * 2 + 1);tree[cur].sum = tree[cur * 2].sum + tree[cur * 2 + 1].sum;}}// 查询线段树中指定闭区间 [l,r] 的和/*** @param l   区间左边界* @param r   区间右边界* @param cur 当前区间的根节点*/int query(int l, int r, int cur){int sum = 0;// 如果查询范围包含了当前节点的范围，则返回当前节点的和if (l <= tree[cur].l && r >= tree[cur].r)sum += tree[cur].sum;else{int mid = (tree[cur].l + tree[cur].r) / 2;// 否则根据查询范围的位置递归查询左右子树if (l > mid)// 查询的区间 和 左区间 没有交集sum += query(l, r, cur * 2 + 1);else if (r <= mid)// 查询的区间 和 右区间 没有交集sum += query(l, r, cur * 2);else// 和左右区间都有交集{sum += query(l, r, cur * 2);sum += query(l, r, cur * 2 + 1);}}return sum;}// 在线段树中指定位置增加值/*** 单点修改：给 tree[idx].sum 加上 val 值* * @param idx 要修改的值下标* @param val 增加多少* @param cur 当前节点*/void add(int idx, int val, int cur){tree[cur].sum += val;// 子结点变动，父结点肯定得变动// 如果当前节点的范围等于要增加值的位置，则直接返回if (tree[cur].l == idx && tree[cur].r == idx)return;// 否则根据要增加值的位置递归更新左右子树if (idx > (tree[cur].l + tree[cur].r) / 2)add(idx, val, cur * 2 + 1);elseadd(idx, val, cur * 2);}
}public class Main
{public static void main(String[] args){Scanner sc = new Scanner(System.in);int cnt = 0;int t = sc.nextInt(); // 读取测试用例数量while (t-- > 0){int n = sc.nextInt(); // 读取工兵营地数量SegmentTree segmentTree = new SegmentTree(n); // 创建线段树实例segmentTree.workers[0] = 0;for (int i = 1; i <= n; i++)segmentTree.workers[i] = sc.nextInt(); // 读取每个工兵营地的人数segmentTree.build(1, n, 1); // 构造线段树System.out.println("Case " + ++cnt + ":");while (true){String ch = sc.next(); // 读取操作类型if (ch.equals("End"))break;else if (ch.equals("Query")){int l = sc.nextInt(); // 读取查询范围起始位置int r = sc.nextInt(); // 读取查询范围结束位置int sum = segmentTree.query(l, r, 1); // 查询线段树中指定范围的和System.out.println(sum); // 输出查询结果} else if (ch.equals("Add")){int idx = sc.nextInt(); // 读取要增加值的位置int x = sc.nextInt(); // 读取要增加的值segmentTree.add(idx, x, 1); // 在线段树中指定位置增加值} else if (ch.equals("Sub")){int idx = sc.nextInt(); // 读取要减少值的位置int x = sc.nextInt(); // 读取要减少的值segmentTree.add(idx, -x, 1); // 在线段树中指定位置减少值}}}}
}