- 262144K
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] * L + a[l+1] *(L-1) + …… + a[r-1] *2 + a[r]（L is the length of [ l， r ] that equals to r−l+1).
Now Ryuji has qq questions, you should answer him:
1. If the question type is 1, you should answer how much knowledge he will get after he reads books [ l, r ].
2. If the question type is 2, Ryuji will change the ith book's knowledge to a new value.
Input
First line contains two integers nn and qq (n, q≤100000).
The next line contains n integers represent a[i](a[i]≤1e9) .
Then in next qq line each line contains three integers a, b, c, if a = 1， it means question type is 1, and b, ccrepresents [ l, r ]. if a =2 , it means question type is 2 , 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
题目来源
#define ull unsigned long long
#define ll long long
#define N 100009
#define lowbit(x) x&(-x)
ull c1[N],c2[N];
int n,q;
void update1(int x,ull num)
{
while(x<=n)
{
c1[x]+=num;
x+=lowbit(x);
}
}
ull getsum1(int x)
{
ull sum=;
while(x>)
{
sum+=c1[x];
x-=lowbit(x);
}
return sum;
}
void update2(int x,ull num)
{
while(x<=n)
{
c2[x]+=num;
x+=lowbit(x);
}
}
ull getsum2(int x)
{
ull sum=;
while(x>)
{
sum+=c2[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
scanf("%d%d",&n,&q);
ull x;
for(int i=;i<=n;i++)
{
scanf("%lld",&x);
update1(i,x);
update2(i,1ull*(n-i+)*x);//在前面加个 ull 保证整体是ull 的
}
int op,l,r;
while(q--)
{
scanf("%d%d%d",&op,&l,&r);
if(op==)
{
ull ans1=1ull*(n-r)*(getsum1(r)-getsum1(l-));
ull ans2=getsum2(r)-getsum2(l-);
printf("%lld\n",ans2-ans1);//"u" 是unsigned int
}
else{
ull temp=getsum1(l)-getsum1(l-);
update1(l,1ull*(r-temp) );
update2(l,1ull*(r-temp)*(n-l+)) ;
}
}
return ;
}