问题1040--简单整数问题

1040: 简单整数问题

时间限制: 2 Sec  内存限制: 128 MB
提交: 349  解决: 133
[提交] [状态] [讨论版] [命题人:]

题目描述

罗老师给大家N个数字,用A1, A2, …, AN表示,然后有两个操作:
1.     C a b c:表示给区间[ Aa, Ab ],每个数上增加c的值
2.     Q a b:表示询问区间[ Aa, Ab ]的总和

输入

输入N Q表示N个数和Q个操作
然后输入一行N个数,表示每个数字初始值
然后输入Q行,每行一个操作,如题目描述的两种操作

输出

对于每个询问操作,输出区间和

样例输入 Copy

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

样例输出 Copy

4
55
9
15

提示

【数据规模和约定】
1<=N,Q<=100000
-100000000<=Ai<=100000000
-10000<=c<=10000
题解:
tr[i]表示线段树上的结点,表示[st, ed]的未更新前的区间和
ad[i]表示线段树上的[st, ed]更新了多少值
难点在于,更新的值需要传递下去,回更新上来
void pushDown(int p){
   ad[p+p]+=ad[p]; ad[p+p+1]+=ad[p];
   ad[p]=0LL;
}
void pullUp(int p,int len){
   tr[p]=tr[p<<1]+ad[p<<1]*(len-(len>>1))+tr[p<<1|1]+ad[p<<1|1]*(len>>1);
}

来源/分类