秋实大哥与花
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
秋实大哥是一个儒雅之人，昼听笙歌夜醉眠，若非月下即花前。
所以秋实大哥精心照料了很多花朵。现在所有的花朵排成了一行，每朵花有一个愉悦值。
秋实大哥每天要对着某一段连续的花朵歌唱，然后这些花朵的愉悦值都会增加一个相同的值v(v可能为负)。
同时他想知道每次他唱完歌后这一段连续的花朵的愉悦值总和是多少。
Input
第一行有一个整数n，表示花朵的总数目。
第二行包含n个整数ai，表示第i朵花初始的愉悦值。
第三行包含一个整数m，表示秋实大哥唱了m天的歌。
接下来m行，每行包含三个整数l r v，表示秋实大哥对着[l,r][l,r]这个区间内的花朵歌唱，每朵花的愉悦值增加了v。
1≤n，m，ai，|v|≤1000001≤n，m，ai，|v|≤100000，1≤l≤r≤n。1≤l≤r≤n。
Output
输出共mm行，第ii行表示秋实大哥完成第ii天的歌唱后，那一段花朵的愉悦值总和。
Sample input and output
| Sample Input | Sample Output |
|---|---|
30 0 031 2 11 2 -11 3 1 | 203 |
做线段数的题总会有一些小错误，感觉这一次能1Y，结果PushDown里又犯了小错误。。。唉。。。可能与1Y无缘吧。。>_<
#include#include #include using namespace std;#define lson l, m, rt << 1#define rson m + 1, r, rt <<1|1typedef long long LL;const int N = 100000 + 5;LL sum[N << 2], col[N << 2];void PushUP(int rt){ sum[rt] = sum[rt << 1] + sum[rt << 1|1];}void PushDown(int rt, int m){ if(col[rt]){ col[rt << 1] += col[rt]; col[rt << 1|1] += col[rt]; sum[rt << 1] += (LL)col[rt]*(m - (m >> 1)); sum[rt << 1|1] += (LL)col[rt] * (m >> 1); col[rt] = 0; }}void Build(int l, int r, int rt){ if(l == r){ scanf("%lld", &sum[rt]); return; } int m = (l + r) >> 1; Build(lson); Build(rson); PushUP(rt);}void Updata(int L, int R, int c, int l, int r, int rt){ if(L <= l && r <= R){ col[rt] += c; sum[rt] += (LL)c*( r - l + 1); return ; } PushDown(rt, r - l + 1); int m = (l + r) >> 1; if(L <= m) Updata(L, R, c, lson); if(R > m) Updata(L, R, c, rson); PushUP(rt);}LL Query(int L, int R, int l, int r, int rt){ if(L <= l && r <= R){ return sum[rt]; } PushDown(rt, r - l + 1); int m = (l + r) >> 1; LL ret = 0; if(L <= m) ret += Query(L, R, lson); if(R > m) ret += Query(L, R, rson); return ret;}int main(){ int n, m, l, r, c; scanf("%d", &n); Build(1, n, 1); scanf("%d", &m); while(m --){ scanf("%d %d %d", &l, &r, &c); Updata(l, r, c, 1, n, 1); printf("%lld\n", Query(l, r, 1, n, 1)); } return 0;}