A Simple Problem with Integers
| Time Limit: 5000MS |
? |
Memory Limit: 131072K |
| Total Submissions: 70442 |
? |
Accepted: 21723 |
| 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 POJ Monthly--2007.11.25, Yang Yi |
?
题意：
给出n个数和m个操作，C操作是对[l,r]区间同时加上一个数val，Q操作是查询[l,r]区间的和。
?
思路：
线段树区间更新，需要用到lazy标记，每次更新不用更新到叶子节点，而是更新到一个完整的区间，用一个add[]数组记录这个区间需加上的数，就不用继续往下更新了。增加了pushdown和pushup操作，pushdown的作用是将标记下移，这个区间改动了的话，它下面的孩子都会改动，pushup操作是根据孩子重新求该节点的值。（因为每次都pushdown了，所以该节点没有标记了，所以pushup很简单）
ps：not only success的风格，只用数组就行了。
每次pushdown的时候最好将孩子的值也更新，不更新可能存在一定的问题。
其实如果对于这种相互之间不用因为顺序而影响的更新操作，可以不用pushdown的，query的时候将值依次传下去即可，但是写法稍稍麻烦一些，大白上就是这样写的，需要注意一些细节问题，个人还是喜欢pushdown的写法。
?
代码：
?
#include
#include
#include
#include
#define maxn 100005 #define lson (rt<<1) #define rson (rt<<1|1) #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int n,m; int a[maxn],add[maxn<<2],sum[maxn<<2]; char s[10]; void pushup(int rt) { sum[rt]=sum[lson]+sum[rson]; } void pushdown(int le,int ri,int rt) { if(add[rt]) { add[lson]+=add[rt]; sum[lson]+=add[rt]*((ri-le+2)>>1); add[rson]+=add[rt]; sum[rson]+=add[rt]*((ri-le+1)/2); add[rt]=0; } } void update(int le,int ri,int rt,int u,int v,int val) { if(le==u&&ri==v) { add[rt]+=val; sum[rt]+=val*(ri-le+1); return ; } int mid=(le+ri)>>1; pushdown(le,ri,rt); if(v<=mid) { update(le,mid,lson,u,v,val); } else if(u>=mid+1) { update(mid+1,ri,rson,u,v,val); } else { update(le,mid,lson,u,mid,val); update(mid+1,ri,rson,mid+1,v,val); } pushup(rt); } int query(int le,int ri,int rt,int u,int v) { if(le==u&&ri==v) { return sum[rt]; } int res=0,mid=(le+ri)>>1; pushdown(le,ri,rt); if(v<=mid) { res=query(le,mid,lson,u,v); } else if(u>=mid+1) { res=query(mid+1,ri,rson,u,v); } else { res+=query(le,mid,lson,u,mid); res+=query(mid+1,ri,rson,mid+1,v); } return res; } int main() { while(~scanf("%d%d",&n,&m)) { memset(sum,0,sizeof(sum)); memset(add,0,sizeof(add)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); update(1,n,1,i,i,a[i]); } while(m--) { scanf("%s",s); int u,v,val; if(s[0]=='C') { scanf("%d%d%d",&u,&v,&val); update(1,n,1,u,v,val); } else { scanf("%d%d",&u,&v); int ans=query(1,n,1,u,v); printf("%d\n",ans); } } } return 0; } /* 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 */
?
?
?