Time Limit: 5000MS | Memory Limit: 131072K | |
Total Submissions: 48231 | Accepted: 14226 | |
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.
题意:
有N(1到100000)个数和M(1到100000)个操作,给出这个N个数的每个数的值Ai(-100000000到1000000000)。操作有两类,第一类Q a b,代表将[a,b]这区间内的数相加输出结果;第二类C a b c,代表将[a,b]区间内的每个数都+c处理。输出每当Q询问时候的结果。
思路:
线段树。延迟标记。将1到N进行线段树处理,用ad域来标记。
AC:
#include<stdio.h> #define MAX 250000+5 typedef struct { __int64 l; //区间起点 __int64 r; //区间终点 __int64 sum; //区间总和 __int64 ad; //标记增加量 }node; node no[MAX]; __int64 num[MAX]; __int64 s; void build(__int64 from,__int64 to,__int64 i) { __int64 mid=(from+to)/2; no[i].l=from; no[i].r=to; no[i].ad=0; //一开始增加量都为0 if(from==to) { no[i].sum=num[from]; return; } build(from,mid,2*i); build(mid+1,to,2*i+1); no[i].sum=no[i*2].sum+no[i*2+1].sum; } void find(__int64 from,__int64 to,__int64 i) { __int64 mid=(no[i].l+no[i].r)/2; if(from==no[i].l&&to==no[i].r) { if(!no[i].ad) { s+=no[i].sum; return; } else { s+=no[i].sum+(no[i].r-no[i].l+1)*no[i].ad; //这两天一直纠结这个问题 //想着如果在这里往下传标记行不行 //后来发现是忘了维护sum值了,就这点纠结了两天 //RE的原因是如果[1,1]的时候往下传就没有意义了,但是为了确保能下传,数组要开大点 //还有是+=,而不是直接= //no[i].sum+=(no[i].r-no[i].l+1)*no[i].ad; //no[2*i].ad+=no[i].ad; //no[2*i+1].as+=no[i].ad; //no[i].ad=0; //其实这里可以不需要作标记下传操作的,仅仅只是好奇一下 return; } } else { if(no[i].ad) { no[i].sum+=(no[i].r-no[i].l+1)*no[i].ad; no[2*i].ad+=no[i].ad; no[2*i+1].ad+=no[i].ad; no[i].ad=0; //传给左右儿子之后才能清零 } if(from>=mid+1) find(from,to,2*i+1); if(to<=mid) find(from,to,2*i); if(from<=mid&&to>=mid+1) { find(from,mid,2*i); find(mid+1,to,2*i+1); } } } void add(__int64 from,__int64 to,__int64 i,__int64 w) { __int64 mid=(no[i].l+no[i].r)/2; if(no[i].l==from&&no[i].r==to) { no[i].ad+=w; //当找到这个区间之后,增量标记域增加 //而不是直接总和增加 return; } else { if(no[i].ad!=0) { no[i].sum+=(no[i].r-no[i].l+1)*no[i].ad; //当下一次查询的时候,标记域的值ad使总和sum增加 no[2*i].ad+=no[i].ad; no[2*i+1].ad+=no[i].ad; //增加完后则往下传 no[i].ad=0; //传完之后本身标记的值已经使总和sum增加完毕,故变为0 } no[i].sum+=(to-from+1)*w; //这里的相加不是标记域所导致的,是所输入的区间所导致的 if(from>=mid+1) add(from,to,2*i+1,w); if(to<=mid) add(from,to,2*i,w); if(from<=mid&&to>=mid+1) { add(from,mid,2*i,w); add(mid+1,to,2*i+1,w); } //继续查找线段树,找到相同的区间则标记 } } int main() { __int64 n,m; scanf("%I64d%I64d",&n,&m); for(__int64 i=1;i<=n;i++) scanf("%I64d",&num[i]); build(1,n,1); while(m--) { char c; scanf(" %c",&c); if(c=='Q') { __int64 from,to; scanf("%I64d%I64d",&from,&to); s=0; find(from,to,1); printf("%I64d\n",s); } if(c=='C') { __int64 from,to; __int64 w; scanf("%I64d%I64d%I64d",&from,&to,&w); add(from,to,1,w); } } return 0; }
总结:
1.维护ad的同时也要维护sum值,记住;
2.注意数据范围;
相关推荐
We construct a simple fully homomorphic encryption scheme, using only elementary modular arithmetic. We use Gentry’s technique to construct a fully homomorphic scheme from a “bootstrappable” ...
Printing Floating-Point Numbers Quickly and Accurately with IntegersFlorian Loitsch Inria Sophia Antipolis2004 Route des Lucioles - BP 93 - 06902 Sophia Antipolis Cedex florian.loitsch@inria....
I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. Input The first line of the input contains an integer T(1 ) which means the number of ...
I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. Input The first line of the input contains an integer T(1) which means the number of ...
The bipartite independence number of a graph G, denoted as ˜α(G), is the minimal number k such that there exist positive integers a and b with a + b = k + 1 with the property that for any two sets A...
Calculate A + B. Each line will contain two integers A and B. Process to end of file. For each case, output A + B in one line.
主要介绍数字图像处理的基本操作 ...% as A, with 1s (TRUE) in the locations corresponding to integers % (i.e., . . . -2 -1 0 1 2 . . . )in A, and 0s (FALSE) elsewhere. % A must be a numeric array.
Source codes provide implementations of any-length integers and the +-*/% calculations. The integers never overflow or downflow!
Given two integers n and m, count the number of pairs of integers (a,b) such that 0 < a (a^2+b^2 +m)/(ab) is an integer. This problem contains multiple test cases! The first line of a multiple input ...
Bits is the second of a series of 25 Chapters devoted to algorithms, problem solving, and C++ programming. This book is about low level bit programming Table of Contents Chapter 1. Given an unsigned ...
Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 Author HDOJ 代码: #include int main() { ...
A Freeware MFC class which provides 96 bit integers(10KB)
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is [4,3,2,2,1,1], then there are four ...
Using Python as a Simple Adding Machine Recipe 3.15. Checking a Credit Card Checksum Recipe 3.16. Watching Foreign Exchange Rates Chapter 4. Python Shortcuts Introduction Recipe 4.1. ...
Input contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line.
An Exposition of the Eisenstein Integers An Exposition of the Eisenstein Integers
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
Try It Out: Creating a MIME Message with an Attachment 315 MIME Multipart Messages 316 Try It Out: Building E-mail Messages with SmartMessage 320 Sending Mail with SMTP and smtplib 321 Try It Out:...
Create a structure called Struct1 with the following member variables: A short integer A long integer A string of 64 characters A double precision floating point variable Create a second structure ...
9.8.2 Forces with a Velocity Component 480 9.8.3 Simulating Drag in the System 481 9.8.4 Leap Frog Method 481 9.8.5 Velocity Verlet Method 483 9.8.6 Gear's Fifth-Order Predictor-Corrector Method ...