結果

問題 No.1099 Range Square Sum
ユーザー chineristAC
提出日時 2020-06-27 01:04:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,191 ms / 2,000 ms
コード長 2,368 bytes
コンパイル時間 1,087 ms
コンパイル使用メモリ 102,600 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 03:31:22
合計ジャッジ時間 11,187 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<random>
#include<stdio.h>
using namespace std;
typedef long long ll;
long long Mod(long long val, long long m) {
long long res = val % m;
if (res < 0) res += m;
return res;
}
vector<ll> A(200000);
ll Adata[200000];
ll RSQdata[200000];
ll RSSQdata[200000];
ll n;
ll RSQ(ll l,ll r){
ll id=l;
ll L,q,R;
ll res=0;
while (r>=id){
L=id;
q=id/n;
R=min((q+1)*n-1,r);
if (R-L+1==n){
res+=RSQdata[q];
}
else{
for (ll i=L;i<R+1;i++){
res+=A[i]+Adata[q];
}
}
id=R+1;
}
return res;
}
void update(ll l,ll r,ll x){
ll id=l;
ll L,q,R;
while (r>=id){
L=id;
q=id/n;
R=min((q+1)*n-1,r);
if (R-L+1==n){
Adata[q]+=x;
RSQdata[q]+=x*n;
RSSQdata[q]+=2*x*RSQ(L,R)-n*x*x;
}
else{
for (ll i=L;i<R+1;i++){
A[i]+=x;
}
RSQdata[q]+=(R-L+1)*x;
RSSQdata[q]+=2*x*RSQ(L,R)-(R-L+1)*x*x;
}
id=R+1;
}
}
ll RSSQ(ll l,ll r){
ll id=l;
ll L,q,R;
ll res=0;
while (r>=id){
L=id;
q=id/n;
R=min((q+1)*n-1,r);
if (R-L+1==n){
res+=RSSQdata[q];
}
else{
for (ll i=L;i<R+1;i++){
res+=(A[i]+Adata[q])*(A[i]+Adata[q]);
}
}
id=R+1;
}
return res;
}
int main(){
ll N;
scanf("%lld",&N);
for (ll i=0;i<N;i++){
scanf("%lld",&A[i]);
}
while (N>=n*n){
n+=1;
}
n-=1;
for (ll i=0;i<N;i++){
ll q=i/n;
RSQdata[q]+=A[i];
RSSQdata[q]+=A[i]*A[i];
}
ll Q;
scanf("%lld",&Q);
while (Q--){
int q;
scanf("%lld",&q);
if (q==1){
ll l,r,x;
scanf("%lld",&l);
scanf("%lld",&r);
scanf("%lld",&x);
l-=1;r-=1;
update(l,r,x);
}
else{
ll l,r;
scanf("%lld",&l);
scanf("%lld",&r);
l-=1;r-=1;
ll ans=RSSQ(l,r);
cout<<ans<<endl;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0