Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <bits/stdc++.h>
- using namespace std;
- #define amen ;
- typedef long long ll;
- typedef double d;
- typedef long double lld;
- typedef string str;
- const ll neutral = 1e8;
- struct node
- {
- ll left, right, add = neutral, value;
- node * left_children, * right_children;
- };
- node* build(ll left, ll right)
- {
- if (left > right)
- return nullptr;
- node * res = new node;
- res->left = left;
- res->right = right;
- res->add = neutral;
- res->value = 0;
- if (left == right)
- {
- res->left_children = nullptr;
- res->right_children = nullptr;
- }
- else
- {
- ll m = (left + right) / 2;
- res->left_children = build(left, m);
- res->right_children = build(m+1, right);
- }
- return res;
- }
- void push(node * root)
- {
- if (root->add == neutral)
- return;
- root->value = root->add * (root->right - root->left + 1);
- if (root->left == root->right)
- {
- root->add = neutral;
- return;
- }
- root->left_children->add = root->add;
- root->right_children->add = root->add;
- root->add = neutral;
- return;
- }
- void update_line(node * root, ll left, ll right, ll add)
- {
- if (left > root->right || right < root->left)
- return;
- if (left<= root->left && root->right <= right)
- {
- root->add = add;
- return;
- }
- push(root);
- update_line(root->left_children, left, right, add);
- update_line(root->right_children, left, right, add);
- push(root->left_children);
- push(root->right_children);
- root->value = root->left_children->value + root->right_children->value;
- }
- ll sum(node * root, ll left, ll right)
- {
- if (left > root->right || right < root->left)
- return 0;
- if (left<= root->left && root->right <= right)
- {
- push(root);
- return root->value;
- }
- push(root);
- return sum(root->left_children, left, right) + sum(root->right_children, left, right);
- }
- void cout_tree(node * root)
- {
- cout << root->left << " " << root->right << " add: " << root->add << " value : " << root->value << endl;
- if (root->left == root->right)
- {
- return;
- }
- cout_tree(root->left_children);
- cout_tree(root->right_children);
- }
- int main()
- {
- freopen("sum.in", "r", stdin);
- freopen("sum.out", "w", stdout);
- ll n, k;
- cin >> n >> k;
- node * root = build(1, n);
- vector <ll> ans;
- for (ll i = 0; i < k; i++)
- {
- char c;
- cin >> c;
- if (c == 'A')
- {
- ll l, r, x;
- cin >> l >> r >> x;
- update_line(root, l, r, x);
- }
- else
- {
- ll l, r;
- cin >> l >> r;
- ans.push_back(sum(root, l, r));
- }
- //cout_tree(root);
- }
- for (auto it:ans)
- cout << it << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement