結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2024-11-20 09:44:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 194 ms / 2,000 ms |
コード長 | 1,593 bytes |
コンパイル時間 | 1,814 ms |
コンパイル使用メモリ | 173,128 KB |
実行使用メモリ | 21,952 KB |
最終ジャッジ日時 | 2024-11-20 09:44:30 |
合計ジャッジ時間 | 5,395 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long longconst int N = 2e5+100,mod=1e18+7;int n,m;int a[N];struct dat{int x,y;dat(){x=y=0;}inline void operator()(const int add,const int len){x=(x+add*y%mod*2+len*add%mod*add%mod)%mod;y=(y+add*len)%mod;}inline dat operator+(const dat z)const{dat res;res.x=(x+z.x)%mod,res.y=(y+z.y)%mod;return res;}};namespace sg{#define mid ((l+r)>>1)#define ll (x<<1)#define rr (x<<1|1)#define xx (t[x])dat t[N*4];int ad[N*4];void build(int l,int r,int x){if(l==r){cin>>t[x].y;t[x].x=t[x].y*t[x].y%mod;return;}build(l,mid,ll),build(mid+1,r,rr);t[x]=t[ll]+t[rr];}inline void add(const int l1,const int r1,int l,int r,int x,const int val){if(l>=l1&&r<=r1){ad[x]=(ad[x]+val)%mod;t[x](val,r-l+1);return;}if(l1<=mid)add(l1,r1,l,mid,ll,val);if(r1>mid)add(l1,r1,mid+1,r,rr,val);t[x]=t[ll]+t[rr];t[x](ad[x],r-l+1);}inline dat get(const int l1,const int r1,int l,int r,int x){if(l>=l1&&r<=r1)return t[x];dat res;if(l1<=mid)res=res+get(l1,r1,l,mid,ll);if(r1>mid)res=res+get(l1,r1,mid+1,r,rr);res(ad[x],min(r,r1)-max(l,l1)+1);return res;}}using namespace sg;signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;build(1,n,1);cin>>m;char op;int l,r,x;while(m--){cin>>op;if(op=='2'){cin>>l>>r;cout<<get(l,r,1,n,1).x<<'\n';}else{cin>>l>>r>>x;add(l,r,1,n,1,x);}}// int x,y,z;// cin>>x>>y>>z;// dat res;// res.x=x*x+y*y+z*z;// res.y=x+y+z;// res(3,3);// cerr<<res.x;}