codeforces-scrape

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

1682.md (34851B)


      1 Source: https://codeforces.com/blog/entry/103097
      2 
      3 I hope you all liked the round. Please share your feedback in the comments section.
      4 
      5 # [1682A — Palindromic Indices](https://codeforces.com/contest/1682/problem/A)
      6 
      7 **Hint**
      8 
      9 Read the statement carefully!! The given string is a **palindrome**.
     10 
     11 **Tutorial**
     12 
     13 Let's remove some index $i$ from the first half of $s$ and check whether the resulting string is a palindrome or not, the other half has the same approach. The prefix of length $i-1$ already matches with the suffix of the same length because the initial string was a palindrome, so we just need to check if $t = s[i + 1 \ldots n - i + 1]$ is a palindrome.
     14 
     15 For $t$ to be a palindrome, $s_{n - i + 1}$ should be equal to $s_{i + 1}$ which was initially equal to $s_{n - i}$, again which should be equal to $s_{i + 2}$ and this goes on. Here we can see that $s_i = s_{i + 1} \ldots = s_{n - i + 1}$. So the answer is simply equal to the number of contiguous same characters in the center of the string which can be calculated in $\mathcal{O(n)}$.
     16 
     17 **Solution**
     18 
     19 ```
     20 #include<bits/stdc++.h>
     21 using namespace std ;
     22 
     23 #define ll              long long 
     24 #define pb              push_back
     25 #define all(v)          v.begin(),v.end()
     26 #define sz(a)           (ll)a.size()
     27 #define F               first
     28 #define S               second
     29 #define INF             2000000000000000000
     30 #define popcount(x)     __builtin_popcountll(x)
     31 #define pll             pair<ll,ll>
     32 #define pii             pair<int,int>
     33 #define ld              long double
     34 
     35 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
     36 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
     37 
     38 #ifdef LOCAL
     39 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
     40 #else
     41 #define debug(...) 2401
     42 #endif
     43 
     44 int _runtimeTerror_()
     45 {
     46     int n;
     47     cin >> n;
     48     string s;
     49     cin >> s;
     50     int cnt = 0;
     51     for(int i=(n-1)/2;i>=0;--i) {
     52     	if(s[i] == s[(n - 1) / 2]) {
     53     		++cnt;
     54     	}
     55     	else {
     56     		break;
     57     	}
     58     }
     59     cout << 2 * cnt - (n & 1) << "\n";
     60     return 0;
     61 }
     62 
     63 int main()
     64 {
     65     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
     66     #ifdef runSieve
     67         sieve();
     68     #endif
     69     #ifdef NCR
     70         initncr();
     71     #endif
     72     int TESTS = 1;
     73     cin >> TESTS;
     74     while(TESTS--) {
     75         _runtimeTerror_();
     76     }
     77     return 0;
     78 }
     79 ```
     80 
     81 # [1682B — AND Sorting](https://codeforces.com/contest/1682/problem/B)
     82 
     83 **Hints**
     84 
     85 **Hint 1**
     86 
     87 You must have to make at least one swap on the elements which are not at their correct positions initially. So $X$ must be a submask of all elements which are not at their correct positions.
     88 
     89 **Hint 2**
     90 
     91 What is the maximum possible value of $X$ from Hint $1$? It is the bitwise AND of all elements which are not at their correct positions. It turns out that this value is achievable too.
     92 
     93 **Tutorial**
     94 
     95 We always have to make at least one swap for the elements which are not at their correct positions. Hence an upper bound of answer would be the bitwise AND of those elements. Let the value be $X$. It turns out that the given permutation is $X$-sortable.
     96 
     97 **Proof**:
     98 
     99 First, notice that $X$ would always be present in $p$. Let $pos_x$ be the position of $X$ in $p$ initially. Let's say at some point we want to swap two values $p_i$ and $p_j$, then $p_i$ and $p_j$ would always be a supermask of $X$ i.e. $p_i$ & $X = X$ and $p_j$ & $X = X$. We can make the following moves to swap $p_i$ and $p_j$ without disturbing any other element.
    100 
    101 * Swap values at indices $i$ and $pos_x$.
    102 * Swap values at indices $i$ and $j$.
    103 * Swap values at indices $j$ and $pos_x$.
    104 
    105 It can be seen that in every swap the bitwise AND of two values which we are swapping is always $X$. Hence we can swap any two values which were not at their correct positions, therefore we can sort the permutation $p$.
    106 
    107 Overall Complexity: $\mathcal{O(n)}$.
    108 
    109 **Solution**
    110 
    111 ```
    112 #include<bits/stdc++.h>
    113 using namespace std ;
    114 
    115 #define ll              long long 
    116 #define pb              push_back
    117 #define all(v)          v.begin(),v.end()
    118 #define sz(a)           (ll)a.size()
    119 #define F               first
    120 #define S               second
    121 #define INF             2000000000000000000
    122 #define popcount(x)     __builtin_popcountll(x)
    123 #define pll             pair<ll,ll>
    124 #define pii             pair<int,int>
    125 #define ld              long double
    126 
    127 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
    128 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
    129 
    130 #ifdef LOCAL
    131 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
    132 #else
    133 #define debug(...) 2401
    134 #endif
    135 
    136 int _runtimeTerror_()
    137 {
    138     int n;
    139     cin >> n;
    140     int ans = (1 << 30) - 1;
    141     for(int i=0;i<n;++i) {
    142     	int x;
    143     	cin >> x;
    144     	if(x != i) {
    145     		ans &= x;
    146     	}
    147     }
    148     cout << ans << "\n";
    149     return 0;
    150 }
    151 
    152 int main()
    153 {
    154     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    155     #ifdef runSieve
    156         sieve();
    157     #endif
    158     #ifdef NCR
    159         initncr();
    160     #endif
    161     int TESTS = 1;
    162     cin >> TESTS;
    163     while(TESTS--) {
    164         _runtimeTerror_();
    165     }
    166     return 0;
    167 }
    168 ```
    169 
    170 # [1682C — LIS or Reverse LIS?](https://codeforces.com/contest/1682/problem/C)
    171 
    172 **Hint**
    173 
    174 Let $\text{LDS}(a)$ be the longest strictly decreasing subsequence of $a$, then $\text{LIS}(a')$ = $\text{LDS}(a)$.
    175 
    176 There can be at most one index common between $\text{LIS}(a)$ and $\text{LDS}(a)$.
    177 
    178 **Tutorial**
    179 
    180 Let's make a small observation:
    181 
    182 * There can be at most one index common to both $\text{LIS}(a)$ and $\text{LDS}(a)$.
    183 
    184 If some element $x$ occurs $\geq 2$ times, then one of its occurrences can be included in $\text{LIS}(a)$ and another one in $\text{LDS}(a)$, and all the remaining occurrences are of no use because none of them can contain 2 equal elements.
    185 
    186 If some element $x$ is a singleton i.e. the frequency of $x$ in $a$ is $1$, then it can have $3$ positions
    187 
    188 * In $\text{LIS}(a)$ only.
    189 * In $\text{LDS}(a)$ only.
    190 * The only common element of $\text{LIS}(a)$ and $\text{LDS}(a)$.
    191 
    192 It can be seen that it is always optimal to choose some singleton as the only common element (if available) because those with frequency $\geq 2$ can easily contribute $1$ to both $\text{LIS}(a)$ and $\text{LDS}(a)$ easily.
    193 
    194 Let $t$ be the number of elements having frequency $\geq 2$ and $s$ be the number of singletons in $a$. The singletons should be divided equally among $\text{LIS}(a)$ and $\text{LDS}(a)$ with one of them given to both, if available.
    195 
    196 Hence, the answer is $t + \lceil \frac{s}{2} \rceil$.
    197 
    198 The values $s$ and $t$ can be found using some data structure like $\text{std:map}$ in C++ in $\mathcal{O}(n\log(n))$.
    199 
    200 **Solution**
    201 
    202 ```
    203 #include<bits/stdc++.h>
    204 using namespace std ;
    205 
    206 #define ll              long long 
    207 #define pb              push_back
    208 #define all(v)          v.begin(),v.end()
    209 #define sz(a)           (ll)a.size()
    210 #define F               first
    211 #define S               second
    212 #define INF             2000000000000000000
    213 #define popcount(x)     __builtin_popcountll(x)
    214 #define pll             pair<ll,ll>
    215 #define pii             pair<int,int>
    216 #define ld              long double
    217 
    218 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
    219 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
    220 
    221 #ifdef LOCAL
    222 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
    223 #else
    224 #define debug(...) 2401
    225 #endif
    226 
    227 int _runtimeTerror_()
    228 {
    229     int n;
    230     cin >> n;
    231     map<int, int> mp;
    232     for(int i=1;i<=n;++i) {
    233     	int x;
    234     	cin >> x;
    235     	++mp[x];
    236     }
    237     int single = 0, doble = 0;
    238     for(auto &[i, j]:mp) {
    239     	single += j == 1;
    240     	doble += j > 1;
    241     }
    242     cout << doble + (single + 1) / 2 << "\n";
    243     return 0;
    244 }
    245 
    246 int main()
    247 {
    248     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    249     #ifdef runSieve
    250         sieve();
    251     #endif
    252     #ifdef NCR
    253         initncr();
    254     #endif
    255     int TESTS = 1;
    256     cin >> TESTS;
    257     while(TESTS--) {
    258         _runtimeTerror_();
    259     }
    260     return 0;
    261 }
    262 ```
    263 
    264 # [1682D — Circular Spanning Tree](https://codeforces.com/contest/1682/problem/D)
    265 
    266 **Hints**
    267 
    268 **Hint 1**
    269 
    270 What are the mandatory conditions on string $s$ for a tree to be possible?
    271 
    272 **Hint 2**
    273 
    274 If there are no odd degree vertices or the count of odd degree vertices is odd, then it is impossible to construct any tree. It turns out that these conditions are sufficient too.
    275 
    276 **Tutorial**
    277 
    278 Let's check some cases when it is not possible to construct the answer-
    279 
    280 * When all vertices have an even degree, then there is no way to generate a tree because every tree contains at least $2$ leaves.
    281 * When there are an odd number of vertices with odd degrees, then there is no tree possible because the sum of degrees must be even.
    282 
    283 It turns out that it is always possible to construct a tree if none of the above is true.
    284 
    285 The following construction works -
    286 
    287 * Select some vertex $i$ such that the previous vertex of $i$ (assumed cyclically) has an odd degree i.e. $s_{i - 1} = 1$. Clearly, such a vertex always exists.
    288 * Now left rotate $s$, $i - 1$ times such that the selected vertex is now at index $1$. Note that after the rotation $s_n$ will become $1$. Now we can see that $s[2\ldots n]$ can be divided into several segments such that each segment ends with some vertex having an odd degree. And each segment should contain exactly one vertex with an odd degree. So $s[2 \ldots n] = [0\ldots 1][0\ldots 1] \ldots [0\ldots 1]$ where $0$ may appear $0$ times. Connect vertex $1$ to the starting vertex of each segment and connect adjacent vertices inside each segment. It can be clearly seen that edges will never intersect internally. The only thing we need to verify is the degree constraints.
    289 
    290 **Proof**:
    291 
    292 * The degree condition is valid for each segment, as each vertex with an even degree is connected with $2$ other vertices and the last vertex with an odd degree will be connected to only one vertex i.e it's previous one or vertex $1$ if it was only on its segment.
    293 * Let $cnt_1$ be the number of vertices with odd degree. If $s_1 = 1$, then there will be $cnt_1 - 1$ segments which is an odd number, hence vertex $1$ will be connected to odd number of vertices. If $s_1 = 0$, then there will be $cnt_1$ segments which is an even number, hence vertex $1$ will be connected to even number of vertices.
    294 
    295 Note that we renumbered the vertices during rotation which should be handled in implementation.
    296 
    297 The intuition for the above approach comes from the case when all $s_i$ are $1$ in which we create a star network.
    298 
    299 Overall complexity: $\mathcal{O(n)}$.
    300 
    301 **Solution**
    302 
    303 ```
    304 #include<bits/stdc++.h>
    305 using namespace std;
    306 
    307 #define all(v)         v.begin(),v.end()
    308 #define endl           "\n"
    309 
    310 int solve(){
    311  		int n; cin >> n;
    312  		string s; cin >> s;
    313  		auto cnt = count(all(s),'1');
    314  		if(cnt == 0 or cnt & 1){
    315  			cout << "NO" << endl;
    316  			return 0;
    317  		}
    318  		auto inc = [&](int j){
    319 		 	return (j + 1)%n;
    320 		};
    321  		cout << "YES" << endl;
    322  		for(int p = 1; p < n; p++){
    323  			if(s[p - 1] == '1'){
    324 		 		auto i = inc(p);
    325 		 		while(i != p){
    326 		 			int j = i;
    327 		 			int prev = p;
    328 		 			while(j != p){
    329 		 				cout << prev + 1 << " " << j + 1 << endl;
    330 		 				prev = j;
    331 		 				j = inc(j);
    332 		 				if(s[prev] == '1')break;
    333 		 			}
    334 		 			i = j;
    335 		 		}
    336 		 		return 0;
    337  			}
    338  		}
    339 
    340  return 0;
    341 }
    342 signed main(){
    343     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    344     //freopen("input.txt", "r", stdin);
    345     //freopen("output.txt", "w", stdout);
    346     #ifdef SIEVE
    347     sieve();
    348     #endif
    349     #ifdef NCR
    350     init();
    351     #endif
    352     int t=1;cin>>t;
    353     while(t--){
    354         solve();
    355     }
    356     return 0;
    357 }
    358 ```
    359 
    360 # [1682E — Unordered Swaps](https://codeforces.com/contest/1682/problem/E)
    361 
    362 **Tutorial**
    363 
    364 One way of solving permutation problems is to look at permutation cycles. Let's decompose our permutation into cycles, then it's easy to see that each cycle can be solved independently because we have to sort the permutation in a minimum number of moves which isn't possible if two cycles are merged at any instant.
    365 
    366 Let's look at one cycle only, whose vertices are numbered from $1$ to $n$ in the orientation of cycle i.e the cycle is $1 \rightarrow 2 \rightarrow \ldots \rightarrow n \rightarrow 1$. Also assume that we only have swaps $(x, y)$ that are relevant to this cycle.
    367 
    368 It is known that we can sort a cycle of size $n$ in $n - 1$ moves and it is the minimum number of required moves.
    369 
    370 **Claim 1:** The set of swaps if considered as edges $(x, y)$ form a tree on the $n$ vertices of the cycle.
    371 
    372 **Proof**
    373 
    374 Assume that the edges don't form a tree, then there exist at least two disjoint components let's say $S$ and $T$. Now we must be able to make swaps inside $S$ only, to sort elements in $S$ which needs that the set {$i, i \in S$} is same as set {$p_i, i \in S$} which is not possible by property of permutation cycles. Any cycle of permutation, say $C$, can't be split further into two sets $S$ and $T$ such that both of them can be sorted independently among themselves.
    375 
    376 So we must use all the $n - 1$ edges of the tree in some order to get $n$ cycles each of size $1$.
    377 
    378 Let's consider any element $u$ having adjacency list as $[x_1, x_2, ..., x_k]$ in the order they appear on the cycle if we start moving from $u$ in the orientation of cycle i.e $u \rightarrow u + 1 \rightarrow ... \rightarrow n \rightarrow 1 \rightarrow ... \rightarrow u$.
    379 
    380 **Claim 2:** We can never make the swap $(u, x_j)$ before swap $(u, x_i)$ if $j \gt i$.
    381 
    382 **Proof**
    383 
    384 If we make the swap $(u, x_j)$ first, then $u$ and $x_i$ will go in different cycles for subsequent operations and we will never be able to use edge $(u, x_i)$ because it will merge the two different cycles which isn't possible because we are constrained to break a cycle into smaller cycles only.
    385 
    386 And if are not able to use edge $(u, x_i)$ then we will never be able to sort the permutation because we had $n - 1$ edges all of which were to be used and we wasted $1$ of them.
    387 
    388 Using above claim, for every element $u$ the order of edges is fixed i.e $x_1$, then $x_2$, ..., and finally $x_k$.
    389 
    390 Let's build a directed graph on $n - 1$ vertices (representing the swaps) where for every element $u$ we add directed edges $(u,x_1) \rightarrow (u,x_2)$, ..., $(u,x_{k-1}) \rightarrow (u,x_k)$.
    391 
    392 Since it is guaranteed that the answer will exist i.e a valid sequence of moves exist, hence the topological sorting of the above graph must exist, any of which represents a correct sequence of swaps.
    393 
    394 Note that whenever we make a swap that is not violating claim $2$ for any element $u$, then there will be no cross edge in two smaller cycles that are going to be formed and those smaller cycles can be further solved independently. Also the order of edges i.e $[x_1, x_2, ..., x_k]$ is not going to change for any element which ensures that the directed graph we built remains correct even if we remove some appropriate edge.
    395 
    396 Hence the answer is simply the topological sort of the graph we built.
    397 
    398 Overall Complexity: $\mathcal{O(nlog(n))}$, $nlog(n)$ for sorting the edges according to cycle's orientation to get the order $[x_1, x_2, ..., x_k]$ for every vertex.
    399 
    400 **Some other interesting things about this problem**
    401 
    402 **Claim:** The given swaps considered as edges $(x, y)$ forms a non-intersecting tree on $n$ vertices on the circle i.e no two edges intersect internally.  ~~Motivation for problem D~~
    403 
    404 **Proof**
    405 
    406 Let's say edges $(a, b)$ and $(c, d)$ intersect internally in the circle.
    407 
    408 WLOG, let's suppose we make swap $(a, b)$ before swap $(c, d)$, then $c$ and $d$ will go in different cycles as in Claim $2$ above.
    409 
    410 What if you were given any tree on $n$ vertices and asked to solve the problem with "YES/NO"?
    411 
    412 * If the given edges intersect internally in the circle then the answer is "NO" otherwise it's always possible to construct a valid sequence of swaps. This is what the validator of E and checker of D do, try this one, and feel free to discuss in the comments section.
    413 
    414 **Validator**
    415 
    416 Let's make every edge $(u, v)$ such that $u \lt v$, clearly the order of $u$, $v$ doesn't matter.
    417 
    418 Consider each edge as a segment $[u, v]$, then the edges of the tree intersect internally if and only if any two segments say $[l_1, r_1]$ and $[l_2, r_2]$ satisfies any of the below conditions-
    419 
    420 1. $l_1\lt l_2 \lt r_1 \lt r_2$
    421 2. $l_2 \lt l_1 \lt r_2 \lt r_1$
    422 
    423 In the original problem, it was mentioned that there is always a correct sequence of swaps so we claimed that topological sorting must exist and indeed any topological sorting suffices. What if we were given a non-intersecting spanning tree? Can we still claim that there exists a correct move at every step?
    424 
    425 **Claim:** Yes, we can
    426 
    427 **Proof**
    428 
    429 We need to show that there there is always some edge that can be removed without breaking claim $2$ above which is the only required condition.
    430 
    431 Cycles of length $\le 2$ are trivial.
    432 
    433 Let's represent by $u_{next}$ the first element of the list $[x_1, x_2, ..., x_k]$ for $u$ i.e the closest vertex having an edge with $u$ in cycle's orientation.
    434 
    435 Now, let's start an iteration, start moving from $1$ and jump to $v_{next}$ every time when you are at vertex $v$. Continue this process until you again reach $1$ or cross over $1$.
    436 
    437 Let the sequence obtained be $s$ i.e $s_1 = 1, s_2, ..., s_k$ where on moving further from $s_k$ we cross/reach $1$. For simplicity assume $k \ge 3$, $k = 2$ is trivial.
    438 
    439 It can be shown that $(s_{k-1}, s_k)$ is the required edge.
    440 
    441 **Proof**
    442 
    443 $s_{k_{next}}$ lies between $s_{k-1}$ and $s_k$. There are three cases other that this:
    444 
    445 1. $s_{k_{next}}$ lies between $s_k$ and $1$, which is not possible because we would have moved further and $s_k$ would not be the last element of sequence $s$.
    446 2. $s_{k_{next}}$ = $1$ which is not possible because it will create a cycle and we are given a tree.
    447 3. $s_{k_{next}}$ lies between $s_j$ and $s_{j+1}$ for $j \le k-2$, this is also not possible because then the edges $(s_k, s_{k_{next}})$ and $(s_j, s_{j+1})$ will intersect and we are given a non-intersecting tree.
    448 
    449 $s_{k}$ is first element of adjacency list of $s_{k-1}$ by the definition of $v_{next}$ and $s_{k-1}$ is the first element of adjacency list of $s_{k}$ by above 3 points.
    450 
    451 Hence it is safe to make the swap $(s_{k-1}, s_{k})$.
    452 
    453 So the topological sort still works.
    454 
    455 This might not be the only proof, if you have some other proofs feel free to discuss them in the comments.
    456 
    457 Hope you liked the details!!
    458 
    459 **Generator**
    460 
    461 Any ideas on how to write a generator for this problem?
    462 
    463 **My Approach**
    464 
    465 Randomly partition the permutation into cycles, so generating swaps for a particular cycle is the main issue.
    466 
    467 Let's represent the cycle by an array $a$ of size $n$ with cycle as $a_1 \rightarrow a_2 \rightarrow ... \rightarrow a_n \rightarrow a_1$ Now let's start making random swaps say $(a_i, a_j)$ to break the cycle, then this generates two smaller cycles -
    468 
    469 1. $a_1 \rightarrow a_2 \rightarrow ... \rightarrow a_i \rightarrow a_{j+1} \rightarrow ... \rightarrow a_n \rightarrow a_1$.
    470 2. $a_{i+1} \rightarrow ... \rightarrow a_j \rightarrow a_{i+1}$.
    471 
    472 This can be easily done using treaps :) and then we can use recursion to solve them independently.
    473 
    474 **Review by Anton Sir**
    475 
    476 ![](/predownloaded/96/98/96985ce759c84fe197eb54c5405d552c788485d4.png)
    477 
    478 It's very rare!! Atleast first time for us.
    479 
    480 **Solution**
    481 
    482 ```
    483 #include<bits/stdc++.h>
    484 using namespace std ;
    485 
    486 #define ll              long long 
    487 #define pb              push_back
    488 #define all(v)          v.begin(),v.end()
    489 #define sz(a)           (ll)a.size()
    490 #define F               first
    491 #define S               second
    492 #define INF             2000000000000000000
    493 #define popcount(x)     __builtin_popcountll(x)
    494 #define pll             pair<ll,ll>
    495 #define pii             pair<int,int>
    496 #define ld              long double
    497 
    498 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
    499 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
    500 
    501 #ifdef LOCAL
    502 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
    503 #else
    504 #define debug(...) 2401
    505 #endif
    506 
    507 const int N = 2e5 + 5;
    508 vector<int> t_sort;
    509 int idx[N];
    510 int vs[N];
    511 vector<int> v[N];
    512 
    513 bool dfs_sort(int u)
    514 {
    515     vs[u]=2;
    516     for(auto j:v[u])
    517     {
    518         if(vs[j]==2)
    519             return true;
    520         if(vs[j]==0 && dfs_sort(j))
    521             return true;
    522     }
    523     vs[u]=1;
    524     t_sort.push_back(u);
    525     return false;
    526 }
    527 
    528 // Returns true if there is a topological sort else returns false
    529 bool top_sort(int n)
    530 {
    531     t_sort.clear();
    532     for(int i=1;i<=n;++i)
    533         vs[i]=0;
    534     for(int i=1;i<=n;++i)
    535     {
    536         if(vs[i]==0)
    537         {
    538             if(dfs_sort(i))
    539             {
    540                 t_sort.clear();
    541                 return false;
    542             }
    543         }
    544     }
    545     reverse(t_sort.begin(),t_sort.end());
    546     assert(t_sort.size()==n);
    547     for(int i=0;i<n;++i)
    548         idx[t_sort[i]]=i;
    549     return true;
    550 }
    551 
    552 int _runtimeTerror_()
    553 {
    554     int n, k;
    555     cin >> n >> k;
    556     vector<int> p(n+1), a(k), b(k);
    557     for(int i=1;i<=n;++i) {
    558         cin >> p[i];
    559     }
    560 
    561     vector<vector<pii>> g(n+1);
    562     for(int i=0;i<k;++i) {
    563         int x, y;
    564         cin >> x >> y;
    565         a[i] = x, b[i] = y;
    566         g[x].push_back({y, i + 1});
    567         g[y].push_back({x, i + 1});
    568     }    
    569     vector<int> id(n+1);
    570     vector<int> ans;
    571     auto solve = [&](vector<int> &cyc) {
    572         int n = sz(cyc);
    573         if(n == 1) {
    574             return;
    575         }
    576         for(int i=0;i<n;++i) {
    577             id[cyc[i]] = i;
    578         }
    579         auto dist = [&](int x, int y) {
    580             return (id[y] - id[x] + n) % n;
    581         };
    582         vector<int> good;
    583         for(int i:cyc) {
    584             sort(all(g[i]), [&](pii &a, pii &b) {
    585                 return dist(i, a.F) < dist(i, b.F);
    586             });
    587             for(int j=1;j<sz(g[i]);++j) {
    588                 v[g[i][j-1].S].push_back(g[i][j].S);
    589             }
    590         }
    591     };
    592     vector<bool> vis(n+1);
    593     for(int i=1;i<=n;++i) {
    594         if(vis[i]) {
    595             continue;
    596         }   
    597         vector<int> cycle;
    598         int cur = i;
    599         while(!vis[cur]) {
    600             cycle.push_back(cur);
    601             vis[cur] = 1;
    602             cur = p[cur];
    603         }
    604         solve(cycle);
    605     }
    606     top_sort(k);
    607     for(auto i:t_sort) {
    608         cout << i << " ";
    609     }
    610     cout << "\n";
    611     return 0;
    612 }
    613 
    614 int main()
    615 {
    616     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    617     #ifdef runSieve
    618         sieve();
    619     #endif
    620     #ifdef NCR
    621         initncr();
    622     #endif
    623     int TESTS = 1;
    624     //cin >> TESTS;
    625     while(TESTS--) {
    626         _runtimeTerror_();
    627     }
    628     return 0;
    629 }
    630 ```
    631 
    632 # [1682F — MCMF?](https://codeforces.com/contest/1682/problem/F)
    633 
    634 **Tutorial**
    635 
    636 Let us suppose we need to calculate the answer for only one query, say complete array i.e $a[1:n]$.
    637 
    638 The scary flow structure in the problem can be reduced as-
    639 
    640 Let's replicate each vertex $i$, $|b_i|$ times. Then we can see that there will be an equal number of vertices on the left and right side. Now the problem reduces that we have to match these vertices with minimum cost such that the cost of matching $i$ and $j$ is $|a_i - a_j|$.
    641 
    642 There are only 2 type of elements (left side and right side) and the following greedy algorithm to match the elements works.
    643 
    644 Algorithm: Sort the type $1$ and $2$ elements independently and match them in the sorted order.
    645 
    646 **Proof**
    647 
    648 Assume that two elements from left $l_1 \le l_2$ are matched with two elements from right $r_1 \le r_2$ as $[l_1, r_2]$ and $[l_2, r_1]$, then it can be easily shown that matching $[l_1, r_1]$ and $[l_2, r_2]$ is always more optimal. The proof is left as an excercise to reader.
    649 
    650 Since the array $a$ is given in sorted order, let's use it!!
    651 
    652 Let's assume-
    653 
    654 * Type $1$ elements are those having $b_i \lt 0$.
    655 * Type $2$ elements are those having $b_i \gt 0$.
    656 
    657 Now instead of replicating elements $|b_i|$ times and sorting them independently, let's iterate on array $a$ from left to right and add the contribution of each element independently. Say we are at index $i$, and prefix sum of $b_i$ so far is $psum_i$, then the following cases arise-
    658 
    659 * $b_i \gt 0$, $psum_i \ge 0$ — There is no unmatched type $1$ element on the left, so we just add this element's contribution to the answer i.e $-b_i \cdot a_i$.
    660 * $b_i \gt 0$, $psum_i \lt -b_i$ — There are more than $b_i$ unmatched type $1$ elements on the left, so we match $b_i$ of them to $a_i$, adding a contribution of $a_i \cdot b_i$ to the answer.
    661 * $b_i \gt 0$, $psum_i \lt 0$ and $psum_i \gt -b_i$ — There are less than $b_i$ unmatched elements ($= |psum_i|$) on the left, so we match those with equal number of $a_i$ and remaining are propagated further, adding a contribution of $|psum_i| * a_i - (b_i - |psum_i|) * a_i$, where the positive term comes from those matching with previous unmatched elements and the negative term comes from those that are going to be left unmatched.
    662 
    663 Similar cases are there for $b_i \lt 0$.
    664 
    665 Ok so now we can easily solve the problem for one query in $O(n)$.
    666 
    667 **Main idea**:
    668 
    669 Let's simulate the above algorithm for every suffix and record the obtained answer in $ans_i$ for $i^{th}$ suffix. Note that the value $ans_i$ doesn't denote any answer for some suffix because the sum of $b_i$ over that suffix might or might not be zero. One important observation here is that-
    670 
    671 * Let some subarray $a[l:r]$ for which sum of $b_i$ is $0$, then $ans_l - ans_{r+1}$ do have a good meaning, it's the answer for that query indeed.
    672 
    673 **Proof**
    674 
    675 Our answer for $a[l:r]$ would have been the result of simulation on the subarray, but how does simulation on $l^{th}$ suffix looks?
    676 
    677 It greedily matches the subarray $a[l:r]$ first because the sum of $b_i$ is zero, so it will surely pair up all elements in that subarray. Then it moves further on $r+1$ and continuing the simulation after $r+1$ is equivalent to starting the simulation from $r+1$ itself because $psum$ so far (defined above) would be automatically 0.
    678 
    679 Note that $ans_l$ doesn't have any physical meaning because it will add some junk value if elements after $r+1$ are not paired up equally but those junk values are exactly same in $ans_l$ and $ans_r$ which cancel out, giving the correct answer.
    680 
    681 But still, we can't simulate for every suffix, right? It would go $O(n^2)$ again.
    682 
    683 Let's iterate from left to right and for every $i$ try calculating it's contribution in $1^{st}$, $2^{nd}$, ..., $(i-1)^{th}$ suffixes which is easy because it depends only on $psum_i$, $b_i$ (which are constant for a given $i$) and $psum_l$ for contribution to $l^{th}$ suffix. This is pretty standard using $2$ fenwick trees.
    684 
    685 **How to calculate $ans_i$?**
    686 
    687 Let's solve $b_i \gt 0$ and $b_i \lt 0$ independently, say $b_i \gt 0$ for now. Other case is similar.
    688 
    689 Let $psum_i = \sum_{j=1}^{i}b_j$.
    690 
    691 Consider the contribution of index $i$ to $ans_l$ for $l \lt i$, from three cases described above the contribution is different for different $l$ with different $psum_l$. We can build a fenwick tree on compressed prefix sums. Case $1$ and $2$ above add a constant value to a range of prefix sums that can be maintained in one fenwick tree and Case $2$ gives some linear function of $psum$ to be added in a range that can be maintained in other fenwick tree. Add contribution of each $i$ from $1$ to $n$ first, and let's start calculating $ans_i$.
    692 
    693 * For $i = 1$, $ans_1$ can be obtained by querying at $psum_1$ in both fenwicks.
    694 * Then we remove the contribution of $i = 1$ from the two fenwick trees (simply the negative of which we added above), because $i = 1$ won't be contributing to any suffix other than $1^{st}$ one.
    695 * Similarly we move from left to right and calculate $ans_i$ by querying at $psum_i$ and then remove the contribution of $i^{th}$ element.
    696 
    697 **Solution**
    698 
    699 ```
    700 #include<bits/stdc++.h>
    701 using namespace std ;
    702 
    703 #define ll              long long 
    704 #define pb              push_back
    705 #define all(v)          v.begin(),v.end()
    706 #define sz(a)           (ll)a.size()
    707 #define F               first
    708 #define S               second
    709 #define INF             2000000000000000000
    710 #define popcount(x)     __builtin_popcountll(x)
    711 #define pll             pair<ll,ll>
    712 #define pii             pair<int,int>
    713 #define ld              long double
    714 
    715 template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
    716 template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
    717 
    718 #ifdef LOCAL
    719 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
    720 #else
    721 #define debug(...) 2401
    722 #endif
    723 
    724     
    725 const int MOD=1000000007;
    726 struct Mint {
    727     int val;
    728  
    729     Mint(long long v = 0) {
    730         if (v < 0)
    731             v = v % MOD + MOD;
    732         if (v >= MOD)
    733             v %= MOD;
    734         val = v;
    735     }
    736  
    737     static int mod_inv(int a, int m = MOD) {
    738         int g = m, r = a, x = 0, y = 1;
    739         while (r != 0) {
    740             int q = g / r;
    741             g %= r; swap(g, r);
    742             x -= q * y; swap(x, y);
    743         } 
    744         return x < 0 ? x + m : x;
    745     } 
    746     explicit operator int() const {
    747         return val;
    748     }
    749     Mint& operator+=(const Mint &other) {
    750         val += other.val;
    751         if (val >= MOD) val -= MOD;
    752         return *this;
    753     }
    754     Mint& operator-=(const Mint &other) {
    755         val -= other.val;
    756         if (val < 0) val += MOD;
    757         return *this;
    758     }
    759     static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    760            #if !defined(_WIN32) || defined(_WIN64)
    761                 return x % m;
    762            #endif
    763            unsigned x_high = x >> 32, x_low = (unsigned) x;
    764            unsigned quot, rem;
    765            asm("divl %4\n"
    766             : "=a" (quot), "=d" (rem)
    767             : "d" (x_high), "a" (x_low), "r" (m));
    768            return rem;
    769     }
    770     Mint& operator*=(const Mint &other) {
    771         val = fast_mod((uint64_t) val * other.val);
    772         return *this;
    773     }
    774     Mint& operator/=(const Mint &other) {
    775         return *this *= other.inv();
    776     }
    777     friend Mint operator+(const Mint &a, const Mint &b) { return Mint(a) += b; }
    778     friend Mint operator-(const Mint &a, const Mint &b) { return Mint(a) -= b; }
    779     friend Mint operator*(const Mint &a, const Mint &b) { return Mint(a) *= b; }
    780     friend Mint operator/(const Mint &a, const Mint &b) { return Mint(a) /= b; }
    781     Mint& operator++() {
    782         val = val == MOD - 1 ? 0 : val + 1;
    783         return *this;
    784     }
    785     Mint& operator--() {
    786         val = val == 0 ? MOD - 1 : val - 1;
    787         return *this;
    788     }
    789     Mint operator++(int32_t) { Mint before = *this; ++*this; return before; }
    790     Mint operator--(int32_t) { Mint before = *this; --*this; return before; }
    791     Mint operator-() const {
    792         return val == 0 ? 0 : MOD - val;
    793     }
    794     bool operator==(const Mint &other) const { return val == other.val; }
    795     bool operator!=(const Mint &other) const { return val != other.val; }
    796     Mint inv() const {
    797         return mod_inv(val);
    798     }
    799     Mint power(long long p) const {
    800         assert(p >= 0);
    801         Mint a = *this, result = 1;
    802         while (p > 0) {
    803             if (p & 1)
    804                 result *= a;
    805  
    806             a *= a;
    807             p >>= 1;
    808         }
    809         return result;
    810     }
    811     friend ostream& operator << (ostream &stream, const Mint &m) {
    812         return stream << m.val;
    813     }
    814     friend istream& operator >> (istream &stream, Mint &m) {
    815         return stream>>m.val;   
    816     }
    817 };
    818 
    819 template<typename T=long long>
    820 struct fenwick {
    821     vector<T> bit;
    822     int n;
    823     fenwick(int x) {
    824         n = x;
    825         bit.resize(x + 1, T(0));
    826     }
    827     void update(int j,T val)
    828     {
    829         for(;j<=n;j+=j&-j)
    830             bit[j] += val;
    831     }
    832     T get(int r)
    833     {
    834         T u = 0;
    835         for(;r;r-=r&-r)
    836             u += bit[r]; 
    837         return u;
    838     }
    839     T query(int l,int r)
    840     {
    841         return get(r)-get(l-1);
    842     }
    843     // kth element
    844     int getKth(T k) {
    845         int ans = 0;
    846         T cnt = 0;
    847         for(int i=20;i>=0;--i) {
    848             if(ans + (1 << i) <= n && cnt + bit[ans + (1 << i)] < k) {
    849                 ans += (1 << i);
    850                 cnt += bit[ans];
    851             }
    852         }
    853         if(ans == n) {
    854             return -1;
    855         }
    856         return ans + 1;
    857     }
    858     void insert(int x) {
    859         update(x, 1);
    860     }
    861     void erase(int x) {
    862         update(x, -1);
    863     }
    864 };
    865 int _runtimeTerror_()
    866 {
    867     int n;
    868     int Q;
    869     cin >> n >> Q;
    870     vector<array<int,2>> a(n);
    871     for(int i=0;i<n;++i) {
    872         cin >> a[i][0];
    873     }
    874     for(int i=0;i<n;++i) {
    875         cin >> a[i][1];
    876     }
    877     vector<Mint> val(n, 0);
    878     for(int i=n-1;i>=0;--i) {
    879         if(i < n - 1) {
    880             val[i] = val[i + 1];
    881         }
    882         val[i] += a[i][0] * Mint(abs(a[i][1]));
    883     }
    884     auto solve = [&](vector<array<int,2>> &a) {
    885 
    886         ll psum = 0;
    887         vector<ll> psums;
    888         psums.push_back(0);
    889         for(int i=0;i<n;++i) {
    890             psum += a[i][1];
    891             assert(a[i][1] != 0);
    892             psums.push_back(psum);
    893         }
    894         sort(all(psums));
    895         psums.resize(unique(all(psums)) - psums.begin());
    896         psum = 0;
    897         auto get_next = [&](ll x) {
    898             return lower_bound(all(psums), x) - psums.begin() + 1;
    899         };
    900         fenwick<Mint> f1(2*n), f2(2*n), f3(2*n);
    901         for(int i=0;i<n;++i) {
    902             if(a[i][1] > 0) {
    903                 f1.update(1, Mint(a[i][1]) * a[i][0]);
    904                 f1.update(get_next(psum), -Mint(a[i][1]) * a[i][0]);
    905 
    906                 f2.update(get_next(psum), a[i][0]);
    907                 f2.update(get_next(psum + a[i][1]), -a[i][0]);
    908 
    909                 f3.update(get_next(psum), Mint(a[i][0]) * Mint(psum + a[i][1]));
    910                 f3.update(get_next(psum + a[i][1]), -Mint(a[i][0]) * (psum + a[i][1]));
    911             }
    912             psum += a[i][1];
    913         }   
    914         psum = 0;
    915         for(int i=0;i<n;++i) {
    916             val[i] -= 2 * f1.get(get_next(psum));
    917 
    918             val[i] -= 2 * (f3.get(get_next(psum)) - psum * f2.get(get_next(psum)));
    919             if(a[i][1] > 0) {
    920                 
    921                 f1.update(1, -Mint(a[i][1]) * a[i][0]);
    922                 f1.update(get_next(psum), Mint(a[i][1]) * a[i][0]);
    923 
    924                 f2.update(get_next(psum), -a[i][0]);
    925                 f2.update(get_next(psum + a[i][1]), a[i][0]);
    926 
    927                 f3.update(get_next(psum), -Mint(a[i][0]) * Mint(psum + a[i][1]));
    928                 f3.update(get_next(psum + a[i][1]), Mint(a[i][0]) * (psum + a[i][1]));
    929             }
    930             psum += a[i][1];
    931         }
    932     };
    933     solve(a);
    934     for(int i=0;i<n;++i) {  
    935         a[i][1] = -a[i][1];
    936     }
    937     solve(a);   
    938     val.push_back(0);
    939     while(Q--) {
    940         int l, r;
    941         cin >> l >> r;
    942         --l, --r;
    943         cout << val[l] - val[r + 1] << "\n";
    944     }
    945     return 0;
    946 }
    947 
    948 int main()
    949 {
    950     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    951     #ifdef runSieve
    952         sieve();
    953     #endif
    954     #ifdef NCR
    955         initialize();
    956     #endif
    957     int TESTS = 1;
    958     //cin >> TESTS;
    959     while(TESTS--)
    960         _runtimeTerror_();
    961     return 0;
    962 }
    963 ```