Advertisement
Guest User

Untitled

a guest
Apr 21st, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <fstream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <string>
  11. #define ll long long
  12. using namespace std;
  13. const ll INF = 1e18;
  14. void solve();
  15. int main() {
  16.     ios::sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.     cout << fixed;
  20.     cout << setprecision(15);
  21. #ifdef _DEBUG
  22.     freopen("input.txt", "r", stdin);
  23. #endif
  24.     solve();
  25.     return 0;
  26. }
  27. ll len;
  28. ll n, k;
  29. vector<ll>d;
  30. vector<ll>a;
  31. void readd(ll p) {
  32.     ll q = p;
  33.     while (p%len != 0) p--;
  34.     for (int i = 0; i < len; i++) {
  35.         if (i + len == n) break;
  36.         a[p + i] = d[q / len];
  37.     }
  38. }
  39. void add(ll l, ll r, ll x) {
  40.     for (int i = l; i < r;) {
  41.         if (i%len == 0 && i + len <= l) {
  42.             d[i / len] = x;
  43.             i += len;
  44.         }
  45.         else if (d[i / len] != -1) {
  46.             readd(i);
  47.             d[i / len] = -1;
  48.             a[i] = x;
  49.             i++;
  50.         }
  51.         else if (d[i / len] == -1) {
  52.             a[i] = x;
  53.             i++;
  54.         }
  55.     }
  56. }
  57. ll summ(ll l, ll r) {
  58.     ll res = 0;
  59.     for (int i = l; i < r;) {
  60.         if (i%len == 0 && i + len <= l && d[i / len] != -1) {
  61.             res += d[i / len] * len;
  62.             i += len;
  63.         }
  64.         else {
  65.             res += a[i];
  66.             i++;
  67.         }
  68.     }
  69.     return res;
  70. }
  71. void solve() {
  72.     cin >> n >> k;
  73.     len = sqrt(n) + 1;
  74.     d.resize(len);
  75.     a.resize(n);
  76.     for (auto x : d) x = -1;
  77.     for (int i = 0; i < k; i++) {
  78.         char c;
  79.         cin >> c;
  80.         if (c == 'A') {
  81.             ll l, r, x;
  82.             cin >> l >> r >> x;
  83.             add(l - 1, r, x);
  84.         }
  85.         if (c == 'Q') {
  86.             ll l, r;
  87.             cin >> l >> r;
  88.             cout << summ(l - 1, r) << endl;
  89.         }
  90.     }
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement