結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 21:45:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 3,073 bytes |
コンパイル時間 | 1,093 ms |
コンパイル使用メモリ | 118,068 KB |
実行使用メモリ | 18,688 KB |
最終ジャッジ日時 | 2024-07-04 20:30:30 |
合計ジャッジ時間 | 4,540 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<cassert>#include<complex>#include<numeric>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;constexpr ll mod = 998244353;const ll INF = mod * mod;typedef pair<int, int>P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)#define all(v) (v).begin(),(v).end()typedef pair<ll, ll> LP;typedef long double ld;typedef pair<ld, ld> LDP;const ld eps = 1e-8;const ld pi = acosl(-1.0);struct SegT {private:int n; vector<ll> node, lazy;vector<ll> node2;public:SegT(vector<ll> a) {int sz = a.size();n = 1;while (n < sz)n <<= 1;node.resize(2 * n - 1, 0);node2.resize(2 * n - 1, 0);lazy.resize(2 * n - 1, 0);rep(i, sz) {node[i + n - 1] = a[i];}per(i, n - 1) {node[i] = node[2 * i + 1] + node[2 * i + 2];node2[i] = node2[2 * i + 1] + node2[2 * i + 2] + node[2 * i + 1] * node[2 * i + 2];}}void eval(int k, int l, int r) {ll len = r - l;node2[k] += (len - 1)*node[k]*lazy[k];node2[k] += len*(len - 1) / 2 * lazy[k] * lazy[k];node[k] += len*lazy[k];if (r - l > 1) {lazy[2 * k + 1] += lazy[k];lazy[2 * k + 2] += lazy[k];}lazy[k] = 0;}void add(ll x, int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0)r = n;eval(k, l, r);if (r <= a || b <= l)return;if (a <= l && r <= b) {lazy[k] += x; eval(k, l, r);}else {add(x, a, b, k * 2 + 1, l, (l + r) / 2);add(x, a, b, k * 2 + 2, (l + r) / 2, r);node[k] = node[2 * k + 1] + node[2 * k + 2];node2[k] = node2[2 * k + 1] + node2[2 * k + 2] + node[2 * k + 1] * node[2 * k + 2];}}LP query(int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0)r = n;eval(k, l, r);if (r <= a || b <= l)return{ 0,0 };if (a <= l && r <= b)return{ node[k],node2[k] };else {LP vl = query(a, b, k * 2 + 1, l, (l + r) / 2);LP vr = query(a, b, k * 2 + 2, (l + r) / 2, r);return{ vl.first + vr.first,vl.second + vr.second + vl.first*vr.first };}}};void solve() {int n; cin >> n;vector<ll> a(n);rep(i, n)cin >> a[i];SegT st(a);int q; cin >> q;rep(i, q) {int t, l, r; cin >> t >> l >> r; l--; r--;if (t == 1) {int x; cin >> x;st.add(x, l, r + 1);}else {LP p = st.query(l, r + 1);ll ans = p.first*p.first - 2 * p.second;cout << ans << "\n";}}}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(7);//init_f();//init();//int t; cin >> t; rep(i, t)solve();stopreturn 0;}