結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:48:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 420 ms / 2,000 ms |
コード長 | 22,787 bytes |
コンパイル時間 | 4,727 ms |
コンパイル使用メモリ | 216,060 KB |
最終ジャッジ日時 | 2025-01-11 11:59:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
コンパイルメッセージ
In function ‘void wt_L(long long int)’, inlined from ‘int main()’ at main.cpp:632:11: main.cpp:89:3: warning: ‘res’ may be used uninitialized [-Wmaybe-uninitialized] 89 | if(x<0){ | ^~ main.cpp: In function ‘int main()’: main.cpp:551:7: note: ‘res’ was declared here 551 | T res; | ^~~
ソースコード
#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(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');}}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[b] += ((2 * sum[b] + sz) + (2 * (sum[b] + (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<long long> t;int main(){int i, lGW8_MCT;wmem = memarr;long long 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[b] += ((2 * sum[b] + sz) + (2 * (sum[b] + (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<ll> t;// {// ll 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);// }// }// }