Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
58892 | xujindong | 课堂检测 | C++ | 通过 | 100 | 216 MS | 1460 KB | 1181 | 2022-10-10 21:38:32 |
#include<bits/stdc++.h> using namespace std; int n,m,bn,b[100005],bl[100005],br[100005]; long long a[100005],v[100005],tag[100005]; void add(int l,int r,long long x){ if(b[l]==b[r])for(int i=l;i<=r;i++)a[i]+=x,v[b[i]]+=x; else{ for(int i=l;i<=br[b[l]];i++)a[i]+=x,v[b[i]]+=x; for(int i=b[l]+1;i<b[r];i++)tag[i]+=x; for(int i=bl[b[r]];i<=r;i++)a[i]+=x,v[b[i]]+=x; } } long long query(int l,int r,long long ans=0){ if(b[l]==b[r])for(int i=l;i<=r;i++)ans+=(a[i]+tag[b[i]]); else{ for(int i=l;i<=br[b[l]];i++)ans+=(a[i]+tag[b[i]]); for(int i=b[l]+1;i<b[r];i++)ans+=(v[i]+tag[i]*(br[i]-bl[i]+1)); for(int i=bl[b[r]];i<=r;i++)ans+=(a[i]+tag[b[i]]); } return ans; } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>m; bn=sqrt(n); for(int i=1;i<=bn;i++)bl[i]=n/bn*(i-1)+1,br[i]=n/bn*i; br[bn]=n; for(int i=1;i<=bn;i++)for(int j=bl[i];j<=br[i];j++)b[j]=i; for(int i=1;i<=bn;i++)for(int j=bl[i];j<=br[i];j++)v[i]+=a[j]; for(int i=1,opt,l,r;i<=m;i++){ cin>>opt>>l; if(opt==2)cout<<query(l,l)<<'\n'; else{ long long x; cin>>r>>x,add(l,r,x); } } return 0; }