Description
给出了一个序列,你需要处理如下两种询问。
"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。
"Q a b" 询问[a, b]区间中所有值的和。
Input
第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.
第二行包含n个整数,表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。
接下来Q行询问,格式如题目描述。
Output
对于每一个Q开头的询问,你需要输出相应的答案,每个答案一行。
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15 此题和上两题相似,但是区间更新和区间查询,我用了树状数组,zkw线段树还不会区间更新;直接上代码:
import java.io.BufferedInputStream;
import java.util.Scanner; public class Main {
static int n;
static long[] arr = new long[1000001];
static long sun;static long c1[] = new long[100005];
static long c2[] = new long[100005];static String order; public static void main(String[] args) throws Exception {
Scanner s = new Scanner(new BufferedInputStream(System.in));
n = s.nextInt();
int m = s.nextInt(),k, first, second;
for (int i = 1; i <= n; i++) {
arr[i] = s.nextLong();
arr[i] += arr[i - 1];
}
while (m-- != 0) {
order = s.next(); if (order.equals("Q")) { //区间查询
first = s.nextInt();
second = s.nextInt();
sun = arr[second]-arr[first-1]+(second+1)*query(second, c1)-first*query(first-1, c1)-query(second, c2)+query(first-1, c2);
System.out.println(sun);
} else { //区间更新
first = s.nextInt();
second = s.nextInt();
k = s .nextInt();
Add(first,k,c1);
Add(second+1,-k,c1);
Add(first,k*first,c2);
Add(second+1,-k*(second+1),c2); }
}
s.close();
}
static long query(int k, long c[])
{
long ans=0;
while(k>0) {
ans += c[k];
k -= lowbit(k);
}
return ans;
} static void Add(int k, int change, long c[])
{
while(k <= n) {
c[k] += change;
k += lowbit(k);
}
}
static int lowbit(int x) {
return -x & x;
}
}
2016HUAS暑假集训训练2 F - A Simple Problem with Integers的更多相关文章
-
2016HUAS暑假集训训练题 F - 简单计算器
Description 读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值. Input 测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运 ...
-
2016huasacm暑假集训训练五 F - Monkey Banana Problem
题目链接:http://acm.hust.edu.cn/vjudge/contest/126708#problem/F 题意:求至上而下一条路径的所经过的值得和最大值,这题比赛时就出了 但当时看不懂题 ...
-
2016huasacm暑假集训训练三 F - Jungle Roads
题目链接:http://acm.hust.edu.cn/vjudge/contest/123674#problem/F 题意:在相通n个岛屿的所有桥都坏了,要重修,重修每一个桥所用的时间不同,求重修使 ...
-
2016HUAS暑假集训训练2 O - Can you find it?
题目链接:http://acm.hust.edu.cn/vjudge/contest/121192#problem/O 这道题是一道典型二分搜素题,题意是给定3个数组 每个数组的数有m个 再给定l个s ...
-
2016HUAS暑假集训训练2 A - Is It A Tree?
Description A tree is a well-known data structure that is either empty (null, void, nothing) or is a ...
-
2016HUAS暑假集训训练题 D - Find a way
F ...
-
2016HUAS暑假集训训练2 L - Points on Cycle
题目链接:http://acm.hust.edu.cn/vjudge/contest/121192#problem/L 这是一道很有意思的题,就是给定一个以原点为圆心的圆,然后给定 一个点 求最大三 ...
-
2016HUAS暑假集训训练2 K - Hero
题目链接:http://acm.hust.edu.cn/vjudge/contest/121192#problem/K 这也是一道贪心题,刚开始写时以为只要对每一敌人的攻击和血的乘积进行从小到大排序即 ...
-
2016HUAS暑假集训训练2 J - 今年暑假不AC
题目链接:http://acm.hust.edu.cn/vjudge/contest/121192#problem/J 此题要求是计算能够看到最多的节目 ,贪心算法即可,首先对结束时间排序,然后在把开 ...
随机推荐
-
Delphi基础语法的学习笔记和注意事项总结
以下是我在自学Delphi的时候,对一些注意点的简单总结,并没有什么系统性可言,只是一个学习时顺手记下的笔记,主要为了当时加深对知识的印象,并没有希望能在以后的复习和使用Delphi中有什么多大的参考 ...
-
node-webkit教程(13)gpu支持信息查看
node-webkit教程(13)gpu支持信息查看 文/玄魂 目录 node-webkit教程(13)gpu支持信息查看 前言 13.1操作步骤 (一)打开node-webkit,输入chrome: ...
-
Thread safety
https://en.wikipedia.org/wiki/Thread_safety Thread safety is a computer programming concept applicab ...
-
ckeditor 升级到 4.5
原来的项目用的是4.0+asp.net 3.5的,一直不错,这两天升级一下ckeditor到最新版4.5.1,用的是chrome浏览器测试,发觉TextBox.Text获取不到数据,在页面用js写do ...
-
\r,\n,\t
\r:回车符,返回到这一行的开头,return的意思. \n:换行符,到下一行的同一位置,纵坐标相同,new line的意思. \t:制表符,为了在不使用表格的情况下,上下对齐,table的意思. E ...
-
GridView禁止上下滚动的方法
通常情况下,我们使用GridView来完成类似表格的布局,这种布局,我们只需要设置列数,会自动根据适配器的数据进行适配,非常灵活. GridView其实就是一个容器.允许向其内部添加控件,通常情况下, ...
-
easyui 实现Tooltip
$('#btnAddr').tooltip({ content: $('<div class="table"></div>'), //弹出收件地址 show ...
-
redBag
var redBag = (function () { var initialed = false, raining = true, createInterval, walkInterval, cre ...
-
vijos1056题解
题目: 桌面上放了N个平行于坐标轴的矩形,这N个矩形可能有互相覆盖的部分,求它们组成的图形的面积. 在翻题目时,偶然发现了这道标号为WA的题目. 原来,以前我把一中培训的代码发了上去,却WA了4个点, ...
-
cenos安装jdk
安装方式:手动安装 软件:jdk-7u79-linux-x64.tar.gz 官网下载地址:进行下载. 下载完成之后上传到我们的服务器,我使用的是cenos6.5阿里云系统.securecrt工具上传 ...