Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define mp make_pair
- ll const N = 100005;
- struct Tree
- {
- ll add = -1, sum = 0, tl, tr;
- } t[4 * N];
- void push(ll i)
- {
- if (t[i].add != -1) {
- if (t[i].tl + 1 == t[i].tr) {
- t[i].sum = t[i].add;
- }
- else {
- t[i].sum = (t[i].tr - t[i].tl) * t[i].add;
- t[i * 2].add = t[i].add;
- t[i * 2 + 1].add = t[i].add;
- }
- }
- t[i].add = -1;
- }
- void build(ll i, ll l, ll r)
- {
- t[i].tl = l, t[i].tr = r;
- if (l + 1 == r) {
- return;
- }
- build(i * 2, l, (l + r) / 2);
- build(i * 2 + 1, (l + r) / 2, r);
- }
- void update(ll i, ll l, ll r, ll x)
- {
- push(i);
- if (l <= t[i].tl && t[i].tr <= r) {
- t[i].add = x;
- push(i);
- return;
- }
- else if (t[i].tr <= l || t[i].tl >= r) {
- return;
- }
- update(i * 2, l, r, x);
- update(i * 2 + 1, l, r, x);
- t[i].sum = t[i * 2].sum + t[i * 2 + 1].sum;
- }
- ll get(ll i, ll l, ll r)
- {
- push(i);
- if (l <= t[i].tl && t[i].tr <= r) {
- return t[i].sum;
- }
- else if (t[i].tr <= l || t[i].tl >= r) {
- return 0;
- }
- return get(i * 2, l, r) + get(i * 2 + 1, l, r);
- }
- int main()
- {
- freopen("sum.in", "r", stdin);
- freopen("sum.out", "w", stdout);
- ll n, k;
- cin >> n >> k;
- build(1, 0, n);
- while (k--) {
- char tt;
- cin >> tt;
- if (tt == 'A') {
- ll l, r, z;
- cin >> l >> r >> z;
- update(1, l - 1, r, z);
- }
- else {
- ll l, r;
- cin >> l >> r;
- cout << get(1, l - 1, r) << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement