Untitled

mail@pastecode.io avatarunknown
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;
}