比赛 线段数树状数组 评测结果 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;
}