georgiy110802

Untitled

Aug 4th, 2021
784
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<limits.h>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int getMax(int left, int right, vector<int> &maxA) {
  9.     left += maxA.size() >> 1;
  10.     right += maxA.size() >> 1;
  11.     int ans = 0;
  12.     while (left <= right) {
  13.         cout << left << " " << right << "\n";
  14.         if ((left % 2) != 0) {
  15.             ans = ans + maxA[left];
  16.             left++;
  17.         }
  18.         if ((right % 2) == 0) {
  19.             ans = ans + maxA[right];
  20.             right--;
  21.         }
  22.         left >>= 1;
  23.         right >>= 1;
  24.     }
  25.     return ans;
  26. }
  27.  
  28. void setValue(int i, int value, vector<int> &maxA) {
  29.     i += maxA.size() >> 1;
  30.     maxA[i] = value;
  31.     i >>= 1;
  32.     while (i > 0) {
  33.         maxA[i] = maxA[i << 1] + maxA[(i << 1) + 1];
  34.         i >>= 1;
  35.     }
  36. }
  37.  
  38. main() {
  39.     int n;
  40.     cin >> n;
  41.     vector<int> maxA(2 * n);
  42.     for (int i = n; i < 2 * n; i++)cin >> maxA[i];
  43.     for (int i = n - 1; i >= 1; i--)maxA[i] = maxA[i << 1] + maxA[(i << 1) + 1];
  44.     for (int i = 0; i < 2 * n; ++i) {
  45.         cout << maxA[i] << " ";
  46.     }
  47.     cout << "\n";
  48.     bool first = true;
  49.  
  50.     int m;
  51.     cin >> m;
  52.     for (int q = 0; q < m; q++) {
  53.         char cmd;
  54.         scanf(" %c", &cmd);
  55.         if (cmd == 's') {
  56.             int left, right;
  57.             cin >> left >> right;
  58.             left--;
  59.             right--;
  60.             if (first)first = false;
  61.             else printf(" ");
  62.             cout <<  getMax(left, right, maxA);
  63.         } else if (cmd == 'u') {
  64.             int pos, value;
  65.             cin >> pos >> value;
  66.             pos--;
  67.             setValue(pos, value, maxA);
  68.         }
  69.     }
  70. }
  71.  
RAW Paste Data