Untitled
plain_text
2 months ago
2.9 kB
2
Indexable
Never
/****************************************************************************** Welcome to GDB Online. GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS Code, Compile, Run and Debug online from anywhere in world. *******************************************************************************/ #include <iostream> #include <vector> using namespace std; const int N = 300010; const int S = 320; #define ll long long #define pb push_back struct Block { ll sum; int upd; int tl, tr; vector <int> a; Block(){} Block(int l, int r) { sum = 0; upd = -1; tl = l; tr = r; a.resize(r - l + 1, 0); } void push() { if (upd != -1) { for (int i = 0; i < a.size(); i++) a[i] = upd; } upd = -1; } ll getsum(int l, int r) { push(); ll res = 0; for (int i = l; i <= r; i++) res += a[i]; return res; } void update(int l, int r, int x) { push(); for (int i = l; i <= r; i++) { sum += x - a[i]; a[i] = x; } } }; vector <Block> s; int b[N]; int n, q; ll getsum(int l, int r) { int block1 = b[l]; int block2 = b[r]; if (block1 == block2) return s[block1].getsum(l - s[block1].tl, r - s[block1].tl); ll res = s[block1].getsum(l - s[block1].tl, s[block1].tr - s[block1].tl); res += s[block2].getsum(0, r - s[block2].tl); for (int i = block1 + 1; i < block2; i++) res += s[i].sum; return res; } void update(int l, int r, int x) { int b1 = b[l]; int b2 = b[r]; if (b1 == b2) s[b1].update(l - s[b1].tl, r - s[b1].tl, x); else { s[b1].update(l - s[b1].tl, s[b1].tr - s[b1].tl, x); s[b2].update(0, r - s[b2].tl, x); for (int i = b1 + 1; i < b2; i++) { s[i].upd = x; s[i].sum = 1ll * (s[i].tr - s[i].tl + 1) * x; } } } int main() { freopen("sum.in", "r", stdin); freopen("sum.out", "w", stdout); cin >> n >> q; for (int i = 0; i < n; i++) b[i] = i / S; int prev = 0; for (int i = 0; i < n; i++) { if (i == n - 1 || b[i] != b[i + 1]) { s.pb(Block(prev, i)); prev = i + 1; } } for (int i = 1; i <= q; i++) { char ch; cin >> ch; if (ch == 'Q') { int l, r; cin >> l >> r; l--; r--; cout << getsum(l, r) << "\n"; } else { int l, r, x; cin >> l >> r >> x; l--; r--; update(l, r, x); } } return 0; }