Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <set>
- #include <map>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #define ll long long
- using namespace std;
- const ll INF = 1e18;
- void solve();
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed;
- cout << setprecision(15);
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #endif
- solve();
- return 0;
- }
- ll len;
- ll n, k;
- vector<ll>d;
- vector<ll>a;
- void readd(ll p) {
- ll q = p;
- while (p%len != 0) p--;
- for (int i = 0; i < len; i++) {
- if (i + len == n) break;
- a[p + i] = d[q / len];
- }
- }
- void add(ll l, ll r, ll x) {
- for (int i = l; i < r;) {
- if (i%len == 0 && i + len <= l) {
- d[i / len] = x;
- i += len;
- }
- else if (d[i / len] != -1) {
- readd(i);
- d[i / len] = -1;
- a[i] = x;
- i++;
- }
- else if (d[i / len] == -1) {
- a[i] = x;
- i++;
- }
- }
- }
- ll summ(ll l, ll r) {
- ll res = 0;
- for (int i = l; i < r;) {
- if (i%len == 0 && i + len <= l && d[i / len] != -1) {
- res += d[i / len] * len;
- i += len;
- }
- else {
- res += a[i];
- i++;
- }
- }
- return res;
- }
- void solve() {
- cin >> n >> k;
- len = sqrt(n) + 1;
- d.resize(len);
- a.resize(n);
- for (auto x : d) x = -1;
- for (int i = 0; i < k; i++) {
- char c;
- cin >> c;
- if (c == 'A') {
- ll l, r, x;
- cin >> l >> r >> x;
- add(l - 1, r, x);
- }
- if (c == 'Q') {
- ll l, r;
- cin >> l >> r;
- cout << summ(l - 1, r) << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement