Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- using namespace std;
- struct rt
- {
- ll sum;
- ll x;
- };
- rt tree[400001];
- void push(int v, int tl, int tr)
- {
- if(tree[v].x == -1)
- return;
- tree[2*v].x = tree[v].x;
- tree[2*v+1].x = tree[v].x;
- int mid = (tl+tr)/2;
- tree[2*v].sum = 1LL*(mid-tl+1)*tree[v].x;
- tree[2*v+1].sum = 1LL*(tr-mid)*tree[v].x;
- tree[v].x = -1;
- }
- void build(int v, int l, int r)
- {
- if (r > l)
- return;
- tree[v].sum = 0;
- tree[v].x = -1;
- if (l == r)
- return;
- int mid = (l+r)/2;
- int new_v = 2*v;
- build(new_v, l, mid);
- build(new_v+1, mid+1, r);
- }
- void Update(int v, int tl, int tr, int l, int r, int x)
- {
- if (l>r)
- return;
- if (l == tl && r == tr)
- {
- tree[v].x = x;
- tree[v].sum = 1LL*x*(r-l+1);
- return;
- }
- push(v, tl, tr);
- int mid = (tl+tr)/2;
- Update(2*v,tl, mid, l, min(r, mid), x);
- Update(2*v+1, mid+1, tr, max(l, mid+1), r, x);
- tree[v].sum = tree[2*v].sum+tree[2*v+1].sum;
- }
- ll sum(int v, int tl, int tr, int l, int r)
- {
- if(l > r)
- return 0;
- if (l == tl && r == tr)
- return tree[v].sum;
- push(v, tl, tr);
- int mid = (tl+tr)/2;
- return sum(2*v, tl, mid, l ,min(mid, r))+ sum(2*v+1, mid+1, tr, max(mid+1, l), r);
- }
- int main()
- {
- ifstream cin("sum.in");
- int n, q;
- cin >> n >> q;
- build(1, 1, n);
- for (int i = 0; i < q; i++)
- {
- char tp;
- int l , r;
- cin >> tp >> l >> r;
- if(tp == 'A')
- {
- int x;
- cin >> x;
- Update(1, 1, n, l, r, x);
- continue;
- }
- cout << sum(1, 1, n, l, r) << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement