1957.md (30540B)
1 Source: https://codeforces.com/blog/entry/128716 2 3 # [1957A - Stickogon](/contest/1957/problem/A "Codeforces Round 940 (Div. 2) and CodeCraft-23") 4 5 **Idea:** [keyurchd_11](/profile/keyurchd_11 "Master keyurchd_11") 6 **Problem Setting:** [shakr](/profile/shakr "Expert shakr") [lezirtin](/profile/lezirtin "Expert lezirtin") 7 **Editorial**: [shakr](/profile/shakr "Expert shakr") [TheRaja](/profile/TheRaja "Candidate Master TheRaja") 8 9 There were a few solutions which passes pre-tests with the assumption that $a_i \leq n$. We apologize for the pre-tests on A not including this case. 10 11 **Hint 1** 12 13 To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides? 14 15 **Solution** 16 17 Tutorial is loading... 18 19 **Rate this problem** 20 21 * Great Problem 22 * Ok Problem 23 * Bad Problem 24 * Didn't solve 25 26 **C++ Code** 27 28 ``` 29 #include <bits/stdc++.h> 30 31 using namespace std; 32 33 int main(){ 34 int t; 35 cin >> t; 36 while(t--) { 37 int n; 38 cin >> n; 39 vector<int> a(101, 0); 40 for (int i = 0; i < n; i++) { 41 int x; 42 cin >> x; 43 a[x]++; 44 } 45 int sum = 0; 46 for (auto& s : a) 47 sum += s / 3; 48 cout << sum << "\n"; 49 } 50 } 51 ``` 52 53 # [1957B - A BIT of a Construction](/contest/1957/problem/B "Codeforces Round 940 (Div. 2) and CodeCraft-23") 54 55 **Idea:** [akcube](/profile/akcube "Master akcube") 56 **Problem Setting:** [Prakul_Agrawal](/profile/Prakul_Agrawal "Specialist Prakul_Agrawal") 57 **Editorial**: [Prakul_Agrawal](/profile/Prakul_Agrawal "Specialist Prakul_Agrawal") [TheRaja](/profile/TheRaja "Candidate Master TheRaja") 58 59 **Hint 1** 60 61 Given that the sum is bounded, which bits could be set in the bitwise OR? 62 63 **Solution** 64 65 Tutorial is loading... 66 67 **Rate this problem** 68 69 * Great Problem 70 * Ok Problem 71 * Bad Problem 72 * Didn't solve 73 74 **C++ Code** 75 76 ``` 77 #include <bits/stdc++.h> 78 79 using namespace std; 80 81 int main(){ 82 int t; 83 cin >> t; 84 while(t--) { 85 int n, k; 86 cin >> n >> k; 87 vector<int> a(n); 88 if (n == 1) { 89 a[0] = k; 90 } 91 else { 92 int msb = 0; 93 // find the msb of k 94 for (int i = 0; i < 31; i++) { 95 if (k & (1 << i)) { 96 msb = i; 97 } 98 } 99 a[0] = (1 << msb) - 1; 100 a[1] = k - a[0]; 101 for (int i = 2; i < n; i++) { 102 a[i] = 0; 103 } 104 } 105 for (int i = 0; i < n; i++) { 106 cout << a[i] << " "; 107 } 108 cout << "\n"; 109 } 110 return 0; 111 } 112 ``` 113 114 # [1957C - How Does the Rook Move?](/contest/1957/problem/C "Codeforces Round 940 (Div. 2) and CodeCraft-23") 115 116 **Idea:** [SilverTongue1729](/profile/SilverTongue1729 "Expert SilverTongue1729") 117 **Problem Setting:** [ppt1524](/profile/ppt1524 "Expert ppt1524") [GenghizKhan](/profile/GenghizKhan "Candidate Master GenghizKhan") 118 **Editorial**: [ppt1524](/profile/ppt1524 "Expert ppt1524") [TheRaja](/profile/TheRaja "Candidate Master TheRaja") 119 120 There are 2 ways to approach the problem. The combinatorics approach is slightly more involved and might be more difficult to come up with. 121 122 **Hint 1** 123 124 You can ignore the exact positions of the rooks in the initial configurations. Only the number of free rows and columns matter. 125 126 **Hint 2** 127 128 For each move you can make, how does the number of free rows/columns change? 129 130 **Solution** 131 132 Tutorial is loading... 133 134 **Alternate Solution** 135 136 Altenatively, we can iterate on the number of type $1$ moves we play. Let's term this to be $c$. 137 138 There are ${m\choose c}$ ways to choose the $c$ type $1$ moves. Now, we have $m - c$ rows/columns left, and this must be even (type 2 moves cannot exhaust an odd number of rows/columns). 139 140 We can see that each of the $(m - c)!$ permutations of the remaining columns correspond to a set of moves we can play. For example, if we have the columns $(1, 4, 5, 6)$ remaining, a permutation $(4, 5, 6, 1)$ corresponds to playing the moves $(4, 5), (6, 1)$. However, if we simply count the number of permutations, we would also be counting the permutation $(6, 1, 4, 5)$, which corresponds to the same set of moves. 141 142 To remove overcounting, we can just divide $(m - c)!$ by $((m - c)/2)!$ (removing the permutations of the pairs chosen). 143 144 Hence, the answer becomes 145 146 $\sum\limits_{c = 0}^m [(m - c) \bmod 2 = 0] {m \choose c} \frac{(m - c)!}{\left(\frac{m - c}{2}\right)!}$ 147 148 **Rate this problem** 149 150 * Great Problem 151 * Ok Problem 152 * Bad Problem 153 * Didn't solve 154 155 **C++ Code** 156 157 ``` 158 #include <bits/stdc++.h> 159 using namespace std; 160 161 int dp[(int) 3e5+5]; 162 const int MOD = 1e9 + 7; 163 164 int main() { 165 cin.tie(0), cout.tie(0)->sync_with_stdio(0); 166 int t; 167 cin >> t; 168 while (t--) { 169 int n, k; 170 cin >> n >> k; 171 int used = 0; 172 for (int i = 0; i < k; i++) { 173 int r, c; cin >> r >> c; 174 used += 2 - (r == c); 175 } 176 int m = n - used; 177 dp[0] = dp[1] = 1; 178 for (int i = 2; i <= m; i++) 179 dp[i] = (dp[i-1] + 2ll * (i-1) * dp[i-2] % MOD) % MOD; 180 cout << dp[m] << "\n"; 181 } 182 183 } 184 ``` 185 186 # [1957D - A BIT of an Inequality](/contest/1957/problem/D "Codeforces Round 940 (Div. 2) and CodeCraft-23") 187 188 **Idea:** [fangahawk](/profile/fangahawk "Master fangahawk") 189 **Problem Setting:** [fangahawk](/profile/fangahawk "Master fangahawk") [shiven](/profile/shiven "Master shiven") 190 **Editorial**: [JadeReaper](/profile/JadeReaper "Candidate Master JadeReaper") [TheRaja](/profile/TheRaja "Candidate Master TheRaja") 191 192 **Hint 1** 193 194 How can you simplify the given inequality? Use the fact that the XOR of a number with itself is 0. 195 196 **Hint 2** 197 198 The inequality simplifies to $f(x, z) \oplus a_y \gt f(x, z)$. For a given $a_y$ what subarrays (that include $a_y$) would satisfy this? 199 200 **Solution** 201 202 First we may rewrite the inequality as $f(x, z) \oplus a_y \gt f(x, z)$. So, for each index $y$, we want to find the total number of subarrays that contain $y$ but whose $\text{xor}$ decreases when we include the contribution of $a_y$. 203 204 Including $a_y$ in some subarray $[x, z]$ (where $x \le y \le z$) can make the $\text{xor}$ lower only when some set bit of $a_y$ cancels out an existing set bit in $f(x, y - 1) \oplus f(y + 1, z)$. Consider the most signicant set bit in $a_y$. Call this bit $i$. Including $a_y$ would decrease the subarray $\text{xor}$ in subarrays where $f(x, y - 1)$ has $i$ set while $f(y+1, z)$ is unset or vice-versa. 205 206 Now, for the subarrays where both the prefix subarray ($[x \dots y - 1]$) as well as the suffix subarray ($[y + 1 \dots z]$) where either both have bit $i$ set or both have it unset, by including $a_y$, we increment the xor by at least $2^i$. Even if by including $a_y$, every other smaller bit gets unset (because of cancelling out with $a_y$), this sum of these decrements is still less than $2^i$ thereby resulting in an overall positive contribution by including $a_y$. 207 208 **Rate this problem** 209 210 * Great Problem 211 * Ok Problem 212 * Bad Problem 213 * Didn't solve 214 215 **C++ Code** 216 217 ``` 218 #include <bits/stdc++.h> 219 220 using namespace std; 221 222 const int Z = 30; 223 const int MAX_N = 1e5 + 3; 224 int pref[Z][MAX_N][2]; 225 int suff[Z][MAX_N][2]; 226 227 void solve() { 228 int n; 229 cin >> n; 230 vector<int> a(n + 1); 231 for (int i = 1; i <= n; i++) cin >> a[i]; 232 for (int i = 0; i < Z; i++) suff[i][n + 1][0] = suff[i][n + 1][1] = 0; 233 for (int i = 0; i < Z; i++) { 234 for (int j = 1; j <= n; j++) { 235 int t = !!(a[j] & (1 << i)); 236 for (int k = 0; k < 2; k++) pref[i][j][k] = (t == k) + pref[i][j - 1][k ^ t]; 237 } 238 for (int j = n; j >= 1; j--) { 239 int t = !!(a[j] & (1 << i)); 240 for (int k = 0; k < 2; k++) suff[i][j][k] = (t == k) + suff[i][j + 1][k ^ t]; 241 } 242 } 243 long long ans = 0; 244 for (int i = 1; i <= n; i++) { 245 int z = 31 - __builtin_clz(a[i]); 246 ans += 1ll * pref[z][i - 1][1] * (1 + suff[z][i + 1][0]); 247 ans += 1ll * (1 + pref[z][i - 1][0]) * suff[z][i + 1][1]; 248 } 249 cout << ans << "\n"; 250 } 251 252 int main() { 253 int tc; 254 cin >> tc; 255 while (tc--) 256 solve(); 257 return 0; 258 } 259 ``` 260 261 # [1957E - Carousel of Combinations](/contest/1957/problem/E "Codeforces Round 940 (Div. 2) and CodeCraft-23") 262 263 **Idea:** [SilverTongue1729](/profile/SilverTongue1729 "Expert SilverTongue1729") 264 **Problem Setting:** [JadeReaper](/profile/JadeReaper "Candidate Master JadeReaper") 265 **Editorial**: [SilverTongue1729](/profile/SilverTongue1729 "Expert SilverTongue1729") [JadeReaper](/profile/JadeReaper "Candidate Master JadeReaper") [TheRaja](/profile/TheRaja "Candidate Master TheRaja") 266 267 **Hint 1** 268 269 For what values of $j$ is $C(i,j) \bmod j = 0$? 270 271 **Hint 2** 272 273 For all other values of $j$, how can you precompute the result? 274 275 **Hint 3** 276 277 To precompute, switch around the loop order. 278 279 **Solution** 280 281 The number of distinct ways you can select $k$ distinct numbers from the set {$1, 2, \ldots, i$} and arrange them in a line is $i(i-1)\cdots(i-k+1)$, and since arranging in a circle introduces rotational symmetry we have to divide by $k$, so we have $C(i,k) = \frac{i(i-1)\cdots(i-k+1)}{k}$. 282 283 Therefore $C(i,j) \bmod j = \frac{i(i-1)\cdots(i-j+1)}{j} \bmod j$. Now since the numerator is a product of $j$ consecutive integers, atleast one of them will be divisible by $j$. More precisely the exact integer which will be divisible by $j$ will be $ j \times \lfloor \frac{i}{j} \rfloor$. Hence we can simplify the fraction by removing the denominator and replacing the term $ j \times \lfloor \frac{i}{j} \rfloor$ with $\lfloor \frac{i}{j} \rfloor$ in the numerator. Each of the other $j-1$ integers in the numerator, after applying $\bmod j$ would cover all integers from $1$ to $j-1$. Hence 284 285 $C(i,j) \bmod j = \frac{i(i-1)\cdots(i-j+1)}{j} \bmod j = \left( (j-1)! \times \left\lfloor \frac{i}{j} \right\rfloor \right) \bmod j$ 286 287 Here we can notice that all proper factors of $j$ will occur in $(j-1)!$, so based on this we can tell that $C(i,j) \bmod j = 0$ for all composite numbers $j$ except $j=4$. 288 289 We first can handle the case of $j$ being prime. Using Wilson's Theorem, we know that $(j-1)! \equiv -1 \bmod j$ when $j$ is prime. Hence 290 291 $C(i,j) \bmod j = - \left\lfloor \frac{i}{j} \right\rfloor$ 292 293 Now we can reverse the order of loops to sum over all primes, and to calculate the contribution of each prime we can maintain a update array called $delta$. 294 295 To calculate the contribution for a single prime $p$, we know that for all $n$ from $kp$ to $(k + 1)p - 1$ (for all $k$ such that $kp \lt 1e6$) the contribution would be $-k$. So, in the $delta$ array, we increment index $kp$ with $-k \bmod p$ and decrement index $(k + 1)p$ with $-k \mod p$. Now, when we perform a prefix sum on this $delta$ array, we obtain the correct contributions from all primes. 296 297 For the case of $j=4$, we just need to handle it as a prime. 298 299 **Rate this problem** 300 301 * Great Problem 302 * Ok Problem 303 * Bad Problem 304 * Didn't solve 305 306 **C++ Code** 307 308 ``` 309 #include <bits/stdc++.h> 310 311 using namespace std; 312 313 const int MOD = 1e9 + 7; 314 const int MAX_N = 1e6 + 3; 315 bitset<MAX_N> isprime; 316 vector<int> primes; 317 318 vector<int> eratosthenesSieve(int lim) { 319 isprime.set(); 320 isprime[0] = isprime[1] = false; 321 for (int i = 4; i < lim; i += 2) isprime[i] = false; 322 for (int i = 3; i * i < lim; i += 2) 323 if (isprime[i]) 324 for (int j = i * i; j < lim; j += i * 2) isprime[j] = false; 325 vector<int> pr; 326 for (int i = 2; i < lim; i++) 327 if (isprime[i]) pr.push_back(i); 328 return pr; 329 } 330 331 vector<int> ans(MAX_N, 0); 332 333 signed main() { 334 primes = eratosthenesSieve(MAX_N); 335 vector<int> del(MAX_N, 0); 336 // Handle the contribution for all primes 337 for (auto &p: primes) { 338 for (int curr = p; curr < MAX_N; curr += p) { 339 int inc = (p - ((curr / p) % p)) % p; 340 del[curr] = (del[curr] + inc) % MOD; 341 if (curr + p < MAX_N) del[curr + p] = (del[curr + p] - inc + MOD) % MOD; 342 } 343 } 344 //Special case of 4 345 for (int curr = 4; curr < MAX_N; curr += 4) { 346 int inc = (2 * (curr / 4)) % 4; 347 del[curr] = (del[curr] + inc) % MOD; 348 if (curr + 4 < MAX_N) del[curr + 4] = (del[curr + 4] - inc + MOD) % MOD; 349 } 350 int pref = 0; 351 for (int i = 1; i < MAX_N; i++) { 352 pref = (pref + del[i]) % MOD; 353 ans[i] = (ans[i - 1] + pref) % MOD; 354 } 355 int tc; 356 cin >> tc; 357 while (tc--) { 358 int n; 359 cin >> n; 360 cout << ans[n] << "\n"; 361 } 362 } 363 ``` 364 365 # [1957F1 - Frequency Mismatch (Easy Version)](/contest/1957/problem/F1 "Codeforces Round 940 (Div. 2) and CodeCraft-23") 366 367 **Idea:** [fangahawk](/profile/fangahawk "Master fangahawk") 368 **Problem Setting:** [fangahawk](/profile/fangahawk "Master fangahawk") 369 **Editorial:** [akcube](/profile/akcube "Master akcube") 370 371 **Hint 1** 372 373 Let's try answering a different question. Given two multisets of elements how can we check if they differ? Hashing? How to multiset hash efficiently? 374 375 **Hint 2** 376 377 Okay if we can now differentiate two multisets of unequal elements, can we try to answer queries by inserting into these hypothetical multisets and binary search the differing point to identify the element? 378 379 **Solution** 380 381 Let's discuss how to hash a multiset of elements $a$, $b$ and $c$. Here, I will link you to a famous blog by [rng_58](/profile/rng_58 "Legendary Grandmaster rng_58") [Hashing and Probability of Collision](https://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html). Quoting, let's take a random integer $r$ from the interval $[0, MOD)$, and compute the hash $(r+a_1)(r+a_2)\dots(r+a_n)$. This is a polynomial of $r$ of degree $n$, so again from Schwartz-Zippel lemma, the collision probability is at most $\frac{n}{MOD}$. The nice thing about this construction is that we can compute rolling hashes using this idea fast. To make implementation easier, this bound applies for summing the random numbers as well. You can check [this](https://codeforces.com/blog/entry/85900#comment-736594) for proof. 382 383 Let's try to answer a single query $(u_1, v_1, u_2, v_2)$ using binary search. We will solve this query in $nlog^2(n)$ using this idea. To check for some $mid$ in our binary search, we insert the values of all nodes which have values from $1$ to $mid$ into a data structure that we can query the path sum of $u$ to $v$ using. Querying path sum is a fairly standard problem that can be solved using BIT / Segment trees and ETT (Euler-Tour Trick). Now to solve this query, we only need to binary search and find the first vertex where the hashes differ for both the paths. This vertex is guaranteed to have mismatched frequency on the two paths since it's addition into the path multi-sets changed their hashes. So now we can solve a single query in $nlog^2(n)$ time using hashing + BIT / Segtree. 384 385 Now to solve this problem for all $Q$ queries. We can use the idea of parallel binary search here to improve our idea to answering all $Q$ queries efficiently. We can run the binary search for all queries in parallel. For each iteration, sort queries by the current position of their $mid$ values. Then insert values from $1$ to $mid$ of the first query into the BIT and query range sum to determine for that particular query how to adjust $mid$. You can then move the $mid$ pointer to that of the next query and so on. This solution will run in $O(nlog(n) + qlog^2(n))$. 386 387 **Upd:** Thanks to [IceKnight1093](/profile/IceKnight1093 "Master IceKnight1093") for pointing this out. If we just use a single `int` hash with a field size of $\approx 10^9$, it gives us a probability of failure of $\frac{1}{10^9}$ per query. Since we're doing somewhere of the order $10^6$ comparisons per hash representation, this gives a rough $1 - \Big(1 - \frac{1}{10^9}\Big)^{10^6} \approx 10^{-3}$ chance of failure. This is not a great bound theoretically speaking, but from a practical standpoint, it is a loose bound and it is extremely unlikely that this solution can be hacked. That said, if we want better theoretical bounds we can just use a hash with field size $\approx 10^{18}$ or use double hashing. Even if we were to query all ${n \choose 2}$ paths, the chance of collision is $\approx \frac{n^2}{10^{18}} \approx 10^{-8}$, which is more than good enough. TL's were set to allow double hashing solutions to pass comfortably. 388 389 **Rate this problem** 390 391 * Great Problem 392 * Ok Problem 393 * Bad Problem 394 * Didn't solve 395 396 **C++ Code** 397 398 ``` 399 #include <bits/stdc++.h> 400 using namespace std; 401 402 const int MOD = 1e9 + 7; 403 using ll = long long; 404 using dbl = long double; 405 //#define int ll 406 407 using vi = vector<int>; 408 using vvi = vector<vi>; 409 using pii = pair<int, int>; 410 using vii = vector<pii>; 411 using vvii = vector<vii>; 412 using vll = vector<ll>; 413 414 #define ff first 415 #define ss second 416 #define pb push_back 417 #define rep(i, a, b) for(int i = a; i < (b); ++i) 418 #define all(x) begin(x), end(x) 419 #define sz(x) (int)(x).size() 420 #define tc int t; cin>>t; while(t--) 421 #define fightFight cin.tie(0) -> sync_with_stdio(0) 422 423 template<class T> 424 struct RMQ { 425 vector<vector<T>> jmp; 426 RMQ(const vector<T>& V) : jmp(1, V) { 427 for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) { 428 jmp.emplace_back(sz(V) - pw * 2 + 1); 429 rep(j,0,sz(jmp[k])) 430 jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]); 431 } 432 } 433 T query(int a, int b) { 434 assert(a <= b); // tie(a, b) = minimax(a, b) 435 int dep = 31 - __builtin_clz(b-a+1); 436 return min(jmp[dep][a], jmp[dep][b - (1 << dep) + 1]); 437 } 438 }; 439 440 struct LCA { 441 int T = 0; 442 vi st, path, ret; vi en, d; 443 RMQ<int> rmq; 444 LCA(vector<vi>& C) : st(sz(C)), en(sz(C)), d(sz(C)), rmq((dfs(C,0,-1), ret)) {} 445 void dfs(vvi &adj, int v, int par) { 446 st[v] = T++; 447 for (auto to : adj[v]) if (to != par) { 448 path.pb(v), ret.pb(st[v]); 449 d[to] = d[v] + 1; 450 dfs(adj, to, v); 451 } 452 en[v] = T-1; 453 } 454 bool anc(int p, int c) { return st[p] <= st[c] and en[p] >= en[c]; } 455 int lca(int a, int b) { 456 if (a == b) return a; 457 tie(a, b) = minmax(st[a], st[b]); 458 return path[rmq.query(a, b-1)]; 459 } 460 int dist(int a, int b) { return d[a] + d[b] - 2*d[lca(a,b)]; } 461 }; 462 463 template<const int mod> 464 struct mint { 465 constexpr mint(int x = 0) : val((x % mod + mod) % mod) {} 466 mint& operator+=(const mint &b) { val += b.val; val -= mod * (val >= mod); return *this; } 467 mint& operator-=(const mint &b) { val -= b.val; val += mod * (val < 0); return *this; } 468 mint& operator*=(const mint &b) { val = 1ll * val * b.val % mod; return *this; } 469 mint& operator/=(const mint &b) { return *this *= b.inv(); } 470 mint inv() const { 471 int x = 1, y = 0, t; 472 for(int a=val, b=mod; b; swap(a, b), swap(x, y)) 473 t = a/b, a -= t * b, x -= t * y; 474 return mint(x); 475 } 476 mint pow(int b) const { 477 mint a = *this, res(1); 478 for(; b; a *= a, b /= 2) if(b&1) res *= a; 479 return res; 480 } 481 friend mint operator+(const mint &a, const mint &b) {return mint(a) += b;} 482 friend mint operator-(const mint &a, const mint &b) {return mint(a) -= b;} 483 friend mint operator*(const mint &a, const mint &b) {return mint(a) *= b;} 484 friend mint operator/(const mint &a, const mint &b) {return mint(a) /= b;} 485 friend bool operator==(const mint &a, const mint &b) {return a.val == b.val;} 486 friend bool operator!=(const mint &a, const mint &b) {return a.val != b.val;} 487 friend bool operator<(const mint &a, const mint &b) {return a.val < b.val;} 488 friend ostream& operator<<(ostream &os, const mint &a) {return os << a.val;} 489 int val; 490 }; 491 using Mint = mint<MOD>; 492 493 template<typename... Ts, size_t... Is, typename F> 494 void __op(index_sequence<Is...>, tuple<Ts...>& a, const tuple<Ts...>& b, F op) { ((get<Is>(a) = op(get<Is>(a), get<Is>(b))), ...); } 495 #define OVERLOAD(OP, F) \ 496 template<typename... Ts> auto& operator OP##=(tuple<Ts...> &a, const tuple<Ts...> &b) { __op(index_sequence_for<Ts...>(), a, b, F<>{}); return a; } \ 497 template<typename... Ts> auto operator OP(const tuple<Ts...> &a, const tuple<Ts...> &b) { auto c = a; c OP##= b; return c; } 498 OVERLOAD(+, plus) OVERLOAD(-, minus) OVERLOAD(*, multiplies) OVERLOAD(/, divides) 499 500 constexpr int NUM_HASHES = 2; // * 501 constexpr array<int, NUM_HASHES> mods = {127657753, 987654319}; // * 502 template <size_t N = NUM_HASHES> 503 constexpr auto mint_ntuple(const int &v) { 504 return [&]<size_t... Is>(index_sequence<Is...>) { return make_tuple(mint<mods[Is]>(v)...); }(make_index_sequence<N>{}); } 505 506 using HT = decltype(mint_ntuple(0)); 507 508 template<typename T> 509 struct FT { 510 vector<T> s; 511 T def; 512 FT(int n, T def) : s(n, def), def(def) {} 513 void update(int pos, T dif) { // a[pos] += dif 514 for (; pos < sz(s); pos |= pos + 1) s[pos] += dif; 515 } 516 T query(int pos) { // sum of values in [0, pos) 517 pos++; 518 T res = def; 519 for (; pos > 0; pos &= pos - 1) res += s[pos-1]; 520 return res; 521 } 522 }; 523 524 struct Query { 525 int u1, v1, u2, v2, k; 526 int l, r, ans, i; 527 int mid(){ return l + (r-l)/2; } 528 }; 529 530 auto rng = std::mt19937(std::random_device()()); 531 constexpr const int MXN = 1e5+5; 532 533 void solve(){ 534 int n; cin >> n; 535 vi a(n); for(auto &x : a) cin >> x, x--; 536 vvi adj(n); 537 for(int i=0; i < n-1; i++){ 538 int u, v; cin >> u >> v; u--, v--; 539 adj[u].pb(v); adj[v].pb(u); 540 } 541 542 int q; cin >> q; 543 vector<Query> queries(q); 544 int idx=0; 545 for(auto &[u1, v1, u2, v2, k, l, r, ans, i] : queries) cin >> u1 >> v1 >> u2 >> v2 >> k, u1--, v1--, u2--, v2--, l=0, ans=-1, i=idx++; 546 547 LCA lca(adj); 548 vi uni(a); sort(all(uni)); uni.resize(unique(all(uni)) - uni.begin()); 549 vvi cnode(MXN); 550 for(int v=0; v < n; v++) cnode[a[v]].pb(v); 551 vector<HT> hash(MXN); 552 for(auto &c : uni) hash[c] = {rng(), rng()}; 553 554 auto get_ett = [&](vvi &adj){ 555 vi tin(n), tout(n); 556 int timer = 0; 557 function<void(int,int)> dfs = [&](int v, int p){ 558 tin[v] = timer++; 559 for(auto &to : adj[v]) if(to != p) dfs(to, v); 560 tout[v] = timer++; 561 }; 562 dfs(0, -1); 563 return make_pair(tin, tout); 564 }; 565 auto [tin, tout] = get_ett(adj); 566 567 for(auto &q : queries) q.r = sz(uni)-1; 568 569 vi vis(MXN); 570 for(int _=0; _<20; _++){ 571 FT<HT> st(2*n, mint_ntuple(0)); 572 sort(all(queries), [&](Query &a, Query &b) { return a.mid() < b.mid(); }); 573 for(int qq=0, cptr=0; qq < q; qq++) if(queries[qq].l <= queries[qq].r) { 574 auto &[u1, v1, u2, v2, k, l, r, ans, i] = queries[qq]; 575 for(; cptr < sz(uni) and cptr <= queries[qq].mid(); cptr++){ 576 for(auto &v : cnode[uni[cptr]]) 577 st.update(tin[v], hash[uni[cptr]]), st.update(tout[v], mint_ntuple(0)-hash[uni[cptr]]); 578 vis[uni[cptr]] = true; 579 } 580 581 int lca1 = lca.lca(u1, v1), lca2 = lca.lca(u2, v2); 582 HT r1 = st.query(tin[lca1]), r2 = st.query(tin[lca2]); 583 HT hash1 = (st.query(tin[u1]) + st.query(tin[v1]) - (r1 + r1)); 584 if(vis[a[lca1]]) hash1 += hash[a[lca1]]; 585 HT hash2 = (st.query(tin[u2]) + st.query(tin[v2]) - (r2 + r2)); 586 if(vis[a[lca2]]) hash2 += hash[a[lca2]]; 587 588 if(hash1 != hash2){ 589 ans = queries[qq].mid(); 590 r = queries[qq].mid()-1; 591 } 592 else l = queries[qq].mid()+1; 593 } 594 for(auto &c : uni) vis[c] = false; 595 } 596 597 sort(all(queries), [&](Query &a, Query &b) { return a.i < b.i; }); 598 for(auto &[u1, v1, u2, v2, k, l, r, ans, i] : queries){ 599 if(ans == -1) cout << 0 << '\n'; 600 else cout << 1 << ' ' << uni[ans]+1 << '\n'; 601 } 602 } 603 signed main(){ 604 fightFight; 605 solve(); 606 } 607 ``` 608 609 # [1957F2 - Frequency Mismatch (Hard Version)](/contest/1957/problem/F2 "Codeforces Round 940 (Div. 2) and CodeCraft-23") 610 611 **Idea:** [fangahawk](/profile/fangahawk "Master fangahawk") 612 **Problem Setting:** [fangahawk](/profile/fangahawk "Master fangahawk") 613 **Editorial**: [fangahawk](/profile/fangahawk "Master fangahawk") [TheRaja](/profile/TheRaja "Candidate Master TheRaja") 614 615 **Hint 1** 616 617 How would you find the smallest element with different frequencies in two static arrays using a segment tree? Consider hashing. 618 619 **Hint 2** 620 621 Try extending this idea to finding the smallest element with different frequencies in two different paths on a tree. Think persistent data structures. 622 623 **Hint 3** 624 625 Once you solve that, you can be extend it to finding the k smallest elements. 626 627 **Solution** 628 629 Tutorial is loading... 630 631 You can also use an idea similar to the hashing technique used in F1 to hash the segment tree nodes. 632 633 **Rate this problem** 634 635 * Great Problem 636 * Ok Problem 637 * Bad Problem 638 * Didn't solve 639 640 **C++ Code** 641 642 ``` 643 #include <bits/stdc++.h> 644 using namespace std; 645 646 const int MOD1 = 1e9 + 7; 647 const int MOD2 = 998244353; 648 using ll = long long; 649 using dbl = long double; 650 //#define int ll 651 652 using vi = vector<int>; 653 using vvi = vector<vi>; 654 using pii = pair<int, int>; 655 using vii = vector<pii>; 656 using vvii = vector<vii>; 657 using vll = vector<ll>; 658 659 #define ff first 660 #define ss second 661 #define pb push_back 662 #define rep(i, a, b) for(int i = a; i < (b); ++i) 663 #define all(x) begin(x), end(x) 664 #define sz(x) (int)(x).size() 665 #define tc int t; cin>>t; while(t--) 666 #define fightFight cin.tie(0) -> sync_with_stdio(0) 667 template<class T> 668 struct RMQ { 669 vector<vector<T>> jmp; 670 RMQ(const vector<T>& V) : jmp(1, V) { 671 for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) { 672 jmp.emplace_back(sz(V) - pw * 2 + 1); 673 rep(j,0,sz(jmp[k])) 674 jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]); 675 } 676 } 677 T query(int a, int b) { 678 assert(a <= b); // tie(a, b) = minimax(a, b) 679 int dep = 31 - __builtin_clz(b-a+1); 680 return min(jmp[dep][a], jmp[dep][b - (1 << dep) + 1]); 681 } 682 }; 683 struct LCA { 684 int T = 0; 685 vi st, path, ret; vi en, d; 686 RMQ<int> rmq; 687 LCA(vector<vi>& C) : st(sz(C)), en(sz(C)), d(sz(C)), rmq((dfs(C,1,-1), ret)) {} 688 void dfs(vvi &adj, int v, int par) { 689 st[v] = T++; 690 for (auto to : adj[v]) if (to != par) { 691 path.pb(v), ret.pb(st[v]); 692 d[to] = d[v] + 1; 693 dfs(adj, to, v); 694 } 695 en[v] = T-1; 696 } 697 bool anc(int p, int c) { return st[p] <= st[c] and en[p] >= en[c]; } 698 int lca(int a, int b) { 699 if (a == b) return a; 700 tie(a, b) = minmax(st[a], st[b]); 701 return path[rmq.query(a, b-1)]; 702 } 703 int dist(int a, int b) { return d[a] + d[b] - 2*d[lca(a,b)]; } 704 }; 705 template<const int mod> 706 struct mint { 707 constexpr mint(int x = 0) : val((x % mod + mod) % mod) {} 708 mint& operator+=(const mint &b) { val += b.val; val -= mod * (val >= mod); return *this; } 709 mint& operator-=(const mint &b) { val -= b.val; val += mod * (val < 0); return *this; } 710 mint& operator*=(const mint &b) { val = 1ll * val * b.val % mod; return *this; } 711 mint& operator/=(const mint &b) { return *this *= b.inv(); } 712 mint inv() const { 713 int x = 1, y = 0, t; 714 for(int a=val, b=mod; b; swap(a, b), swap(x, y)) 715 t = a/b, a -= t * b, x -= t * y; 716 return mint(x); 717 } 718 mint pow(int b) const { 719 mint a = *this, res(1); 720 for(; b; a *= a, b /= 2) if(b&1) res *= a; 721 return res; 722 } 723 friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; } 724 friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; } 725 friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; } 726 friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; } 727 friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; } 728 friend bool operator!=(const mint &a, const mint &b) { return a.val != b.val; } 729 friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; } 730 friend ostream& operator<<(ostream &os, const mint &a) { return os << a.val; } 731 int val; 732 }; 733 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 734 uniform_int_distribution<ll> rnd(20,10000); 735 using Mint1 = mint<MOD1>; 736 using Mint2 = mint<MOD2>; 737 using Mint = pair<Mint1,Mint2>; 738 const int N = 3e5 + 10, LOGN = 20; 739 int p1, p2; 740 int blen = 0; 741 int L[N * LOGN], R[N * LOGN]; 742 Mint ST[N * LOGN], p_pow[N]; 743 void prec() { 744 p1 = rnd(rng); 745 p2 = p1; 746 while (p2 == p1) p2 = rnd(rng); 747 p_pow[0].ff = 1; 748 p_pow[0].ss = 1; 749 for (int i = 1; i < N; i++) { 750 p_pow[i].ff = p_pow[i - 1].ff * p1; 751 p_pow[i].ss = p_pow[i - 1].ss * p2; 752 } 753 } 754 int update(int pos, int l, int r, int id) { 755 if (pos < l || pos > r) return id; 756 int ID = ++blen, m = (l + r) / 2; 757 if (l == r) return (ST[ID] = {ST[id].ff + 1, ST[id].ss + 1}, ID); 758 L[ID] = update(pos, l, m, L[id]); 759 R[ID] = update(pos, m + 1, r, R[id]); 760 return (ST[ID] = {ST[L[ID]].ff + p_pow[m - l + 1].ff * ST[R[ID]].ff, ST[L[ID]].ss + p_pow[m - l + 1].ss * ST[R[ID]].ss}, ID); 761 } 762 vi vals; 763 using a4 = array<int,4>; 764 void descent(int l, int r, const array<int, 4>& a, const array<int, 4>& b, int k) { 765 if (l == r) return void(vals.push_back(l)); 766 int m = (l + r) / 2; 767 #define stm(X, y) {ST[X[y[0]]].ff + ST[X[y[1]]].ff - ST[X[y[2]]].ff - ST[X[y[3]]].ff, ST[X[y[0]]].ss + ST[X[y[1]]].ss - ST[X[y[2]]].ss - ST[X[y[3]]].ss} 768 #define arr(X, y) (a4{X[y[0]], X[y[1]], X[y[2]], X[y[3]]}) 769 Mint l1 = stm(L, a), l2 = stm(L, b), r1 = stm(R, a), r2 = stm(R, b); 770 if (sz(vals) < k && l1 != l2) descent(l, m, arr(L, a), arr(L, b), k); 771 if (sz(vals) < k && r1 != r2) descent(m + 1, r, arr(R, a), arr(R, b), k); 772 } 773 774 vvi adj; 775 vi a, roots, par; 776 void dfs(int x, int p) { 777 par[x] = p; 778 roots[x] = update(a[x], 0, N, roots[par[x]]); 779 for (auto& s : adj[x]) if (s != p) { 780 dfs(s, x); 781 } 782 } 783 void solve(){ 784 int n; cin >> n; 785 adj = vvi(n + 1); 786 a = roots = par = vi(n + 1); 787 for (int i = 1; i <= n; i++) cin >> a[i]; 788 for (int i = 0; i < n - 1; i++) { 789 int a, b; cin >> a >> b; 790 adj[a].pb(b), adj[b].pb(a); 791 } 792 dfs(1, 0); 793 LCA lca(adj); 794 int q; cin >> q; 795 while (q--) { 796 vals.clear(); 797 int u1, v1, u2, v2, k; cin >> u1 >> v1 >> u2 >> v2 >> k; 798 int l1 = lca.lca(u1, v1), l2 = lca.lca(u2, v2); 799 a4 a{roots[u1], roots[v1], roots[l1], roots[par[l1]]}; 800 a4 b{roots[u2], roots[v2], roots[l2], roots[par[l2]]}; 801 descent(0, N, a, b, k); 802 cout << sz(vals) << " "; 803 for (auto& s : vals) cout << s << " "; 804 cout << "\n"; 805 } 806 } 807 signed main(){ 808 fightFight; 809 prec(); 810 solve(); 811 } 812 ```