题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入样例#1：
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出样例#1：
11
8
20
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
模板题. 因为以前很少写标记永久化, 这里贴一份代码.
PS: 这题在写对拍的时候出现了一些问题. 总结一下经验, 在对拍程序里面尽量不要出现 数字 || 字母 ||下划线 以外的符号, 否则很有可能出现BAT命令台无法运行程序而又没有报错的情况.
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxN = (int)1e5;
long long tag[maxN << 2];
long long sum[maxN << 2];
void modify(int p, long long del, int curL, int curR, int L, int R)
{
if (L <= curL && R >= curR)
{
tag[p] += del;
sum[p] += (curR - curL + 1) * del;
return;
}
int mid = (curL + curR) >> 1;
if(L <= mid)
modify(p << 1, del, curL, mid, L, R);
if(R > mid)
modify((p << 1) + 1, del, mid + 1, curR, L, R);
sum[p] += (min(curR, R) - max(curL, L) + 1) * del;
}
long long query(int p, int curL, int curR, int L, int R)
{
if(L <= curL && R >= curR)
return sum[p];
int mid = (curL + curR) >> 1;
long long ret = 0;
if(L <= mid)
ret += query(p << 1, curL, mid, L, R);
if(R > mid)
ret += query((p << 1) + 1, mid + 1, curR, L, R);
ret += (min(curR, R) - max(curL, L) + 1) * tag[p];
return ret;
}
int main()
{
freopen("L3372.in", "r", stdin);
freopen("L3372.out", "w", stdout);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
memset(tag, 0, sizeof(tag));
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; i ++)
{
long long x;
cin >> x;
modify(1, x, 1, n, i, i);
}
for(int i = 0; i < m; i ++)
{
int opt;
cin >> opt;
if(opt == 1)
{
long long L, R, del;
cin >> L >> R >> del;
modify(1, del, 1, n, L, R);
}
else if (opt == 2)
{
int L, R;
cin >> L >> R;
cout << query(1, 1, n, L, R) << endl;
}
}
}