士兵杀敌(二)
- 描述
-
南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的。
小工是南将军手下的军师,南将军经常想知道第m号到第n号士兵的总杀敌数,请你帮助小工来回答南将军吧。
南将军的某次询问之后士兵i可能又杀敌q人,之后南将军再询问的时候,需要考虑到新增的杀敌数。
- 输入
- 只有一组测试数据
第一行是两个整数N,M,其中N表示士兵的个数(1<N<1000000),M表示指令的条数。(1<M<100000)
随后的一行是N个整数,ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行是一条指令,这条指令包含了一个字符串和两个整数,首先是一个字符串,如果是字符串QUERY则表示南将军进行了查询操作,后面的两个整数m,n,表示查询的起始与终止士兵编号;如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A. - 输出
- 对于每次查询,输出一个整数R表示第m号士兵到第n号士兵的总杀敌数,每组输出占一行
- 样例输入
-
5 6
1 2 3 4 5
QUERY 1 3
ADD 1 2
QUERY 1 3
ADD 2 3
QUERY 1 2
QUERY 1 5 - 样例输出
-
6
8
8
20 树状数组树的应用啦(区间更新)。。刚刚用JAVA没AC过去,找不到原因,后来用c++ 写发现AC了,然后发现一个无力吐槽的问题,那个QUERY NUM1 NUM2 要一起输入。。。我是先判断
了条件然后输入num1 num2结果会超时。。。。。import java.util.Scanner; public class 士兵杀敌二 {
static int n,m;
static int [] a;
static int [] c; public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
a = new int [n+1];
c = new int [n+1];
for(int i=1;i<=n;i++){
a[i] = sc.nextInt();
update(i,a[i]);
}
int start,end;
for(int i=0;i<m;i++){
String str = sc.next();
start = sc.nextInt();
end = sc.nextInt();
if(str.equals("QUERY")){
System.out.println(getSum(end)-getSum(start-1));
}else{
update(start,end);
}
} } private static int getSum(int index) {
int sum = 0;
for(int i = index;i>=1;i-=lowbit(i)){
sum+=c[i];
}
return sum;
} private static void update(int index, int value) {
for(int i=index;i<=n;i+=lowbit(i)){
c[i]+=value;
}
} private static int lowbit(int x) {
return x&(-x);
}
}
NYOJ 116 士兵杀敌二的更多相关文章
-
NYOJ 116士兵杀敌(二) 树状数组
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=116 士兵杀敌(一) 数组是固定的,所以可以用一个sum数组来保存每个元素的和就行,但是不 ...
-
NYOJ 116 士兵杀敌 (线段树,区间和)
题目链接:NYOJ 116 士兵杀敌 士兵杀敌(二) 时间限制:1000 ms | 内存限制:65535 KB 难度:5 描写叙述 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的 ...
-
nyoj 116 士兵杀敌(二)【线段树单点更新+求和】
士兵杀敌(二) 时间限制:1000 ms | 内存限制:65535 KB 难度:5 描述 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的. 小工是南将军手下的军师,南将军经常 ...
-
nyoj 116 士兵杀敌(二)(线段树、单点更新)
士兵杀敌(二) 时间限制:1000 ms | 内存限制:65535 KB 难度:5 描述 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的. 小工是南将军手下的军师,南将军经常 ...
-
NYOJ 116 士兵杀敌(二) (树状数组)
题目链接 描述 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的.小工是南将军手下的军师,南将军经常想知道第m号到第n号士兵的总杀敌数,请你帮助小工来回答南将军吧.南将军的某次询问之后 ...
-
NYOJ 116 士兵杀敌(二)(二叉索引树)
http://acm.nyist.net/JudgeOnline/problem.php?pid=116 题意: 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的. 小工是南将军手下的 ...
-
NYOJ 116 士兵杀敌(二)【线段树 单点更新】
题意:题意非常清楚: 策略:如题. 这道题就是简单的线段树应用,据说还能够用树状数组来做,等我学了之后在说吧. 代码: #include<stdio.h> #include<stri ...
-
NYOJ 123 士兵杀敌4-树状数组的插线求点
士兵杀敌(四) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军麾下有百万精兵,现已知共有M个士兵,编号为1~M,每次有任务的时候,总会有一批编号连在一起人请战(编 ...
-
NYOJ 119 士兵杀敌(三) RMQ ST
NYOJ 119 士兵杀敌(三) RMQ ST 题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=119 思路: ST在线 预处理O(nlog ...
随机推荐
-
QuickFlow UI 控件之 NamedFormAttachment
在开发自定义表单时,如果碰到需要按类别上传附件的情况,(比如流程附件分为草稿版,正式版,发布版),比较难处理,需要开发自定义字段控件来实现. QF最新版本(Build131124)提供了NamedFo ...
-
SSH_框架整合7--整个项目CODE
一 架构 1Action类 2 配置文件 3 View页面 二 Code 1 src (1)com.atguigu.ssh.actions >EmployeeAction.java packa ...
-
beaglebone-black 在Angstrom系统中的网络配置方法
Beaglebone Linux 101: Assigning a Static IP Address with Connman Posted on February 6, 2012 by dwatt ...
-
poj_1743_Musical Theme(后缀数组)
题目链接:poj_1743_Musical Theme 题意: 给你一串数字,让你找最长的变化相同不重叠的子串,至少长度为5 题解: 处理数据后用后缀数组加二分答案,然后用height数组check答 ...
-
简单的做一个图片上传预览(web前端)
转载:点击查看原文 在做web项目很多的时候图片都是避免不了的,所以操作图片就成了一个相对比较棘手的问题,其实也不是说很麻烦,只是说上传然后直接预览的过程很恶心,今天简单的做一个处理. 效果预览: & ...
-
《基于Nginx的中间件架构》学习笔记---3.nginx的目录分析
一.目录分析 用yum的方式进行安装实质上装的都是一个个的rpm包,对于linux系统rpm包管理器,我们使用命令rpm -ql 服务名称 就可以列出我们已经安装的服务所对应安装的每一个文件所在的目 ...
-
Codeforces Round #272 (Div. 2) D. Dreamoon and Sets 构造
D. Dreamoon and Sets 题目连接: http://www.codeforces.com/contest/476/problem/D Description Dreamoon like ...
-
vim ,vi总是卡死,终于找到原因了。
玩了这么多年linux 居然不知道这个..特此记录. 使用vim时,如果你不小心按了 Ctrl + s后,你会发现不能输入任何东西了,像死掉了一般,其实vim并没有死掉,这时vim只是停止向终端输出而 ...
-
git自用笔记
同步远程库:git clone xxx.git [filename] git ls-files: 查看已经添加进暂存区的文件. 在commit前修改一个文件后(假设名为:xxx.file),想撤销时, ...
-
SaltStack学习系列之自定义grains
Master端 打开存放自定义grains的目录 vim /etc/salt/master file_roots: base: - /srv/salt/ 建立自定义模块 cd /srv/salt mk ...