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
两个树状数组一个维护a[i]前缀合,一个维护(n-i+1)*a[i]前缀和。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define esp 1e-9
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
ll sum[],n,m;
ll pos[];
ll a[];
void add(int x,ll val){
for(int i=x;i;i-=lowbit(i))
sum[i]+=val;
}
ll query(int x){
ll ans=;
for(int i=x;i<=;i+=lowbit(i))
ans+=sum[i];
return ans;
}
void add_one(int x,ll val){
for(int i=x;i;i-=lowbit(i))
pos[i]+=val;
}
ll query_one(int x){
ll ans=;
for(int i=x;i<=;i+=lowbit(i))
ans+=pos[i];
return ans;
}
int main()
{
while(scanf("%lld%lld",&n,&m)!=EOF)
{
memset(sum,,sizeof(sum));
memset(pos,,sizeof(pos));
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
add(i,1ll*a[i]*(n-i+));
add_one(i,a[i]);
}
while(m--){
ll op,x,y;
scanf("%lld%lld%lld",&op,&x,&y);
if(op==)
{
ll l=query(x);
ll r=query(y+);
ll u=query_one(x);
ll d=query_one(y+);
//printf("%lld\n",u-d);
printf("%lld\n",l-r-(1ll*(n-y)*(u-d)));
}
else{
add(x,1ll*(-)*a[x]*(n-x+));
add(x,1ll*(n-x+)*y);
add_one(x,1ll*(-)*a[x]);
a[x]=y;
add_one(x,1ll*a[x]);
}
}
}
return ;
}