Untitled
unknown
c_cpp
a year ago
3.2 kB
3
Indexable
Never
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; using ull = unsigned long long; using db = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<db, db>; using tiii = tuple<int, int, int>; using str = string; #define vt vector #define pb push_back #define eb emplace_back #define ins insert #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() #define mp make_pair #define mt make_tuple #define fi first #define se second struct segtree { struct node { ll sum; int mean; }; int size; vt<node> tree; const node zero = {0, 0}; int NO_OPERATION = 0; void init(int n) { size = 1; while (size < n) size *= 2; tree.assign(2 * size - 1, zero); } void propagate(int x, int lx, int rx) { if (tree[x].mean == NO_OPERATION) return; if (rx == lx + 1) { tree[x].sum = tree[x].mean; return; } tree[2 * x + 1].mean = tree[x].mean; tree[2 * x + 2].mean = tree[x].mean; tree[x].mean = NO_OPERATION; } void modify(int l, int r, int v, int x, int lx, int rx) { propagate(x, lx, rx); if (l >= rx || r <= lx) { return; } if (l <= lx && rx <= r) { tree[x].mean = v; tree[x].sum = (rx - lx) * v; return; } int m = (lx + rx) / 2; modify(l, r, v, 2 * x + 1, lx, m); modify(l, r, v, 2 * x + 2, m, rx); tree[x].sum = tree[2 * x + 1].sum + tree[2 * x + 2].sum; } void modify(int l, int r, int v) { modify(l, r, v, 0, 0, size); } ll sum(int l, int r, int x, int lx, int rx) { if (l >= rx || r <= lx) { return 0; } if (l <= lx && rx <= r) { return tree[x].sum; } int m = (lx + rx) / 2; ll s1 = sum(l, r, 2 * x + 1, lx, m); ll s2 = sum(l, r, 2 * x + 2, m, rx); return s1 + s2; } ll sum(int l, int r) { return sum(l, r, 0, 0, size); } }; void solve() { int n, k; cin >> n >> k; segtree st; st.init(n); while (k--) { char c; cin >> c; if (c == 'A') { int l, r, x; cin >> l >> r >> x; l--; st.modify(l, r, x); // for (auto i : st.tree) { // cout << '{' << i.mean << ", " << i.sum << "} " ; // } // cout << endl; } else { int l, r; cin >> l >> r; l--; cout << st.sum(l, r) << endl; } } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }