codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1928.md (20496B)


      1 Source: https://codeforces.com/blog/entry/125740
      2 
      3 ## [1928A - Rectangle Cutting](/contest/1928/problem/A "Codeforces Round 924 (Div. 2)")
      4 
      5 **Solution**
      6 
      7 Let $a \le b$. Let's consider several cases:
      8 
      9 * If $a$ is even, then we can cut the rectangle into two rectangles of size $\frac{a}{2} \times b$ and combine them into a rectangle of size $\frac{a}{2} \times 2b$, which is definitely different from $a \times b$.
     10 * If $b$ is even and $b \ne 2a$, then we can cut the rectangle into two rectangles of size $a \times \frac{b}{2}$ and combine them into a rectangle of size $2a \times \frac{b}{2}$. Note that here we use the fact that $b \ne 2a$, because if $b = 2a$, then we will get the same rectangle of size $b \times a$.
     11 * If $a$ and $b$ are both odd, or $b = 2a$ and $a$ is odd, then the rectangle is not interesting. It is easy to understand that if we cut the rectangle of size $a \times b$ into two rectangles of size $a \times c$ and $a \times d$, where $c \ne d$, then we can always only combine the original rectangle (similarly if we cut it into rectangles $c \times b$ and $d \times b$). And from here it follows that we must divide one of the sides of the rectangle in half, so at least one side must be even.
     12 
     13 **Code**
     14 
     15 ```
     16 #include <vector>
     17 #include <iostream>
     18 #include <numeric>
     19 #include <algorithm>
     20 #include <cassert>
     21 #include <map>
     22 
     23 using namespace std;
     24  
     25 int main() {
     26 	ios_base::sync_with_stdio(false);
     27 	cin.tie(0);
     28 	cout.tie(0);
     29 	int t;
     30 	cin >> t;
     31 	while (t--) {
     32 	    int a, b;
     33 	    cin >> a >> b;
     34 	    if (a > b) {
     35 	        swap(a, b);
     36 	    }
     37 	    if (((a % 2 == 1) && (b % 2 == 1)) || ((a % 2 == 1) && (b == 2 * a))) {
     38 	        cout << "No\n";
     39 	    } else {
     40 	        cout << "Yes\n";
     41 	    }
     42 	}
     43 	
     44 	return 0;
     45 }
     46 ```
     47 
     48 ## [1928B - Equalize](/contest/1928/problem/B "Codeforces Round 924 (Div. 2)")
     49 
     50 **Solution**
     51 
     52 Suppose we already know the permutation that needs to be added. Let's consider the elements that will become equal after the addition. Notice that among them there cannot be equal elements, because among the numbers we are adding, there are no duplicates. Thus, only a set of numbers among which there are no equal ones, and the difference between the maximum and minimum does not exceed $n - 1$, can become equal. It is easy to see that any set of numbers satisfying these conditions can be equalized, and any set of numbers that became equal after adding the permutation satisfies these constraints.
     53 
     54 So let's sort the array, remove the equal elements from it. After that, we can use two pointers to find the maximum length subarray where the difference between the maximum and minimum does not exceed $n - 1$. The answer will be the length of such a subarray. The complexity of the solution is $O(n \log n)$.
     55 
     56 **Code**
     57 
     58 ```
     59 #include <bits/stdc++.h>
     60 
     61 using namespace std;
     62 
     63 void solve() {
     64     int n;
     65     cin >> n;
     66     vector<int> a(n);
     67     for (int i = 0; i < n; i++) {
     68         cin >> a[i];
     69     }
     70     sort(a.begin(), a.end());
     71     a.resize(unique(a.begin(), a.end()) - a.begin());
     72     int pnt = 0, ans = 0;
     73     for (int i = 0; i < a.size(); i++) {
     74         while(a[i] - a[pnt] >= n) {
     75             pnt++;
     76         }
     77         ans = max(ans, i - pnt + 1);
     78     }
     79     cout << ans << endl;
     80 }
     81 
     82 signed main() {
     83     int t = 1;
     84     cin >> t;
     85     for (int i = 0; i < t; ++i) {
     86         solve();
     87     }
     88     return 0;
     89 }
     90 ```
     91 
     92 ## [1928C - Physical Education Lesson](/contest/1928/problem/C "Codeforces Round 924 (Div. 2)")
     93 
     94 **Solution**
     95 
     96 All numbers repeat every $2k - 2$ positions. If the boy Vasya's number is calculated to be $x$, then it can be at positions of the form $(2k - 2) \cdot t + x$, or $(2k - 2) \cdot t + k + k - x$, for some non-negative $t$. This is true for all $x$, except for $x = 1$ and $x = k$ ~--- for these values, there is only one option left.
     97 
     98 Let's fix one of the options, the second one will be analogous. We need to find how many different values of $k$ satisfy the equation $(2k - 2) \cdot t + x = n$, for some non-negative $t$. It is not difficult to see that this holds if and only if $n - x$ is divisible by $2k - 2$. Therefore, it is necessary to find the number of \textbf{even} divisors of the number $n - x$. To consider the second case, it is necessary to proceed similarly with the number $n + x - 2$. The solution's complexity: $O(\sqrt{n})$
     99 
    100 **Code**
    101 
    102 ```
    103 #include <iostream>
    104 #include <unordered_set>
    105 
    106 using namespace std;
    107 
    108 unordered_set<int> solve(int a) {
    109     unordered_set<int> candidates;
    110     for (int i = 1; i * i <= a; i++) {
    111         if (a % i == 0) {
    112             if (i % 2 == 0) // segment len should be even
    113                 candidates.insert(i);
    114             if ((a / i) % 2 == 0)
    115                 candidates.insert(a / i);
    116         }
    117     }
    118     unordered_set<int> answer;
    119     for (int i : candidates) {
    120         answer.insert(1 + i / 2);
    121     }
    122     return answer;
    123 }
    124 
    125 int main() {
    126     int t;
    127     cin >> t;
    128     for (int _ = 1; _ <= t; _++) {
    129         int n, pos;
    130         cin >> n >> pos;
    131         unordered_set<int> candidates = solve(n - pos);  // bug2
    132         for (int i : solve(n + pos - 2)) { // bug1
    133             candidates.insert(i);
    134         }
    135         int answer = 0;
    136         for (int i : candidates) {
    137             if (i >= pos) {
    138                 answer++;
    139             }
    140         }
    141         cout << answer << endl;
    142     }
    143 }
    144 ```
    145 
    146 ## [1928D - Lonely Mountain Dungeons](/contest/1928/problem/D "Codeforces Round 924 (Div. 2)")
    147 
    148 **Solution**
    149 
    150 Let's learn how to solve the problem when $n = 1$. Suppose there is only one race and the number of its representatives is $c$. Notice that for a fixed $k$, it is advantageous for us to divide the representatives of the race almost evenly into squads.
    151 
    152 If $c$ is divisible by $k$, then it is advantageous for us to take exactly $y = \frac{c}{k}$ beings in each squad. Then the total number of pairs of beings in different squads is equal to $\frac{k(k-1)}{2} \cdot y^2$ (there are a total of $\frac{k(k-1)}{2}$ pairs of squads, and for each pair of squads there are $y^2$ pairs of beings from different squads).
    153 
    154 In the general case, when $c$ may not be divisible by $k$, let's denote $y = \left\lfloor \frac{c}{k} \right\rfloor$ and $y' = \left\lceil \frac{c}{k} \right\rceil$. Then it is advantageous for us to make squads of size $y$ and $y'$, where the number of squads of size $y'$ is equal to $c \bmod k$ (we essentially make all squads of size $y$, and then add 1 to some squads from the remaining part). In this case, the total number of pairs of beings in different squads is equal to $C_{k - c \bmod k}^2 \cdot y^2 + C_{c \bmod k}^2 \cdot y'^2 + (k - c \bmod k) \cdot (c \bmod k) \cdot y \cdot y'$. It remains to notice that it makes no sense to have $k \gt c$, so we can simply iterate through $k$ from $1$ to $c$ and choose the optimal one.
    155 
    156 When $n \gt 1$, we can notice that for a fixed $k$, we can solve the problem independently for each race. Let the number of representatives of the $i$-th race be $c_i$. Then we will iterate through $k$ from $1$ to $c_i$ for it and add the maximum total strength to the value of $cnt_k$ (the array $cnt$ is common for all races). Also, notice that for $k \gt c_i$, we will get the same total strength as for $k = c_i$. Then in the additional array $add$ (again, common for all races), we will add the maximum total strength for $k = c_i$ to $add_{c_i}$.
    157 
    158 We get the following solution: first, calculate the described arrays $cnt$ and $add$. After that, iterate through $k$ from $1$ to the maximum $c_i$. The maximum total strength of the squads for a fixed $k$ will be equal to $(cnt_k + (\text{sum of values } add_i \text{ for } i \lt k)) \cdot b - (k - 1) \cdot X$. From these values, we need to choose the maximum.
    159 
    160 **Code**
    161 
    162 ```
    163 #include <iostream>
    164 #include <vector>
    165 
    166 using namespace std;
    167 using ll = long long;
    168 
    169 ll pairs(ll n, ll k){
    170     if (n == 0 || k == 0){
    171         return 0;
    172     }
    173     ll x = n / k;
    174     ll l = n % k;
    175     ll r = k - l;
    176     ll L = (x + 1) * l, R = x * r;
    177     return R * L + (R - x) * R / 2 + L * (L - x - 1) / 2;
    178 }
    179 
    180 void solve(){
    181     int m;
    182     long long c, b;
    183     cin >> m >> b >> c;
    184 
    185     int n = 0;
    186     vector<int> cnt(m);
    187     for (int i = 0; i < m; ++i) {
    188         cin >> cnt[i];
    189         n = max(n, cnt[i]);
    190     }
    191 
    192     vector<long long> pair(n + 1);
    193     vector<long long> add(n + 1);
    194     for (int i = 0; i < m; ++i) {
    195         for (int j = 1; j <= cnt[i]; ++j) {
    196             pair[j] += pairs(cnt[i], j);
    197         }
    198         add[cnt[i]] += pairs(cnt[i], cnt[i]);
    199     }
    200 
    201     long long ans = 0;
    202     long long other = 0;
    203     for (int i = 1; i <= n; ++i) {
    204         ans = max(ans, b * (pair[i] + other) - c * (i - 1));
    205         other += add[i];
    206     }
    207     cout << ans << endl;
    208 }
    209 
    210 int main(){
    211     int t;
    212     cin >> t;
    213     while (t--){
    214         solve();
    215     }
    216 }
    217 ```
    218 
    219 ## [1928E - Modular Sequence](/contest/1928/problem/E "Codeforces Round 924 (Div. 2)")
    220 
    221 **Solution**
    222 
    223 Let's see what the answer will look like: first, there will be a prefix of the form $x, x + y, \ldots, x + k\cdot y$, and then there will be some number of blocks of the form $x \bmod y, x \bmod y + y, \ldots, x \bmod y + k \cdot y$.
    224 
    225 We can subtract the number $x \bmod y$ from all the elements of the sequence, and then divide all the elements by $y$ (all the elements will be divisible by $y$, since they initially had a remainder of $x \bmod y$). Let $b_1 = \frac{x - x \bmod y}{y}$. Then our sequence will start with $b_1, b_1 + 1, \ldots, b_1 + k_1$, and then there will be blocks of the form $0, 1, \ldots, k_i$.
    226 
    227 Let's calculate these values: $dp_i$~--- the minimum length of a sequence of blocks of the form $0, 1, \ldots, k_j$ with a sum of $i$. This value can be calculated for all numbers from $0$ to $s$ using dynamic programming. If we have processed all values from $0$ to $k-1$, then for $k$ we have calculated the minimum length, and we can update the value of $dp$ for $k + 1, k + 1 + 2, \ldots$~--- a total of $O(\sqrt{s})$ values not exceeding $s$. In this same $dp$, we can store through which values we were recalculated, for the restoration of the answer.
    228 
    229 Now, we can iterate over the length of the first block of the form $b_1, b_1 + 1, \ldots, b_1 + k_1$. Then we know the sum of the remaining blocks, and using the precalculated $dp$, we can determine whether the desired sequence can be formed or not.
    230 
    231 **Code**
    232 
    233 ```
    234 #include <cassert>
    235 #include <initializer_list>
    236 #include <numeric>
    237 #include <vector>
    238 #include <iostream>
    239 #include <utility>
    240 #include <stack>
    241 #include <queue>
    242 #include <set>
    243 #include <map>
    244 #include <algorithm>
    245 #include <math.h>
    246 
    247 using namespace std;
    248 
    249 #define pii pair<int, int>
    250 #define mp make_pair
    251 #define fi first
    252 #define se second
    253 #define all(x) (x).begin(), (x).end()
    254 #define ll long long
    255 #define pb emplace_back
    256 
    257 const int INF = 1e9 + 10;
    258 const ll INFLL = 1e18;
    259 
    260 void solve() {
    261     int n, x, y, S;
    262     cin >> n >> x >> y >> S;
    263     vector<int> dp(S + 1, INF);
    264     dp[0] = 0;
    265     for (int k = 1; k <= S; k++) {
    266         for (int l = 2; (l * (l - 1)) / 2 <= k; l++) {  // just 0 is never optimal
    267             dp[k] = min(dp[k], dp[k - (l * (l - 1)) / 2] + l);
    268         }
    269         assert(dp[k] <= 2 * k);
    270     }
    271     for (ll k = 0; k < n; k++) {
    272         ll prevSum = (k + 1) * x + (k * (k + 1)) / 2 * y;
    273         if (prevSum > S) {
    274             continue;
    275         }
    276         ll needSum = S - prevSum;
    277         needSum -= (n - k - 1) * (x % y);
    278         if (needSum < 0) {
    279             continue;
    280         }
    281         if (needSum % y != 0) {
    282             continue;
    283         }
    284         needSum /= y;
    285         assert(needSum <= S);
    286         if (dp[needSum] <= n - k - 1) {  // we found the answer
    287             vector<int> a(n);
    288             a[0] = x;
    289             for (int i = 1; i <= k; i++) {  // construct prefix
    290                 a[i] = a[i - 1] + y;
    291             }
    292             for (int i = k + 1; i <= k + (n - k - 1) - dp[needSum];
    293                  i++) {  // fill the rest like 0 0 0 ...
    294                 a[i] = x % y;
    295             }
    296             int i = k + (n - k - 1) - dp[needSum] + 1;  // first free index
    297             vector<int> lens;                           // recover lengths of the segments
    298             while (needSum != 0) {
    299                 for (int l = 2; (l * (l - 1)) / 2 <= needSum; l++) {
    300                     if (dp[needSum] == dp[needSum - (l * (l - 1)) / 2] + l) {
    301                         lens.pb(l);
    302                         needSum -= (l * (l - 1)) / 2;
    303                         break;
    304                     }
    305                 }
    306             }
    307             for (auto &len : lens) {
    308                 for (int j = 0; j < len; j++) {
    309                     a[i] = (x % y) + y * j;
    310                     i++;
    311                 }
    312             }
    313             cout << "YES\n";
    314             for (auto &c : a) {
    315                 cout << c << " ";
    316             }
    317             cout << "\n";
    318             return;
    319         }
    320     }
    321     cout << "NO\n";
    322 }
    323 
    324 int main() {
    325     cin.tie(0);
    326     cout.tie(0);
    327     ios_base::sync_with_stdio(0);
    328     int t = 1;
    329     cin >> t;
    330     while (t--) {
    331         solve();
    332     }
    333     return 0;
    334 }
    335 ```
    336 
    337 ## [1928F - Digital Patterns](/contest/1928/problem/F "Codeforces Round 924 (Div. 2)")
    338 
    339 **Solution**
    340 
    341 Let's assume that $a_i = a_{i+1}$ for some $1 \le i \lt n$, then for any $1 \le j \le m$, the cells $(i, j)$ and $(i+1, j)$ will have the same transparency. A similar statement can be made if there is an index $j$: $b_j = b_{j+1}$.
    342 
    343 Then the positions $a_i = a_{i+1}$ divide the array $a$ into \textit{blocks}, in each of which all neighboring pairs are not equal to each other. It is clear that if there is a square $(x, y, d)$ consisting of cells $(i, j)$ such that $x \le i \lt x+d$ and $y \le j \lt y+d$, then the segment $[x, x+d-1]$ is entirely contained in one of these \textit{blocks} of the array $a$. Similarly, the array $b$ can also be divided into blocks, and then the segment $[y, y+d-1]$ will also be entirely contained in one of the blocks.
    344 
    345 Let's try to solve the problem in $O(1)$ time, if there are no neighboring elements with the same values in the arrays $a$ and $b$ (also assuming that $n \le m$):
    346 
    347 $ f(n, m) = \sum \limits_{k=1}^{n} (n-k+1)(m-k+1) = \sum_{k=1}^n \left( k^2 + (m-n)k \right) \\ f(n, m) = \frac{n(n + 1)(2n + 1)}6 + (m - n) \cdot \frac{n(n+1)}2 \\ $
    348 
    349 This formula can be further transformed by introducing a quadruple of numbers for each natural number $n$: $a_n = 1$, $b_n = n$, $c_n = \frac12 n(n+1)$, $d_n = \frac16 n(n+1)(2n+1) - \frac12n^2(n+1)$. Then $f(n, m) = d_n a_m + c_n b_m$, if $n \le m$ and $f(n, m) = a_n d_m + b_n c_m$, if $n \gt m$.
    350 
    351 But if there are neighboring identical elements in the arrays $a$ and $b$, then this means that they are somehow divided into blocks. If these are blocks of lengths $n_1, \ldots, n_k$ in the array $a$ and blocks of lengths $m_1, \ldots, m_l$ in the array $b$, then the answer to the problem is
    352 
    353 $ \textrm{ans} = \sum_{i=1}^k \sum_{j=1}^l f(n_i, m_j) $
    354 
    355 Let's learn how to quickly calculate sums of the form $f(x, m_1) + \ldots + f(x, m_l)$. To do this, we will create 4 segment trees to quickly calculate the sums $\sum a_y$, $\sum b_y$, $\sum c_y$, $\sum d_y$ over segments of $y$, taking into account the multiplicity of $y$ in the array $m_1, \ldots, m_l$. Now the calculation of $f(x, m_1) + \ldots + f(x, m_k)$ is reduced to $4$ segment tree queries:
    356 
    357 $ f(x, m_1) + \ldots + f(x, m_l) = a_x \cdot \sum_{m_i \lt x} d_{m_i} + b_x \cdot \sum_{m_i \lt x} c_{m_i} + c_x \cdot \sum_{m_i \ge x} b_{m_i} + d_x \cdot \sum_{m_i \ge x} a_{m_i} $
    358 
    359 The sum $f(n_1, y) + \ldots + f(n_k, y)$ is calculated similarly. Now we just need to put our solution together. We will maintain the blocks of arrays $a$ and $b$ in an online mode. It is very convenient to do this by storing the positions $a_i = a_{i+1}$ in a data structure like std::set, and also by working with the differential array $a$ (i.e., maintaining not the array $a$ itself, but the array of differences between neighboring elements $c_i = a_{i+1} - a_i$). To recalculate the answer, we will count the number of squares that are involved in a specific block of the array $a$ or $b$, using the above result. As a result, we have a solution in $O((n+q) (\log n + \log m))$.
    360 
    361 P.S. A solution in $O(q \sqrt n)$ will not work due to a large constant. I tried very hard to rule it out :D.
    362 
    363 **Code**
    364 
    365 ```
    366 #include <bits/stdc++.h>
    367 
    368 using namespace std;
    369 using ll = long long;
    370 using pi = pair<int, int>;
    371 
    372 struct SegmentTree {
    373     int n;
    374     vector<ll> t;
    375 
    376     SegmentTree(int n) : n(n), t(2*n) { }
    377 
    378     void Add(int i, ll x) {
    379         for (i += n; i != 0; i >>= 1) t[i] += x;
    380     }
    381 
    382     ll Query(int l, int r) {
    383         ll ans = 0;
    384 
    385         for (l += n, r += n - 1; l <= r; l >>= 1, r >>= 1) {
    386             if ((l&1) == 1) ans += t[l++];
    387             if ((r&1) == 0) ans += t[r--];
    388         }
    389         return ans;
    390     }
    391 };
    392 
    393 struct SegmentContainer {
    394     int side;
    395     SegmentTree sgt_a, sgt_b, sgt_c, sgt_d;
    396     int id;
    397     // sgt_a: sum(1)
    398     // sgt_b: sum(m)
    399     // sgt_c: sum(m*(m+1)/2)
    400     // sgt_d: sum(m*(m-1)*(2*m-1)/6 - m*(m-1)/2*m)
    401 
    402     SegmentContainer(int side) : side(side), sgt_a(side), sgt_b(side), sgt_c(side), sgt_d(side) {
    403     }
    404 
    405     tuple<ll, ll, ll, ll> GetABCD(ll m) {
    406         return make_tuple(1, m, m*(m+1)/2, m*(m-1)*(2*m-1)/6 - m*(m-1)/2*m);
    407     }
    408 
    409     void Insert(int m) {
    410         auto [a, b, c, d] = GetABCD(m);
    411         sgt_a.Add(m-1, +a);
    412         sgt_b.Add(m-1, +b);
    413         sgt_c.Add(m-1, +c);
    414         sgt_d.Add(m-1, +d);
    415     }
    416 
    417     void Erase(int m) {
    418         auto [a, b, c, d] = GetABCD(m);
    419         sgt_a.Add(m-1, -a);
    420         sgt_b.Add(m-1, -b);
    421         sgt_c.Add(m-1, -c);
    422         sgt_d.Add(m-1, -d);
    423     }
    424 
    425     ll SquaresCount(int n) {
    426         const int mid = min(side, n);
    427         auto sum_a = sgt_a.Query(mid, side); // m > n
    428         auto sum_b = sgt_b.Query(mid, side); // m > n
    429         auto sum_c = sgt_c.Query(0, mid); // m <= n
    430         auto sum_d = sgt_d.Query(0, mid); // m <= n
    431         auto [a, b, c, d] = GetABCD(n);
    432 
    433         return d * sum_a + c * sum_b + b * sum_c + a * sum_d;
    434     }
    435 };
    436 
    437 struct SegmentMaintainer {
    438     SegmentContainer& my;
    439     SegmentContainer& other;
    440     ll& ans;
    441 
    442     set<int> pos_zero;
    443     vector<ll> diff_array;
    444 
    445     SegmentMaintainer(vector<int> a, 
    446                       SegmentContainer& my,
    447                       SegmentContainer& other,
    448                       ll& ans) :
    449             pos_zero(), diff_array(a.size()), my(my), other(other), ans(ans) {
    450         pos_zero.insert(0);
    451         for (int i = 1; i < a.size(); ++i) {
    452             diff_array[i] = a[i] - a[i-1];
    453             if (diff_array[i] == 0) pos_zero.insert(i);
    454         }
    455         pos_zero.insert(a.size());
    456 
    457         for (auto it = pos_zero.begin(); *it != my.side; ++it) {
    458             OnSegmentAppear(*next(it) - *it);
    459         }
    460     }
    461 
    462     void OnSegmentAppear(int len) {
    463         my.Insert(len);
    464         ans += other.SquaresCount(len);
    465     }
    466 
    467     void OnSegmentDissapear(int len) {
    468         my.Erase(len);
    469         ans -= other.SquaresCount(len);
    470     }
    471 
    472     void ChangeBound(int pos, ll dx) {
    473         if (pos == 0 || pos == my.side) return; 
    474             
    475         bool was_zero = diff_array[pos] == 0;
    476         diff_array[pos] += dx;
    477         bool now_zero = diff_array[pos] == 0;
    478 
    479         if (was_zero && !now_zero) {
    480             auto mid = pos_zero.find(pos);
    481             auto prv = prev(mid), nxt = next(mid);
    482             
    483             OnSegmentDissapear(*mid - *prv);
    484             OnSegmentDissapear(*nxt - *mid);
    485             OnSegmentAppear(*nxt - *prv);
    486 
    487             pos_zero.erase(mid);
    488         }
    489         
    490         if (!was_zero && now_zero) {
    491             auto mid = pos_zero.insert(pos).first;
    492             auto prv = prev(mid), nxt = next(mid);
    493 
    494             OnSegmentAppear(*mid - *prv);
    495             OnSegmentAppear(*nxt - *mid);
    496             OnSegmentDissapear(*nxt - *prv);
    497         }
    498     }
    499 
    500     void RangeAdd(int l, int r, int x) {
    501         ChangeBound(l, +x);
    502         ChangeBound(r, -x);
    503     }
    504 };
    505 
    506 int main() {
    507     ios::sync_with_stdio(0); cin.tie(0);
    508     int n, m, q; cin >> n >> m >> q;
    509 
    510     vector<int> a(n), b(m);
    511     for (int& x : a) cin >> x;
    512     for (int& x : b) cin >> x;
    513 
    514     ll ans = 0;
    515     SegmentContainer a_segments(n), b_segments(m);
    516 
    517     a_segments.id = 1;
    518     b_segments.id = 2;
    519 
    520     SegmentMaintainer a_maintainer(a, a_segments, b_segments, ans); 
    521     SegmentMaintainer b_maintainer(b, b_segments, a_segments, ans);
    522     
    523     cout << ans << '\n';
    524     while (q--) {
    525         int t, l, r, x; cin >> t >> l >> r >> x; --l;
    526         if (t == 1) a_maintainer.RangeAdd(l, r, x);
    527         if (t == 2) b_maintainer.RangeAdd(l, r, x);
    528         cout << ans << '\n';
    529     }
    530 }
    531 ```