显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) ((x)&(-(x)))
#define LL long long
using namespace std;
namespace mine{
template<class T>inline void readint(T &__x){
static int __c;
static bool __neg;
__x=0;
__neg=false;
do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
if(__c=='-'){
__neg=true;
__c=getchar();
}
for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
if(__neg)__x=-__x;
}
template<class T>inline void putint(T __x){
static int __a[40],__i,__j;
static bool __neg;
__neg=__x<0;
if(__neg)__x=-__x;
__i=0;
do{
__a[__i++]=__x%(T)10^(T)48;
__x/=10;
}while(__x);
if(__neg)putchar('-');
for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
}
}
using namespace mine;
const int maxn=100010;
void add(int,LL,LL*);
LL query(int,LL*);
LL a[maxn],c1[maxn]={0},c2[maxn]={0};
int n,m,x,y;
LL d;
inline int MAIN(){
#define MINE
#ifdef MINE
freopen("overwatch.in","r",stdin);
freopen("overwatch.out","w",stdout);
#endif
readint(n);
readint(m);
for(int i=1;i<=n;i++){
readint(a[i]);
add(i,a[i]*(LL)(n-i+1),c1);
add(i,a[i],c2);
}
while(m--){
readint(x);
if(x==1){
readint(x);
readint(d);
add(x,d*(LL)(n-x+1),c1);
add(x,d,c2);
}
else{
readint(x);
readint(y);
putint(query(y,c1)-query(x-1,c1)-(query(y,c2)-query(x-1,c2))*(LL)(n-y));
putchar('\n');
}
}
#ifndef MINE
printf("\n--------------------DONE--------------------\n");
for(;;);
#endif
return 0;
}
int hzoier=MAIN();
int main(){;}
inline void add(int x,LL d,LL *c){
while(x<=n){
c[x]+=d;
x+=lowbit(x);
}
}
inline LL query(int x,LL *c){
LL ans=0ll;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
/*
题意很好理解，类似一个hash，只不过带了动态修改。
本来想转离线......然而不会写CDQ，所以还是写在线吧。
大体思路应该是线段树or树状数组......
对于每个数，我们预处理时把它变为ai*(n-i+1)，这样求和就可以用两个树状数组分别维护。
修改当然更简单，直接更新树状数组即可。
感觉就是水题嘛......
等我学会了CDQ再试试用CDQ水了这题......
*/
AntiLeaf