Ryuji is not a good student, and he doesn't want to study. But there are n books he should learn, each book has its knowledge a[i]a[i].
Unfortunately, the longer he learns, the fewer he gets.
That means, if he reads books from ll to rr, he will get a[l] imes L + a[l+1] imes (L-1) + cdots + a[r-1] imes 2 + a[r]a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r](LL is the length of [ ll, rr ] that equals to r - l + 1r−l+1).
Now Ryuji has qq questions, you should answer him:
11. If the question type is 11, you should answer how much knowledge he will get after he reads books [ ll, rr ].
22. If the question type is 22, Ryuji will change the ith book's knowledge to a new value.
Input
First line contains two integers nn and qq (nn, q le 100000q≤100000).
The next line contains n integers represent a[i]( a[i] le 1e9)a[i](a[i]≤1e9) .
Then in next qq line each line contains three integers aa, bb, cc, if a = 1a=1, it means question type is 11, and bb, cc represents [ ll , rr ]. if a = 2a=2 , it means question type is 22 , and bb, cc means Ryuji changes the bth book' knowledge to cc
Output
For each question, output one line with one integer represent the answer.
样例输入复制
5 3
1 2 3 4 5
1 1 3
2 5 0
1 4 5样例输出复制
10
8题目来源
题意：两种操作 一种是更新某节点
一种是查询l-r的一个值 这个值的计算公式是：
思路：
看上去就应该是一个线段树 区间查询单点更新
但是对于查询的处理没有那么简单
可以采用前缀和的思想 因为这个公式中的系数是递减的
那么我们在线段树中维护两个值 一个是本身的值 一个是（n-i+1）倍的值
那么我们查询的时候只需要查到倍数之和 减去 本身之和的（n-r）倍就可以了
WA了一会 因为没用long long
还是要注意啊这些细节 虽然单个没有超int 但是相加就会超的
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<set>
//#include<bits/stdc++.h>
#define inf 0x7f7f7f7f7f7f7f7f
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
LL tree[maxn << 2], treetime[maxn << 2], a[maxn];
int n, q;
void pushup(int rt)
{
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
treetime[rt] = treetime[rt << 1] + treetime[rt << 1 | 1];
}
void build(int rt, int l, int r)
{
if (l == r) {
tree[rt] = a[l];
treetime[rt] = a[l] * (n - l + 1);
return;
}
int m = (l + r) / 2;
build(rt << 1, l, m);
build(rt << 1 | 1, m + 1, r);
pushup(rt);
}
void update(int x, LL val, int l, int r, int rt)
{
if (l == r) {
tree[rt] = val;
treetime[rt] = val * (n - l + 1);
return;
}
int m = (l + r) / 2;
if (x <= m) {
update(x, val, l, m, rt << 1);
}
else {
update(x, val, m + 1, r, rt << 1 | 1);
}
pushup(rt);
}
LL query(int L, int R, int l, int r, int rt)
{
if (L <= l && R >= r) {
return tree[rt];
}
int m = (l + r) / 2;
LL ans = 0;
if (L <= m) {
ans += query(L, R, l, m, rt << 1);
}
if (R > m) {
ans += query(L, R, m + 1, r, rt << 1 | 1);
}
pushup(rt);
return ans;
}
LL querytime(int L, int R, int l, int r, int rt)
{
if (L <= l && R >= r) {
return treetime[rt];
}
int m = (l + r) / 2;
LL ans = 0;
if (L <= m) {
ans += querytime(L, R, l, m, rt << 1);
}
if (R > m) {
ans += querytime(L, R, m + 1, r, rt << 1 | 1);
}
return ans;
}
void init()
{
memset(tree, 0, sizeof(tree));
memset(treetime, 0, sizeof(treetime));
}
int main()
{
while (scanf("%d%d", &n, &q) != EOF) {
if(n == 0){
while(q--){
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
printf("0
");
}
continue;
}
init();
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
build(1, 1, n);
for (int i = 0; i < q; i++) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
LL ans = querytime(l, r, 1, n, 1) - (n - r) * query(l, r, 1, n, 1);
printf("%lld
", ans);
}
else {
update(l, r, 1, n, 1);
}
}
}
return 0;
}