結果
| 問題 | No.1099 Range Square Sum |
| ユーザー |
 LayCurse
|
| 提出日時 | 2020-06-26 22:42:38 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 23,341 bytes |
| コンパイル時間 | 2,588 ms |
| コンパイル使用メモリ | 215,124 KB |
| 実行使用メモリ | 38,596 KB |
| 最終ジャッジ日時 | 2023-09-18 06:22:09 |
| 合計ジャッジ時間 | 7,798 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,384 KB |
| testcase_01 | AC | 2 ms
5,360 KB |
| testcase_02 | AC | 2 ms
5,436 KB |
| testcase_03 | AC | 2 ms
5,396 KB |
| testcase_04 | AC | 2 ms
5,380 KB |
| testcase_05 | AC | 2 ms
5,420 KB |
| testcase_06 | AC | 2 ms
5,532 KB |
| testcase_07 | WA | - |
| testcase_08 | AC | 2 ms
5,572 KB |
| testcase_09 | AC | 2 ms
5,396 KB |
| testcase_10 | AC | 2 ms
5,456 KB |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
コンパイルメッセージ
関数 ‘void wt_L(__int128)’ 内,
inlined from ‘int main()’ at main.cpp:676:11:
main.cpp:135:6: 警告: ‘res’ may be used uninitialized [-Wmaybe-uninitialized]
135 | x=-x;
| ~^~~
main.cpp: 関数 ‘int main()’ 内:
main.cpp:595:7: 備考: ‘res’ はここで定義されています
595 | T res;
| ^~~
メンバ関数 ‘T segtree_tmp<T>::getSum2(int, int) [with T = __int128]’ 内,
inlined from ‘int main()’ at main.cpp:675:22:
main.cpp:634:11: 警告: ‘tmp’ may be used uninitialized [-Wmaybe-uninitialized]
634 | res = res + tmp;
| ~~~~^~~~~~~~~~~
main.cpp: 関数 ‘int main()’ 内:
main.cpp:596:7: 備考: ‘tmp’ はここで定義されています
596 | T tmp;
| ^~~
ソースコード
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class S, class T> inline S min_L(S a,T b){
return a<=b?a:b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
inline int my_getchar_unlocked(){
static char buf[1048576];
static int s = 1048576;
static int e = 1048576;
if(s == e && e == 1048576){
e = fread_unlocked(buf, 1, 1048576, stdin);
s = 0;
}
if(s == e){
return EOF;
}
return buf[s++];
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = my_getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = my_getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline int rd_int(void){
int x;
rd(x);
return x;
}
struct MY_WRITER{
char buf[1048576];
int s;
int e;
MY_WRITER(){
s = 0;
e = 1048576;
}
~MY_WRITER(){
if(s){
fwrite_unlocked(buf, 1, s, stdout);
}
}
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
MY_WRITER_VAR.s = 0;
}
MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
my_putchar_unlocked(a);
}
inline void wt_L(int x){
int s=0;
int m=0;
char f[10];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(long long x){
int s=0;
int m=0;
char f[20];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(__int128_t x){
int s=0;
int m=0;
char f[40];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
template<class T> struct segtree_tmp{
int N;
int logN;
T *sum;
T *mn;
T *sum2;
int *mnind;
T *fixval;
char *fixed;
T *addval;
void malloc(int maxN, int once = 0){
int i;
for(i=1;i<maxN;i*=2){
;
}
sum = new T[2*i];
sum2 = new T[2*i];
mn = new T[2*i];
mnind = new int[2*i];
fixval = new T[i];
addval = new T[i];
fixed = new char[i];
if(once){
setN(maxN);
}
}
void walloc(int maxN, int once = 0, void **mem = &wmem){
int i;
for(i=1;i<maxN;i*=2){
;
}
walloc1d(&sum, 2*i, mem);
walloc1d(&sum2, 2*i, mem);
walloc1d(&mn, 2*i, mem);
walloc1d(&mnind, 2*i, mem);
walloc1d(&fixval, i, mem);
walloc1d(&addval, i, mem);
walloc1d(&fixed, i, mem);
if(once){
setN(maxN);
}
}
void free(void){
delete [] sum;
delete [] sum2;
delete [] mn;
delete [] mnind;
delete [] fixval;
delete [] addval;
delete [] fixed;
}
T& operator[](int i){
return sum[N+i];
}
void setN(int n, int zerofill = 1, int dobuild = 1){
int i;
for(i=1,logN=0;i<n;i*=2,logN++){
;
}
N = i;
if(zerofill){
for(i=(0);i<(N);i++){
sum[N+i] = 0;
}
}
if(dobuild){
build();
}
}
void build(void){
int i;
for(i=(0);i<(N);i++){
mn[N+i] = sum[N+i];
mnind[N+i] = i;
sum2[N+i] = sum[N+i] * sum[N+i];
}
for(i=N-1;i;i--){
sum[i] = sum[2*i] + sum[2*i+1];
sum2[i] = sum2[2*i] + sum2[2*i+1];
if(mn[2*i] <= mn[2*i+1]){
mn[i] = mn[2*i];
mnind[i] = mnind[2*i];
}
else{
mn[i] = mn[2*i+1];
mnind[i] = mnind[2*i+1];
}
}
int tU__gIr_ = N;
for(i=(1);i<(tU__gIr_);i++){
fixed[i] = 0;
}
int V9aVTaxx = N;
for(i=(1);i<(V9aVTaxx);i++){
addval[i] = 0;
}
}
inline void push_one(int a, int sz, int st){
if(fixed[a]){
if(sz > 1){
fixed[a*2] = fixed[a*2+1] = 1;
fixval[a*2] = fixval[a*2+1] = fixval[a];
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
else{
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
fixed[a] = 0;
addval[a] = 0;
return;
}
if(addval[a] != 0){
if(sz > 1){
if(fixed[a*2]){
fixval[a*2] += addval[a];
}
else{
addval[a*2] += addval[a];
}
if(fixed[a*2+1]){
fixval[a*2+1] += addval[a];
}
else{
addval[a*2+1] += addval[a];
}
sum2[a*2] += ((2 * sum[a*2] + sz) + (2 * (sum[a*2] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
sum2[a*2+1] += ((2 * sum[a*2+1] + sz) + (2 * (sum[a*2+1] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
else{
sum2[a*2] += ((2 * sum[a*2] + sz) + (2 * (sum[a*2] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
sum2[a*2+1] += ((2 * sum[a*2+1] + sz) + (2 * (sum[a*2+1] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
addval[a] = 0;
return;
}
}
inline void push(int a){
int i;
int aa = a - N;
int nd;
int sz;
int st;
for(i=logN;i;i--){
nd = a>>i;
sz = 1<<(i-1);
st = 2 * sz * (aa>>i);
push_one(nd, sz, st);
}
}
inline void build(int a){
int sz = 1;
int st = a - N;
while(a > 1){
if(a%2){
st += sz;
}
a /= 2;
sz *= 2;
if(fixed[a]){
sum[a] = sz * fixval[a];
mn[a] = fixval[a];
}
else{
sum[a] = sum[a*2] + sum[a*2+1];
sum2[a] = sum2[a*2] + sum2[a*2+1];
if(mn[a*2] <= mn[a*2+1]){
mn[a] = mn[a*2];
mnind[a] = mnind[a*2];
}
else{
mn[a] = mn[a*2+1];
mnind[a] = mnind[a*2+1];
}
if(addval[a] != 0){
mn[a] += addval[a];
sum2[a] += ((2 * sum[a] + sz) + (2 * (sum[a] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
sum[a] += sz * addval[a];
}
}
}
}
inline void change(int a, int b, T val){
int sz = 1;
int aa;
int bb;
int st_a = a;
int st_b = b;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] = mn[a] = val;
sum2[a] = val * val;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
sum[b] = mn[b] = val;
sum2[b] = val*val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
fixed[a]=1;
fixval[a]=val;
sum[a] = sz * val;
mn[a] = val;
mnind[a] = st_a;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
fixed[b]=1;
fixval[b]=val;
sum[b] = sz * val;
mn[b] = val;
mnind[b] = st_b;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline void add(int a, int b, T val){
int sz = 1;
int aa;
int bb;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] += val;
sum2[a] = sum[a] * sum[a];
mn[a] += val;
a++;
}
if(b%2){
b--;
sum[b] += val;
sum2[b] = sum[b] * sum[b];
mn[b] += val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
if(fixed[a]){
fixval[a] += val;
}
else{
addval[a] += val;
}
sum2[a] += ((2 * sum[a] + sz) + (2 * (sum[a] + (val - 1) * sz) + sz)) * val / 2;
sum[a] += sz * val;
mn[a] += val;
a++;
}
if(b%2){
b--;
if(fixed[b]){
fixval[b] += val;
}
else{
addval[b] += val;
}
sum2[a] += ((2 * sum[a] + sz) + (2 * (sum[a] + (val - 1) * sz) + sz)) * val / 2;
sum[b] += sz * val;
mn[b] += val;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline pair<T,int> getMin(int a, int b){
pair<T,int> res;
pair<T,int> tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res =min_L(res, make_pair(mn[a], mnind[a]));
}
else{
res = make_pair(mn[a], mnind[a]);
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp =min_L(make_pair(mn[b], mnind[b]), tmp);
}
else{
tmp = make_pair(mn[b], mnind[b]);
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res =min_L(res, tmp);
return res;
}
return res;
}
inline T getMinVal(int a, int b){
T res;
T tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res =min_L(res, mn[a]);
}
else{
res = mn[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp =min_L(mn[b], tmp);
}
else{
tmp = mn[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res =min_L(res, tmp);
return res;
}
return res;
}
inline int getMinInd(int a, int b){
return getMin(a,b).second;
}
inline T getSum(int a, int b){
T res;
T tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res = res + sum[a];
}
else{
res = sum[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp = sum[b] + tmp;
}
else{
tmp = sum[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res = res + tmp;
return res;
}
return res;
}
inline T getSum2(int a, int b){
T res;
T tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res = res + sum2[a];
}
else{
res = sum2[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp = sum2[b] + tmp;
}
else{
tmp = sum2[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res = res + tmp;
return res;
}
return res;
}
}
;
int N;
int A[200000];
int T;
int L;
int R;
int X;
segtree_tmp<__int128_t> t;
int main(){
int i, lGW8_MCT;
wmem = memarr;
__int128_t res;
rd(N);
{
int o3WxPXbE;
for(o3WxPXbE=(0);o3WxPXbE<(N);o3WxPXbE++){
rd(A[o3WxPXbE]);
}
}
t.malloc(N,1);
for(i=(0);i<(N);i++){
t.add(i,i+1,A[i]);
}
int XNa8avth = rd_int();
for(lGW8_MCT=(0);lGW8_MCT<(XNa8avth);lGW8_MCT++){
rd(T);
rd(L);
rd(R);
if(T==1){
rd(X);
}
if(T==1){
t.add(L-1,R,X);
}
else{
res = t.getSum2(L-1,R);
wt_L(res);
wt_L('\n');
}
}
return 0;
}
// cLay varsion 20200509-1
// --- original code ---
// template<class T>
// struct segtree_tmp{
// int N, logN;
// T *sum, *mn, *sum2;
// int *mnind;
//
// T *fixval; char *fixed;
// T *addval;
//
// void malloc(int maxN, int once = 0){
// int i;
// for(i=1;i<maxN;i*=2);
//
// sum = new T[2*i];
// sum2 = new T[2*i];
// mn = new T[2*i];
// mnind = new int[2*i];
// fixval = new T[i];
// addval = new T[i];
// fixed = new char[i];
//
// if(once) setN(maxN);
// }
//
// void walloc(int maxN, int once = 0, void **mem = &wmem){
// int i;
// for(i=1;i<maxN;i*=2);
//
// walloc1d(&sum, 2i, mem);
// walloc1d(&sum2, 2i, mem);
// walloc1d(&mn, 2i, mem);
// walloc1d(&mnind, 2i, mem);
// walloc1d(&fixval, i, mem);
// walloc1d(&addval, i, mem);
// walloc1d(&fixed, i, mem);
//
// if(once) setN(maxN);
// }
//
// void free(void){
// delete [] sum;
// delete [] sum2;
// delete [] mn;
// delete [] mnind;
// delete [] fixval;
// delete [] addval;
// delete [] fixed;
// }
//
// T& operator[](int i){
// return sum[N+i];
// }
//
// void setN(int n, int zerofill = 1, int dobuild = 1){
// int i;
// for(i=1,logN=0;i<n;i*=2,logN++);
// N = i;
// if(zerofill) rep(i,N) sum[N+i] = 0;
// if(dobuild) build();
// }
//
// void build(void){
// int i;
// rep(i,N){
// mn[N+i] = sum[N+i], mnind[N+i] = i;
// sum2[N+i] = sum[N+i] * sum[N+i];
// }
// for(i=N-1;i;i--){
// sum[i] = sum[2*i] + sum[2*i+1];
// sum2[i] = sum2[2*i] + sum2[2*i+1];
// if(mn[2*i] <= mn[2*i+1]){
// mn[i] = mn[2*i];
// mnind[i] = mnind[2*i];
// } else {
// mn[i] = mn[2*i+1];
// mnind[i] = mnind[2*i+1];
// }
// }
// REP(i,1,N) fixed[i] = 0;
// REP(i,1,N) addval[i] = 0;
// }
//
// inline void push_one(int a, int sz, int st){
// if(fixed[a]){
// if(sz > 1){
// fixed[a*2] = fixed[a*2+1] = 1;
// fixval[a*2] = fixval[a*2+1] = fixval[a];
// sum[a*2] = sum[a*2+1] = sz * fixval[a];
// mn[a*2] = mn[a*2+1] = fixval[a];
// mnind[a*2] = st;
// mnind[a*2+1] = st + sz;
// } else {
// sum[a*2] = sum[a*2+1] = sz * fixval[a];
// mn[a*2] = mn[a*2+1] = fixval[a];
// mnind[a*2] = st;
// mnind[a*2+1] = st + sz;
// }
// fixed[a] = 0;
// addval[a] = 0;
// return;
// }
// if(addval[a] != 0){
// // wt("---",a,addval[a],sz);
// if(sz > 1){
// if(fixed[a*2]) fixval[a*2] += addval[a];
// else addval[a*2] += addval[a];
// if(fixed[a*2+1]) fixval[a*2+1] += addval[a];
// else addval[a*2+1] += addval[a];
// // wt("------",sum2[a*2],sum2[a*2+1]);
// sum2[a*2] += ((2 * sum[a*2] + sz) + (2 * (sum[a*2] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
// sum2[a*2+1] += ((2 * sum[a*2+1] + sz) + (2 * (sum[a*2+1] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
// // wt("----->",sum2[a*2],sum2[a*2+1]);
// sum[a*2] += sz * addval[a];
// sum[a*2+1] += sz * addval[a];
// mn[a*2] += addval[a];
// mn[a*2+1] += addval[a];
// } else {
// // wt("------",sum2[a*2],sum2[a*2+1]);
// sum2[a*2] += ((2 * sum[a*2] + sz) + (2 * (sum[a*2] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
// sum2[a*2+1] += ((2 * sum[a*2+1] + sz) + (2 * (sum[a*2+1] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
// // wt("----->",sum2[a*2],sum2[a*2+1]);
// sum[a*2] += sz * addval[a];
// sum[a*2+1] += sz * addval[a];
// mn[a*2] += addval[a];
// mn[a*2+1] += addval[a];
// }
// addval[a] = 0;
// return;
// }
// }
//
// inline void push(int a){
// int i, aa = a - N, nd, sz, st;
// for(i=logN;i;i--){
// nd = a>>i;
// sz = 1<<(i-1);
// st = 2 * sz * (aa>>i);
// push_one(nd, sz, st);
// }
// }
//
// inline void build(int a){
// int sz = 1, st = a - N;
// while(a > 1){
// if(a%2) st += sz;
// a /= 2;
// sz *= 2;
// if(fixed[a]){
// sum[a] = sz * fixval[a];
// mn[a] = fixval[a];
// } else {
// sum[a] = sum[a*2] + sum[a*2+1];
// sum2[a] = sum2[a*2] + sum2[a*2+1];
// if(mn[a*2] <= mn[a*2+1]){
// mn[a] = mn[a*2];
// mnind[a] = mnind[a*2];
// } else {
// mn[a] = mn[a*2+1];
// mnind[a] = mnind[a*2+1];
// }
// if(addval[a] != 0){
// mn[a] += addval[a];
// sum2[a] += ((2 * sum[a] + sz) + (2 * (sum[a] + (addval[a] - 1) * sz) + sz)) * addval[a] / 2;
// sum[a] += sz * addval[a];
// }
// }
// }
// }
//
// inline void change(int a, int b, T val){
// int sz = 1, aa, bb, st_a = a, st_b = b;
// if(a >= b) return;
//
// aa = (a += N);
// bb = (b += N);
// push(a); push(b-1);
//
// if(a%2){
// sum[a] = mn[a] = val;
// sum2[a] = val * val;
// a++;
// st_a += sz;
// }
// if(b%2){
// b--;
// st_b -= sz;
// sum[b] = mn[b] = val;
// sum2[b] = val*val;
// }
// a /= 2;
// b /= 2;
//
// while(a < b){
// sz *= 2;
// if(a%2){
// fixed[a]=1, fixval[a]=val;
// sum[a] = sz * val;
// mn[a] = val;
// mnind[a] = st_a;
// a++;
// st_a += sz;
// }
// if(b%2){
// b--;
// st_b -= sz;
// fixed[b]=1, fixval[b]=val;
// sum[b] = sz * val;
// mn[b] = val;
// mnind[b] = st_b;
// }
// a /= 2;
// b /= 2;
// }
//
// build(aa);
// build(bb-1);
// }
//
// inline void add(int a, int b, T val){
// int sz = 1, aa, bb;
// if(a >= b) return;
//
// aa = (a += N);
// bb = (b += N);
// push(a); push(b-1);
//
// if(a%2){
// sum[a] += val;
// sum2[a] = sum[a] * sum[a];
// mn[a] += val;
// a++;
// }
// if(b%2){
// b--;
// sum[b] += val;
// sum2[b] = sum[b] * sum[b];
// mn[b] += val;
// }
// a /= 2;
// b /= 2;
//
// while(a < b){
// sz *= 2;
// if(a%2){
// if(fixed[a]) fixval[a] += val; else addval[a] += val;
// sum2[a] += ((2 * sum[a] + sz) + (2 * (sum[a] + (val - 1) * sz) + sz)) * val / 2;
// sum[a] += sz * val;
// mn[a] += val;
// a++;
// }
// if(b%2){
// b--;
// if(fixed[b]) fixval[b] += val; else addval[b] += val;
// sum2[a] += ((2 * sum[a] + sz) + (2 * (sum[a] + (val - 1) * sz) + sz)) * val / 2;
// sum[b] += sz * val;
// mn[b] += val;
// }
// a /= 2;
// b /= 2;
// }
//
// build(aa);
// build(bb-1);
// }
//
// inline pair<T,int> getMin(int a, int b){
// pair<T,int> res, tmp;
// int fga = 0, fgb = 0;
//
// a += N;
// b += N;
// push(a); push(b-1);
//
// while(a < b){
// if(a%2){
// if(fga){
// res = min(res, make_pair(mn[a], mnind[a]));
// } else {
// res = make_pair(mn[a], mnind[a]);
// fga = 1;
// }
// a++;
// }
// if(b%2){
// b--;
// if(fgb){
// tmp = min(make_pair(mn[b], mnind[b]), tmp);
// } else {
// tmp = make_pair(mn[b], mnind[b]);
// fgb = 1;
// }
// }
// a /= 2;
// b /= 2;
// }
// if(fga==1 && fgb==0) return res;
// if(fga==0 && fgb==1) return tmp;
// if(fga==1 && fgb==1){
// res = min(res, tmp);
// return res;
// }
// return res;
// }
//
// inline T getMinVal(int a, int b){
// T res, tmp;
// int fga = 0, fgb = 0;
//
// a += N;
// b += N;
// push(a); push(b-1);
//
// while(a < b){
// if(a%2){
// if(fga){
// res = min(res, mn[a]);
// } else {
// res = mn[a];
// fga = 1;
// }
// a++;
// }
// if(b%2){
// b--;
// if(fgb){
// tmp = min(mn[b], tmp);
// } else {
// tmp = mn[b];
// fgb = 1;
// }
// }
// a /= 2;
// b /= 2;
// }
// if(fga==1 && fgb==0) return res;
// if(fga==0 && fgb==1) return tmp;
// if(fga==1 && fgb==1){
// res = min(res, tmp);
// return res;
// }
// return res;
// }
//
// inline int getMinInd(int a, int b){
// return getMin(a,b).second;
// }
//
// inline T getSum(int a, int b){
// T res, tmp;
// int fga = 0, fgb = 0;
//
// a += N;
// b += N;
// push(a); push(b-1);
//
// while(a < b){
// if(a%2){
// if(fga){
// res = res + sum[a];
// } else {
// res = sum[a];
// fga = 1;
// }
// a++;
// }
// if(b%2){
// b--;
// if(fgb){
// tmp = sum[b] + tmp;
// } else {
// tmp = sum[b];
// fgb = 1;
// }
// }
// a /= 2;
// b /= 2;
// }
// if(fga==1 && fgb==0) return res;
// if(fga==0 && fgb==1) return tmp;
// if(fga==1 && fgb==1){
// res = res + tmp;
// return res;
// }
// return res;
// }
//
// inline T getSum2(int a, int b){
// T res, tmp;
// int fga = 0, fgb = 0;
//
// a += N;
// b += N;
// push(a); push(b-1);
//
// while(a < b){
// if(a%2){
// if(fga){
// res = res + sum2[a];
// } else {
// res = sum2[a];
// fga = 1;
// }
// a++;
// }
// if(b%2){
// b--;
// if(fgb){
// tmp = sum2[b] + tmp;
// } else {
// tmp = sum2[b];
// fgb = 1;
// }
// }
// a /= 2;
// b /= 2;
// }
// if(fga==1 && fgb==0) return res;
// if(fga==0 && fgb==1) return tmp;
// if(fga==1 && fgb==1){
// res = res + tmp;
// return res;
// }
// return res;
// }
// };
//
// int N, A[2d5];
// int T, L, R, X;
// segtree_tmp<__int128_t> t;
// {
// __int128_t res;
// rd(N,A(N));
// t.malloc(N,1);
// rep(i,N) t.add(i,i+1,A[i]);
// // rep(i,N) wt(i,t.getSum2(i,i+1));
// // wt(t.getSum2(0,N));
// // t.add(0,N,10);
// // rep(i,N) wt(i,t.getSum2(i,i+1));
// // wt(t.getSum2(0,N));
// REP(rd_int()){
// rd(T,L,R);
// if(T==1) rd(X);
// if(T==1){
// t.add(L-1,R,X);
// } else {
// res = t.getSum2(L-1,R);
// wt(res);
// }
// }
// }