A Simple Problem with Integers
Time Limit: 5000MS |
|
Memory Limit: 131072K |
Total Submissions: 17755 |
|
Accepted: 4605 |
Case Time Limit: 2000MS |
Description
You have N integers, A1, A2, ... ,
AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1,
A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa,
Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... ,
Ab.
Output
You need to answer all Q commands in order. One answer in a line.
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
Hint
The sums may exceed the range of 32-bit integers.
Source
分享到:
相关推荐
POJ3468,线段树处理,注意longlongint
相信大家在做poj上的题目的时候如果没有分类的话很迷茫吧....这里有一份目前比较全面的poj题目分类..
NULL 博文链接:https://128kj.iteye.com/blog/1739064
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1746750
Poj中一些题目的源代码,里面共有二十多道题目,OI
NULL 博文链接:https://128kj.iteye.com/blog/1739733
史上最全poj题目分类(159页).pdf
POJ题目分类POJ题目分类POJ题目分类
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 百练 题目分类 poj 百练 题目分类
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。