洛谷P3372 【模板】线段树 1

P3372 【模板】线段树 1

标题形貌

如题，已知一个数列 \(\{a_i\}\)，你必要举行下面两种操纵：

• 将某区间每一个数加上 \(k\)。
  
• 求出某区间每一个数的和。
  

输入格式

第一行包罗两个整数 \(n, m\)，分别表现该数列数字的个数和操纵的总个数。
第二行包罗 \(n\) 个用空格分隔的整数 \(a_i\)，此中第 \(i\) 个数字表现数列第 \(i\) 项的初始值。
接下来 \(m\) 行每行包罗 \(3\) 或 \(4\) 个整数，表现一个操纵，详细如下：

• 1 x y k：将区间 \([x, y]\) 内每个数加上 \(k\)。
  
• 2 x y：输出区间 \([x, y]\) 内每个数的和。
  

输特别式

输出包罗多少行整数，即为全部操纵 2 的效果。
输入输出样例 #1

输入 #1

1. 5 5
2. 1 5 4 2 3
3. 2 2 4
4. 1 2 3 2
5. 2 3 4
6. 1 1 5 1
7. 2 1 4

复制代码

输出 #1

1. 11
2. 8
3. 20

复制代码

分析/提示

对于 \(15\%\) 的数据：\(n \le 8\)，\(m \le 10\)。
对于 \(35\%\) 的数据：\(n \le {10}^3\)，\(m \le {10}^4\)。
对于 \(100\%\) 的数据：\(1 \le n, m \le {10}^5\)，\(a_i,k\) 为正数，且恣意时候数列的和不高出 \(2\times 10^{18}\)。
【样例表明】

标题分析

这题的详细分析和AC代码如下：
[code]#includeusing namespace std;#define ll long long#define ull unsigned long longconst int N=1e6+5;ull n,m,a[N],ans[N>x>>y>>k;                        update(x,y,1,n,1,k);                }                else{                        ll x,y;                        cin>>x>>y;                        cout