比赛 |
线段数树状数组 |
评测结果 |
AAAAAAAAAAWWWWWWWWWW |
题目名称 |
数列操作C |
最终得分 |
50 |
用户昵称 |
李宴彬 |
运行时间 |
4.711 s |
代码语言 |
C++ |
内存使用 |
9.35 MiB |
提交时间 |
2018-06-08 15:21:19 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
long long n;
long long c[100010];
long long c1[100010] ;
long long lowb(long long x)
{
return x & -x;
}
long long getsum(long long t[],long long x)
{
long long sum=0;
while(x>0)
{
sum+=t[x];
x-=lowb(x);
}
return sum;
}
void chang(long long t[],long long a,long long b)
{
while(a<=n)
{
t[a]+=b;
a+=lowb(a);
}
}
int main()
{
long long a[1000010];
long long m;
freopen("shuliec.in","r",stdin);
freopen("shuliec.out","w",stdout);
cin>>n;
a[0]=0;
for (long long i=1;i<=n;i++) {
cin>>a[i];
chang(c,i,a[i]-a[i-1]);
chang(c1,i,(i-1)*(a[i]-a[i-1]));
}
cin>>m;
string s;
int x,y,k;
for (long long i=1;i<=m;i++)
{
cin>>s;
if (s=="SUM"){
cin>>x>>y;
cout<<y*getsum(c,y)-getsum(c1,y)-(x-1)*getsum(c,x-1)+getsum(c1,x-1)<<endl;
}
else {
cin>>x>>y>>k;
chang(c,x,k);
chang(c,y+1,-k);
chang(c1,x,k*(x-1));
chang(c1,y+1,-k*y);
}
}
return 0;
}