记录编号	542459	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	数列操作C	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	2.456 s
提交时间	2019-09-25 18:44:24	内存使用	16.71 MiB

#include<bits/stdc++.h>
#define LL long long
#define dl double
void rd(int &x){
 x=0;int f=1;char ch=getchar();
 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 while(ch<='9' && ch>='0')x=x*10+ch-'0',ch=getchar();x*=f;
}
void lrd(LL &x){
 x=0;int f=1;char ch=getchar();
 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 while(ch<='9' && ch>='0')x=x*10+ch-'0',ch=getchar();x*=f;
}
const int INF=1e9;
const LL LINF=1e18;
const int inf=1e5+10;
using namespace std;
int n,m,len;
char s[10];
LL a[inf];
LL sum[inf];//sqrt(inf)即可 
int bel[inf];
namespace fk1{
 LL get_sum(int l,int r){
  LL ans=0;
  if(bel[l] == bel[r]){//特判l,r在同一块内情况 
   for(int i=l;i<=r;i++)ans+=a[i];
   return ans;
  }
  for(int i=bel[l]+1;i<bel[r];i++)ans+=sum[i];
  int tmp=bel[l]*len;
  for(int i=l;i<=tmp;i++)ans+=a[i];
  tmp=(bel[r]-1)*len+1;
  for(int i=tmp;i<=r;i++)ans+=a[i];
  return ans;
 }
 void modify(int x,int y){
  a[x]+=y;sum[bel[x]]+=y;
 }
 void does(){
  for(int i=1;i<=m;i++){
   int x,y;
   scanf("%s",s);rd(x);rd(y);
   if(s[0] == 'S')printf("%lld\n",get_sum(x,y));
   else modify(x,y);
  }
 }
}
namespace fk2{
 int tag[inf];
 void add(int l,int r,int val){
  if(bel[l] == bel[r]){
   for(int i=l;i<=r;i++)a[i]+=val;
   return ;
  }
  for(int i=bel[l]+1;i<bel[r];i++)tag[i]+=val;
  int tmp=bel[l]*len;
  for(int i=l;i<=tmp;i++)a[i]+=val;
  tmp=(bel[r]-1)*len+1;
  for(int i=tmp;i<=r;i++)a[i]+=val;
 }
 void does(){
  for(int i=1;i<=m;i++){
   scanf("%s",s);int x,y,z;
   if(s[0] == 'A'){
    rd(x);rd(y);rd(z);
	add(x,y,z);
   }
   else rd(x),printf("%d\n",a[x]+tag[bel[x]]);
  }
 }
}
namespace fk3{
 LL tag[inf];
 void add(int l,int r,LL val){
  if(bel[l] == bel[r]){
   for(int i=l;i<=r;i++)a[i]+=val,sum[bel[l]]+=val;
   return ;
  }
  for(int i=bel[l]+1;i<bel[r];i++)tag[i]+=val;
  int tmp=bel[l]*len;
  for(int i=l;i<=tmp;i++)a[i]+=val,sum[bel[l]]+=val;
  tmp=(bel[r]-1)*len+1;
  for(int i=tmp;i<=r;i++)a[i]+=val,sum[bel[r]]+=val;
 }
 LL get_sum(int l,int r){
  LL ans=0;
  if(bel[l] == bel[r]){
   for(int i=l;i<=r;i++)ans+=a[i];
   ans+=tag[bel[l]]*(r-l+1);return ans;
  }
  for(int i=bel[l]+1;i<bel[r];i++)ans+=tag[i]*len+sum[i];
  int tmp=bel[l]*len;
  for(int i=l;i<=tmp;i++)ans+=tag[bel[l]]+a[i];
  tmp=(bel[r]-1)*len+1;
  for(int i=tmp;i<=r;i++)ans+=tag[bel[r]]+a[i];
  return ans;
 }
 void does(){
  for(int i=1;i<=m;i++){
   scanf("%s",s);int x,y;LL z;
   if(s[0] == 'A'){
    rd(x),rd(y),lrd(z);
    add(x,y,z);
   }
   else rd(x),rd(y),printf("%lld\n",get_sum(x,y));
  }
 }
}
int main(){
 freopen("shuliec.in","r",stdin);
 freopen("shuliec.out","w",stdout);
// freopen("in.txt","r",stdin);
 rd(n);len=sqrt(n);//这个不是一定的,需要进行复杂度分析 
 for(int i=1;i<=n;i++){
  lrd(a[i]);sum[bel[i]=(i-1)/len+1]+=a[i];//(i-1)可以保证整块包含元素数目一样,直接用i会导致第一个块元素个数少一个,因为是从1开始存的 
 }
 rd(m);
// fk1::does();
// fk2::does();
 fk3::does();
 return 0;
}
/*cogs 264
  cogs 1316
  cogs 1317
基础分块大礼包*/