結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2024-03-27 19:49:28 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 288 ms / 2,000 ms |
コード長 | 2,427 bytes |
コンパイル時間 | 2,770 ms |
コンパイル使用メモリ | 209,956 KB |
実行使用メモリ | 19,984 KB |
最終ジャッジ日時 | 2024-09-30 14:34:58 |
合計ジャッジ時間 | 6,957 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
import std, core.bitop;bool chmin(T)(ref T SE, T MI) { if (SE > MI) { SE = MI; return true; } else { return false; } }bool chmax(T)(ref T SE, T MI) { if (SE < MI) { SE = MI; return true; } else { return false; } }int lowerBound(T)(T[] SE, T MI) { int lo = -1, hi = cast(int)(SE.length); while (hi - lo > 1) { int mid = lo + hi >> 1; (SE[mid] < MI ? lo : hi) = mid; } return hi; }int upperBound(T)(T[] SE, T MI) { int lo = -1, hi = cast(int)(SE.length); while (hi - lo > 1) { int mid = lo + hi >> 1; (SE[mid] > MI ? hi : lo) = mid; } return hi; }struct SegmentTree {int N;long[] dat0, dat1;int[] laz;this(int[] A) {int n = cast(int)(A.length);for (N = 1; N < n; N <<= 1) {}dat0 = new long[N << 1];dat1 = new long[N << 1];laz = new int[N << 1];foreach (i; 0 .. n) {dat0[i + N] = A[i];dat1[i + N] = 1L * A[i] * A[i];}foreach_reverse (i; 0 .. N) {dat0[i] = dat0[i << 1] + dat0[i << 1 | 1];dat1[i] = dat1[i << 1] + dat1[i << 1 | 1];}}void propagate(int i, int w) {if (i < N) {laz[i << 1] += laz[i];laz[i << 1 | 1] += laz[i];}dat1[i] += 2L * laz[i] * dat0[i] + 1L * laz[i] * laz[i] * w;dat0[i] += 1L * laz[i] * w;laz[i] = 0;}void rangeAdd(int L, int R, int x, int i, int l, int r) {propagate(i, r - l);if (r <= L || R <= l) {return;}if (L <= l && r <= R) {laz[i] += x;propagate(i, r - l);} else {int m = l + r >> 1;rangeAdd(L, R, x, i << 1, l, m);rangeAdd(L, R, x, i << 1 | 1, m, r);dat0[i] = dat0[i << 1] + dat0[i << 1 | 1];dat1[i] = dat1[i << 1] + dat1[i << 1 | 1];}}void rangeAdd(int L, int R, int x) {rangeAdd(L, R, x, 1, 0, N);}long rangeSquareSum(int L, int R, int i, int l, int r) {propagate(i, r - l);if (r <= L || R <= l) {return 0;}if (L <= l && r <= R) {return dat1[i];}int m = l + r >> 1;return rangeSquareSum(L, R, i << 1, l, m) + rangeSquareSum(L, R, i << 1 | 1, m, r);}long rangeSquareSum(int L, int R) {return rangeSquareSum(L, R, 1, 0, N);}};void main() {int N;readf("%s\n", N);auto A = readln.chomp.split.to!(int[]);int Q;readf("%s\n", Q);auto ST = new SegmentTree(A);while (Q--) {int op;readf("%s ", op);if (op == 1) {int l, r, x;readf("%s %s %s\n", l, r, x);ST.rangeAdd(--l, r, x);}if (op == 2) {int l, r;readf("%s %s\n", l, r);ST.rangeSquareSum(--l, r).writeln;}}}