A - 整数的简单问题/A - A Simple Problem with Integers
你有 N 个整数，A1、A2、... 、AN。您需要处理两种作。一种类型的作是在给定的时间间隔内将一些给定的数字添加到每个数字。另一种是询问给定区间内的数字之和。
输入
第一行包含两个数字 N 和 Q。1 ≤ N，Q ≤ 100000。
第二行包含 N 个数字，初始值为 A1、A2、... 、AN。-10000000000 ≤ Ai ≤ 1000000000。
接下来的 Q 行中的每一行都表示一个作。
“C a b c” 是指将 c 添加到 Aa、Aa+1、... 、Ab 中的每一个。-10000 ≤ c ≤ 10000。
“Q a b” 表示查询 Aa， Aa+1， ... ， Ab 之和。
输出
您需要按顺序回答所有 Q 命令。一行中只有一个答案。
样本
| 输入复制 | 输出复制 |
|---|---|
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
| 4
55
9
15 |
提示
总和可能超出 32 位整数的范围。
注意：查询的返回值为long long 型
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct ss {
long long sum ;
long long lazy ;
int x ;
int y ;
};
struct ss zong[400005];
long long a[400005];
int n, m;
char v;
int f, g;
long long h;
void build(int i, int l, int r) {
zong[i].x = l, zong[i].y = r;
zong[i].sum = a[r] - a[l - 1];
zong[i].lazy = 0;
if (l == r) {
return;
}
int mid = l + (r - l) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
}
void yidong(int i, int q, int w) {
if (zong[i].y<q || zong[i].x>w || (zong[i].x >= q && zong[i].y <= w))
return;
zong[i * 2].lazy += zong[i].lazy;
zong[i * 2 + 1].lazy += zong[i].lazy;
zong[i].sum += zong[i].lazy * (zong[i].y - zong[i].x + 1);
zong[i].lazy = 0;
yidong(i * 2, q, w);
yidong(i * 2 + 1, q, w);
}
long long chaxun(int i,int q, int w) {
if (zong[i].x >= q && zong[i].y <= w) {
return zong[i].sum + zong[i].lazy * (zong[i].y - zong[i].x + 1);
}
else if ((zong[i].x < q && zong[i].y>=q) || (zong[i].x <= w &&zong[i].y > w)) {
if (zong[i].lazy != 0) {
yidong(i, q, w);
}
return chaxun(i * 2, q, w) + chaxun(i * 2 + 1, q, w);
}
else {
return 0;
}
}
void tianjia(int i, int q,int w,int e) {
if (zong[i].y<q || zong[i].x>w )
return;
else if (zong[i].x >= q && zong[i].y <= w) {
zong[i].lazy += e;
return;
}
else{
if (zong[i].lazy != 0) {
zong[i * 2].lazy += zong[i].lazy;
zong[i * 2 + 1].lazy += zong[i].lazy;
zong[i].sum += zong[i].lazy * (zong[i].y - zong[i].x + 1);
zong[i].lazy = 0;
}
if (zong[i].x < q && zong[i].y >= q) {
zong[i].sum += e * ((zong[i].y > w ? w : zong[i].y) - q + 1);
tianjia(i * 2, q, w, e);
tianjia(i * 2 + 1, q, w, e);
}
else {
zong[i].sum += e * (w - zong[i].x + 1);
tianjia(i * 2, q, w, e);
tianjia(i * 2 + 1, q, w, e);
}
}
}
int main(){
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
a[i] += a[i - 1];
}
build(1, 1, n);
while (m--) {
do{
scanf("%c", &v);
} while (v != 'Q' && v != 'C');
if (v == 'Q') {
scanf("%d %d", &f, &g);
long long t=chaxun(1,f, g);
printf("%lld\n", t);
}
else {
scanf("%d %d %lld", &f, &g, &h);
tianjia(1,f, g, h);
}
}
return 0;
}