codeforces-scrape

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

2044.md (21815B)


      1 Source: https://codeforces.com/blog/entry/137306
      2 
      3 #### Special thanks to our hub of testuwuers for contributing solution explanations!
      4 
      5 #### [2044A - Легкая задача](/contest/2044/problem/A "Codeforces Round 993 (Div. 4)")
      6 
      7 Problem Credits: [cry](/profile/cry "Международный мастер cry")   
      8  Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev")
      9 
     10 **Solution** 
     11 
     12 For any $n$, Cube can set $a$ = any integer between $1$ and $n-1$ inclusive, and set $b = n - a$. $a$ cannot be less than $1$, because then it would be non-positive, and $a$ cannot be greater than $n-1$, because then $b$ would be less than $1$, which would make it non-positive. Therefore the answer is just $n-1$ for all $n$.
     13 
     14 **Code (Python)**
     15 
     16 ```
     17 input = sys.stdin.readline
     18 for _ in range(int(input())):
     19     print(int(input())-1)
     20 ```
     21 
     22 #### [2044B - Обычная задача](/contest/2044/problem/B "Codeforces Round 993 (Div. 4)")
     23 
     24 Problem Credits: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad")   
     25  Analysis: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad"), [macaquedev](/profile/macaquedev "Специалист macaquedev")
     26 
     27 **Solution** 
     28 
     29 The letters she reads that comprise string $b$ are just the letters that comprise string $a$, flipped left-to-right. This means that 'p' becomes 'q', 'q' becomes 'p', and 'w' stays 'w', since it is vertically symmetrical. The order in which the letters are read is also reversed, because what used to be the left side of string $a$ gets flipped over to the right side of string $b$, and vice versa.
     30 
     31 We now have an algorithm for constructing string $b$, which is to iterate from right-to-left on string $a$, outputting 'p' when there is a 'q', 'q' when there is a 'p', and 'w' when there is a 'w'.
     32 
     33 **Code (C++)**
     34 
     35 ```
     36 #include <bits/stdc++.h>
     37 using namespace std;
     38 #define ll long long
     39 #define pll pair<ll, ll>
     40 
     41 int t;
     42 
     43 int main() {
     44 	cin.tie(0)->sync_with_stdio(0);
     45 	cin >> t;
     46 	while (t--) {
     47 		string s;
     48 		cin >> s;
     49 		reverse(s.begin(), s.end());
     50 		for (char &c : s) if (c == 'q') c = 'p'; else if (c == 'p') c = 'q';
     51 		cout << s << '\n';
     52 	}
     53 }
     54 ```
     55 
     56 #### [2044C - Сложная задача](/contest/2044/problem/C "Codeforces Round 993 (Div. 4)")
     57 
     58 Problem Credits: [cry](/profile/cry "Международный мастер cry")   
     59  Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev")
     60 
     61 **Solution** 
     62 
     63 Let $A$, $B$, $C$ be three sets of monkeys, such that monkeys in $A$ can only sit in row $1$, $B$ in row $2$, and $C$ can sit anywhere. It is clear that if there is free space in row $1$, and there are monkeys left in set $A$, it is optimal to seat a monkey from set $A$ onto row $1$. This is because a monkey from set $C$ can be seated on either row, and there might be space left on the other row for that same monkey in set $C$ after you've already seated the monkey from set $A$. However, this is not the case if you start by seating the monkeys in set $C$ in the front row, since you might now leave empty seats at the back, but then have monkeys from set $A$ still left unseated.
     64 
     65 Therefore, the strategy is as follows: seat as many monkeys from set $A$ as you can in the front row, then seat as many monkeys from set $B$ as you can in the back row, then seat as many monkeys from set $C$ as you can, and that yields the answer.
     66 
     67 **Code (C++)**
     68 
     69 ```
     70 #include<bits/stdc++.h>
     71 #define ll long long
     72 using namespace std;
     73 
     74 int main()
     75 {
     76     ios::sync_with_stdio(false);
     77     cin.tie(nullptr);
     78     int tt;
     79     cin>>tt;
     80     while(tt--)
     81     {
     82         int m,a,b,c;
     83         cin>>m>>a>>b>>c;
     84         int ans=0,rem=0;
     85         ans+=min(m,a);rem+=m-min(m,a);
     86         ans+=min(m,b);rem+=m-min(m,b);
     87         ans+=min(rem,c);
     88         cout<<ans<<'\n';
     89     }
     90     return 0;
     91 }
     92 ```
     93 
     94 #### [2044D - Задача посложнее](/contest/2044/problem/D "Codeforces Round 993 (Div. 4)")
     95 
     96 Problem Credits: [cry](/profile/cry "Международный мастер cry"), [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED")   
     97  Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev")
     98 
     99 **Solution** 
    100 
    101 Observe that if you have an array where all elements are unique, they will all have frequency $1$, therefore they can all be classified as the mode. Therefore, it follows that the strategy for the construction is to just construct an array where for each prefix, the last element of this prefix appears in the array at least once. An easy way of doing is this is such:
    102 
    103 For each element $a_i$, if this value has appeared previously in the array (you can use a set to check this), set $b_i$ equal to some random integer that isn't used elsewhere in the list $a$, and keep going. Otherwise, set $b_i = a_i$.
    104 
    105 **Code (C++)**
    106 
    107 ```
    108 #include<bits/stdc++.h>
    109 #define ll long long
    110 using namespace std;
    111 
    112 int main()
    113 {
    114     ios::sync_with_stdio(false);
    115     cin.tie(nullptr);
    116     int tt;
    117     cin>>tt;
    118     while(tt--)
    119     {
    120         int n;
    121         cin>>n;
    122         vector<int> a(n+1),b(n);
    123         for(int i=0;i<n;i++)
    124         {
    125             int x;
    126             cin>>x;
    127             if(!a[x])
    128             {
    129                 b[i]=x;
    130                 a[x]=1;
    131             }
    132         }
    133         queue<int> q;
    134         for(int i=1;i<=n;i++)
    135             if(!a[i])
    136                 q.push(i);
    137         for(int i=0;i<n;i++)
    138         {
    139             if(!b[i])
    140             {
    141                 b[i]=q.front();
    142                 q.pop();
    143             }
    144         }
    145         for(int i=0;i<n;i++)
    146             cout<<b[i]<<" \n"[i==n-1];
    147     }
    148     return 0;
    149 }
    150 ```
    151 
    152 #### [2044E - Безумная задача](/contest/2044/problem/E "Codeforces Round 993 (Div. 4)")
    153 
    154 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED"),[Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad")   
    155  Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev"), [chromate00](/profile/chromate00 "Эксперт chromate00")
    156 
    157 **Solution 1 (Binary Search)**
    158 
    159 Clearly, trying to bruteforce over all possible values of $x$ or $y$ is too slow, because the bounds are $1 \leq l_1 \leq r_1 \leq 10^9$. However, there is another variable that you can actually bruteforce over — and that is $n$. This is because exponentiation famously makes numbers very big very quickly — and if we set $k$ as small as possible (i.e. $2$), we only need to check $1 \leq n \leq 32$. This is because $2^{32} \gt 10^9$, so there cannot possibly be any solutions for $n \gt 32$ for any $k$.
    160 
    161 Now, let's rephrase the problem. We need to find pairs $(x, y)$ such that $x \cdot k^n = y$. Now, we can check every value of $n$ from $1$ to $32$, and for each, binary search to find the smallest $x$ such that $y$ fits the conditions, and the largest $x$. Now, we can subtract these two values and add this to the answer.
    162 
    163 **Solution 2 (Intervals)**
    164 
    165 Note that we do not need to care about more than $32$ different values of $k^n$, because obviously $k^{32} \ge 2^{32} \gt 10^9$. From here and on, we focus on solving for only one value of $k^n$.
    166 
    167 When $k^n$ is fixed and you are given $\frac{y}{x}=k^n$, notice $y$ is fixed as $x k^n$. Therefore, if we count the values $x$ such that $y$ is in the given interval as well, we will be properly counting the ordered pairs.
    168 
    169 Formally, this condition can be cleared out as:
    170 
    171 * $l_2 \le x k^n \le r_2$
    172 * $\frac{l_2}{k^n} \le x \le \frac{r_2}{k^n}$
    173 * Because $x$ is an integer, $\left \lceil {\frac{l_2}{k^n}} \right \rceil \le x \le \left \lfloor {\frac{r_2}{k^n}} \right \rfloor$
    174 
    175 Thus, when we intersect the two intervals, we get the following interval at last.
    176 
    177 $\max \left({l_1,\left \lceil {\frac{l_2}{k^n}} \right \rceil}\right) \le x \le \min \left({r_1,\left \lfloor {\frac{r_2}{k^n}} \right \rfloor}\right)$
    178 
    179 Compute the size of this interval for all $k^n$ (at most $32$ values) and the answer can be found.
    180 
    181 Do note the following details while implementing:
    182 
    183 * When $r \lt l$, the size of the interval is $0$, not negative.
    184 * Beware of overflows. Dealing with big integers can be helpful in avoiding this, but it may make your solution slow.
    185 * Do not round up a fraction using the `ceil` function; This has been a recurring issue in almost every Div.4!
    186 
    187 **Code (C++)**
    188 
    189 ```
    190 #include<bits/stdc++.h>
    191 #define ll long long
    192 using namespace std;
    193 
    194 int main()
    195 {
    196     ios::sync_with_stdio(false);
    197     cin.tie(nullptr);
    198     int tt;
    199     cin>>tt;
    200     while(tt--)
    201     {
    202         ll k,l1,r1,l2,r2;
    203         cin>>k>>l1>>r1>>l2>>r2;
    204         ll kn=1,ans=0;
    205         for(int n=0;r2/kn>=l1;n++)
    206         {
    207             ans+=max(0ll,min(r2/kn,r1)-max((l2-1)/kn+1,l1)+1ll);
    208             kn*=k;
    209         }
    210         cout<<ans<<'\n';
    211     }
    212     return 0;
    213 }
    214 ```
    215 
    216 #### [2044F - Легкая демоническая задача](/contest/2044/problem/F "Codeforces Round 993 (Div. 4)")
    217 
    218 Problem Credits: [chromate00](/profile/chromate00 "Эксперт chromate00"), [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED")   
    219  Analysis: [DivinePunishment](/profile/DivinePunishment "Эксперт DivinePunishment")
    220 
    221 **Are you a python user and failing test 12?**
    222 
    223 This is an anti-hash test for python sets and dictionaries. Before you call us evil, we saved you from getting hacked in open hack phase. Beware!
    224 
    225 **Solution** 
    226 
    227 Let's denote the beauty of the matrix as $B$, and denote $\text{SumA}$ as the sum of all the elements in the array $a$, and $\text{SumB}$ as the sum of all the elements in the array $b$.
    228 
    229 Before applying an operation, the beauty of the matrix can be expressed as:
    230 
    231 $B = b_1 \cdot a_1 + b_1 \cdot a_2 + b_1 \cdot a_3 + b_2 \cdot a_1 + b_2 \cdot a_2 + \ldots$
    232 
    233 After factoring, this simplifies to:
    234 
    235 $ B = b_1 \cdot (a_1 + a_2 + a_3 + \ldots) + b_2 \cdot (a_1 + a_2 + a_3 + \ldots) + \ldots $
    236 
    237 Further factoring gives:
    238 
    239 $ B = (a_1 + a_2 + a_3 + a_4 + \ldots) \cdot (b_1 + b_2 + b_3 + \ldots) $
    240 
    241 This can be written as:
    242 
    243 $ B = \text{SumA} \cdot \text{SumB}$
    244 
    245 Now, consider the effect of an operation on a column $C$. The beauty decreases by $A_c \cdot \text{SumB}$. Similarly, when an operation is done on a row $R$, the beauty decreases by $B_r \cdot \text{SumA}$.
    246 
    247 An important observation is that the element at position $(r, c)$ is counted twice, so we must account for this in the formula.
    248 
    249 After considering this, let the beauty after the operations be denoted as $X$. Using the observations above:
    250 
    251 $X = B - (b_i \cdot \text{SumA} + a_j \cdot \text{SumB} - a_j \cdot b_i)$
    252 
    253 Simplifying further:
    254 
    255 $X = \text{SumA} \cdot \text{SumB} - b_i \cdot \text{SumA} - a_j \cdot \text{SumB} + a_j \cdot b_i$
    256 
    257 Factoring terms, we obtain:
    258 
    259 $X = \text{SumA} \cdot (\text{SumB} - b_i) - a_j \cdot (\text{SumB} - b_i)$
    260 
    261 Finally:
    262 
    263 $X = (\text{SumB} - b_i) \cdot (\text{SumA} - a_j)$
    264 
    265 At this stage, it is sufficient to iterate over the divisors of $X$. For each ordered pair of divisors whose product is $X$, we check whether the required values of $\text{SumB} - b_i$ and $\text{SumA} - a_j$ can be achieved.
    266 
    267 This can be implemented using a simple map or boolean vector for faster computation, although such optimization is not required for this problem.
    268 
    269 **Code (C++)**
    270 
    271 ```
    272 #include <bits/stdc++.h>
    273 using namespace std;
    274 #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
    275 #define F0R(i,a) FOR(i,0,a)
    276 #define int long long
    277 #define vt vector
    278 #define endl "\n"
    279 
    280 const int N = 4e5 + 5;
    281 bool apos[N], aneg[N], bpos[N], bneg[N], posspos[N], possneg[N];
    282 
    283 signed main() {
    284     ios_base::sync_with_stdio(false); 
    285     cin.tie(0);
    286     int n,m,q;
    287     cin >> n >> m >> q;
    288     vector<int> a(n), b(m);
    289     int asum = 0, bsum = 0;
    290     F0R(i, n) {
    291         cin >> a[i];
    292         asum += a[i];
    293     }
    294     F0R(i, m) {
    295         cin >> b[i];
    296         bsum += b[i];
    297     }
    298     F0R(i, n) {
    299         if(abs(asum-a[i]) < N) {
    300             if(asum-a[i]<0) aneg[a[i]-asum]=true;   
    301             else apos[asum-a[i]]=true;
    302         } 
    303     }
    304     F0R(i, m) {
    305         if(abs(bsum-b[i]) < N) {
    306             if(bsum-b[i]<0) bneg[b[i]-bsum]=true;   
    307             else bpos[bsum-b[i]]=true;
    308         } 
    309     }
    310     FOR(i, 1, N) {
    311         FOR(j, 1, N) {
    312             if(i * j > N) break;
    313             if(apos[i]&&bpos[j]) posspos[i*j]=true;
    314             if(apos[i]&&bneg[j]) possneg[i*j]=true;
    315             if(aneg[i]&&bpos[j]) possneg[i*j]=true;
    316             if(aneg[i]&&bneg[j]) posspos[i*j]=true;
    317         }
    318     }
    319     while(q--) {
    320         int x;
    321         cin >> x;
    322         if(x>0) {
    323             if(posspos[x]) {
    324                 cout << "YES" << endl;
    325             } else {
    326                 cout << "NO" << endl;
    327             }
    328         } else {
    329             if(possneg[-x]) {
    330                 cout << "YES" << endl;
    331             } else {
    332                 cout << "NO" << endl;
    333             }
    334         }
    335     }
    336     return 0;
    337 }
    338 ```
    339 
    340 #### [2044G1 - Средняя демоническая задача (легкая версия)](/contest/2044/problem/G1 "Codeforces Round 993 (Div. 4)")
    341 
    342 Problem Credits: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad")   
    343  Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev")
    344 
    345 **Solution** 
    346 
    347 This problem deals with a specific subclass of graphs called "functional graphs", also known as "successor graphs". The key feature that they have is that each node only has one successor. Therefore, the graph in the problem will necessarily be split into $k \geq 1$ components, where each component necessarily contains one cycle, and each node will either be in the cycle, or it will be on a path leading towards the cycle.
    348 
    349 Observe that if a node that is not on a cycle currently has a plushie, this plushie will cause the arrangement to be unstable until the plushie reaches the cycle. Proof: suppose node $u$ has the plushie on day $i$. On the next day, $u$ will no longer have this plushie, because they will have passed it down to $r_u$, therefore, the arrangement has changed. This continues inductively until the plushie reaches the cycle of its component.
    350 
    351 From this, we know that the answer is at least the distance of any node to the cycle. Now, since every node in the cycle already has a plushie, we know that these plushies just get passed round and round, so actually, nodes within the cycle cannot change the answer. Therefore, we've already found the final answer.
    352 
    353 **Code (C++)**
    354 
    355 ```
    356 #include<bits/stdc++.h>
    357 #define ll long long
    358 using namespace std;
    359 
    360 int main()
    361 {
    362     ios::sync_with_stdio(false);
    363     cin.tie(nullptr);
    364     int tt;
    365     cin>>tt;
    366     while(tt--)
    367     {
    368         int n;
    369         cin>>n;
    370         vector<int> r(n+1),d(n+1);
    371         for(int i=1;i<=n;i++)
    372         {
    373             cin>>r[i];
    374             d[r[i]]++;
    375         }
    376         set<pair<int,int> > s;
    377         for(int i=1;i<=n;i++)
    378             s.insert({d[i],i});
    379         int ans=2;
    380         queue<int> q;
    381         while(!s.empty()&&(*s.begin()).first==0)
    382         {
    383             while(!s.empty()&&(*s.begin()).first==0)
    384             {
    385                 int k=(*s.begin()).second;
    386                 auto it=s.find({d[r[k]],r[k]});
    387                 d[r[k]]--;
    388                 if(it!=s.end())
    389                 {
    390                     s.erase(it);
    391                     q.push(r[k]);
    392                 }
    393                 s.erase(s.begin());
    394             }
    395             while(!q.empty())
    396                 s.insert({d[q.front()],q.front()}),q.pop();
    397             ans++;
    398         }
    399         cout<<ans<<'\n';
    400     }
    401     return 0;
    402 }
    403 ```
    404 
    405 #### [2044G2 - Средняя демоническая задача (сложная версия)](/contest/2044/problem/G2 "Codeforces Round 993 (Div. 4)")
    406 
    407 Problem Credits: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad")   
    408  Analysis: [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED")
    409 
    410 **Solution** 
    411 
    412 Note that similarly to G1, once all plushies end up in the hands of spiders who are in a loop, the process becomes stable.
    413 
    414 Let's model the input as a collection of rooted forests. For each spider $i$, if $i$ is part of a loop, then let's compress the loop into a single node and use that as the root of a tree. Otherwise, if spider $i$ gives a present to spider $r_i$, then let's draw an edge from $i$ to $r_i$. Now, let $i$ be any node that is not part of a loop. How long will it take until spider $i$ runs out of presents? We can see that it is the subtree size of $i$, as one present leaves the subtree each year.
    415 
    416 Thus, our challenge now is to process the nodes in an efficient order such that we can find the subtree size of all nodes. This can be done with topological sorting, which gives us an order that processes all nodes starting from the leaf upwards. After the topological sort, we may do dynamic programming to find subtree sizes of all nodes. Let $dp[i]$ be the number of days until spider $i$ runs out of presents. Let's suppose that we already calculated $dp[i]$ (we initialize it to be $1$ for all nodes since each spider starts with a present). Then, we should add $dp[i]$ to $dp[r_i]$. Doing this and adding up all $dp$ values of nodes directly before a cycle will yield the answer.
    417 
    418 **Code (C++)**
    419 
    420 ```
    421 #include<bits/stdc++.h>
    422 #define ll long long
    423 using namespace std;
    424 
    425 int main()
    426 {
    427     ios::sync_with_stdio(false);
    428     cin.tie(nullptr);
    429     int tt;
    430     cin>>tt;
    431     while(tt--)
    432     {
    433         int n;
    434         cin>>n;
    435         vector<int> r(n+1),d(n+1),v(n+1,1);
    436         for(int i=1;i<=n;i++)
    437         {
    438             cin>>r[i];
    439             d[r[i]]++;
    440         }
    441         set<pair<int,int> > s;
    442         for(int i=1;i<=n;i++)
    443         {
    444             s.insert({d[i],i});
    445         }
    446         int ans=2;
    447         queue<int> q;
    448         while(!s.empty()&&(*s.begin()).first==0)
    449         {
    450             while(!s.empty()&&(*s.begin()).first==0)
    451             {
    452                 int k=(*s.begin()).second;
    453                 ans=max(ans,v[k]+2);v[r[k]]+=v[k];
    454                 auto it=s.find({d[r[k]],r[k]});
    455                 d[r[k]]--;
    456                 if(it!=s.end())
    457                 {
    458                     s.erase(it);
    459                     q.push(r[k]);
    460                 }
    461                 s.erase(s.begin());
    462             }
    463             while(!q.empty())
    464                 s.insert({d[q.front()],q.front()}),q.pop();
    465         }
    466         cout<<ans<<'\n';
    467     }
    468     return 0;
    469 }
    470 ```
    471 
    472 #### [2044H - Сложная демоническая задача](/contest/2044/problem/H "Codeforces Round 993 (Div. 4)")
    473 
    474 Problem Credits: [cry](/profile/cry "Международный мастер cry")   
    475  Analysis: [chromate00](/profile/chromate00 "Эксперт chromate00")
    476 
    477 **Solution** 
    478 
    479 Consider translating the sum back onto the matrix. For simplicity we discuss about querying the whole matrix.
    480 
    481 The sum we would like to find is $\sum_i i\cdot A_i$. Here, $A_i$ corresponds to $M_{(x,y)}$, so we will translate this to $\sum_{x,y} i\cdot M_{(x,y)}$. The issue left is on the $i$ multiplied to it.
    482 
    483 Remember that we index the entries in increasing order of $y$, and then increasing order of $x$. Assuming $y$ and $x$ were $0$-indexed, this will mean entry $(x,y)$ corresponds to $x\cdot n + y$ (also $0$-indexed). You can notice that this naturally corresponds to the order we had defined as well.
    484 
    485 Then, what we want to find is $\sum_{x,y} (x \cdot n + y + 1)\cdot M_{(x,y)}$. Notice $x \cdot n$, $y$, $1$ are independent, and we can split them into sums $\sum_x x \cdot n \cdot M_{(x,y)}$, $\sum_y y \cdot M_{(x,y)}$, $\sum M_{(x,y)}$. Each of these three sums can be precomputed entry by entry, and a 2D prefix sum can solve the answer for the entire matrix.
    486 
    487 The query for a submatrix is very similar. Formally, you have to care about:
    488 
    489 * That we have $y_2-y_1+1$ columns instead of $n$ now;
    490 * That the precomputed values might not start from $0$ on the first row/column of the query.
    491 
    492 Still, these two issues can be fixed using the three sums we have precomputed. The time complexity becomes $\mathcal{O}(n^2+q)$.
    493 
    494 **Code (C++)**
    495 
    496 ```
    497 #include <bits/stdc++.h>
    498 using namespace std;
    499 using ll = long long;
    500 using vll = vector <ll>;
    501 using ii = pair <ll, ll>;
    502 using vii = vector <ii>;
    503 
    504 void tc () {
    505     ll n, Q;
    506     cin >> n >> Q;
    507     vector <vll> mat(n, vll(n));
    508     for (vll &ve : mat) {
    509         for (ll &i : ve) cin >> i;
    510     }
    511     vector <vll> psR(n, vll(n+1)), psRr(n, vll(n+1)), psRc(n+1, vll(n+1)), ps(n+1, vll(n+1)), psRrc(n+1, vll(n+1));
    512     for (ll i = 0; i < n; i++) {
    513         for (ll j = 0; j < n; j++) {
    514             psR[i][j+1] = psR[i][j] + mat[i][j];
    515         }
    516     }
    517     for (ll i = 0; i < n; i++) {
    518         for (ll j = 0; j < n; j++) {
    519             psRr[i][j+1] = psRr[i][j] + mat[i][j]*(j+1);
    520         }
    521     }
    522     for (ll i = 0; i < n; i++) {
    523         for (ll j = 0; j <= n; j++) {
    524             psRc[i+1][j] = psRc[i][j] + psR[i][j]*(i+1);
    525         }
    526     }
    527     for (ll i = 0; i < n; i++) {
    528         for (ll j = 0; j <= n; j++) {
    529             psRrc[i+1][j] = psRrc[i][j] + psRr[i][j];
    530         }
    531     }
    532     for (ll i = 0; i < n; i++) {
    533         for (ll j = 0; j <= n; j++) {
    534             ps[i+1][j] = ps[i][j] + psR[i][j];
    535         }
    536     }
    537     while (Q--) {
    538         ll x1, y1, x2, y2;
    539         cin >> x1 >> y1 >> x2 >> y2;
    540         x1--; y1--; x2--; y2--;
    541         ll ans = 0;
    542         ans += -(ps[x2+1][y2+1]-ps[x2+1][y1]-ps[x1][y2+1]+ps[x1][y1])*x1*(y2-y1+1);
    543         ans += (psRc[x2+1][y2+1] - psRc[x1][y2+1] - (ps[x2+1][y2+1]-ps[x1][y2+1]))*(y2-y1+1);
    544 
    545         ans += (psRc[x2+1][y1] - psRc[x1][y1] - (ps[x2+1][y1]-ps[x1][y1]))*-(y2-y1+1);
    546         ans += (ps[x2+1][y2+1]-ps[x1][y2+1])*-y1;
    547         ans += (ps[x2+1][y1]-ps[x1][y1])*y1;
    548 
    549         ans += psRrc[x2+1][y2+1] - psRrc[x1][y2+1];
    550         ans +=-(psRrc[x2+1][y1] - psRrc[x1][y1]);
    551         cout << ans << ' ';
    552     }
    553     cout << '\n';
    554 }
    555 
    556 int main () {
    557     cin.tie(nullptr) -> sync_with_stdio(false);
    558     ll T; cin >> T; while (T--) { tc(); }
    559     return 0;
    560 }
    561 ```