1043.md (33285B)
1 Source: https://codeforces.com/blog/entry/62797 2 3 #### [1043A — Elections](//codeforces.com/contest/1043/problem/A) 4 5 **Tutorial** 6 7 We can observe that result cannot exceed 201 — Awruk gets at least 101 votes from one person and Elodreip cannot get more than 100 votes from one person. So we can iterate over every possible integer from 1 to 201 and check if Awruk wins with *k* set to this integer. We have to remember that *k* — *a**i* is always at least 0, so we have to check this condition too. Complexity *O*(*n* * *M*), where *M* denotes maximum possible value of *a**i*. Try to solve it in *O*(*n*). 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int n; 17 int mx = 0, sum = 0; 18 19 int main(){ 20 scanf("%d", &n); 21 for(int i = 1; i <= n; ++i){ 22 int a; scanf("%d", &a); 23 mx = max(mx, a); 24 sum += a; 25 } 26 27 sum *= 2; 28 sum += n; 29 sum /= n; 30 31 printf("%d", max(sum, mx)); 32 return 0; 33 } 34 ``` 35 36 Author: [Anadi](/profile/Anadi "Grandmaster Anadi") 37 38 #### [1043B — Lost Array](//codeforces.com/contest/1043/problem/B) 39 40 **Tutorial** 41 42 First, let's observe that we can replace array *a**i* with array *b**i* = *a**i* - *a**i* - 1, because all we care about are differences between neighboring elements. Now, we can see that our lost array can have length *d* if and only if for every *j* such that *j* + *d* ≤ *n*, *b**j* = *b**j* + *d*. So we can iterate over every possible *d* from 1 to *n* and check if it is correct in *O*(*n*). Complexity of whole algorithm is *O*(*n*2). 43 44 **Solution** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 const int N = 1007; 52 53 int n; 54 int in[N]; 55 56 bool ok(int d){ 57 for(int i = 0; i + d < n; ++i) 58 if(in[i + 1] - in[i] != in[i + d + 1] - in[i + d]) 59 return false; 60 return true; 61 } 62 63 int main(){ 64 scanf("%d", &n); 65 for(int i = 1; i <= n; ++i) 66 scanf("%d", &in[i]); 67 68 vector <int> res; 69 for(int i = 1; i <= n; ++i) 70 if(ok(i)) 71 res.push_back(i); 72 73 printf("%d\n", res.size()); 74 for(int v: res) 75 printf("%d ", v); 76 return 0; 77 } 78 ``` 79 80 Author: [Anadi](/profile/Anadi "Grandmaster Anadi") 81 82 #### [1043C — Smallest Word](//codeforces.com/contest/1043/problem/C) 83 84 **Tutorial** 85 86 Basically in problem we are given a word in which for every *i* we can reverse prefix of first *i* elements and we want to get the smallest lexicographically word. We will show that we can always achieve word in form *a**j**b**n* - *j*. 87 88 Let's say that we solved our problem for prefix of length *i* and for this prefix we have word *a**j**b**i* - *j* (at the beginning it's just empty word). If our next letter is *b* then we do nothing, because we will get word *a**j**b**i* - *j* + 1 which is still the smallest lexicographically word. Otherwise we want to reverse prefix of length *i*, add letter *a* and reverse prefix of length *i* + 1, so we get a word *a**j* + 1*b**i* - *j*, which is still fine for us. 89 90 There is still a problem — what if we have already reversed prefix *i* and we just said that we will reverse it second time. But instead of reversing it second time, we can deny it's first reverse. 91 92 Final complexity is *O*(*n*). 93 94 **Solution** 95 96 ``` 97 #include <bits/stdc++.h> 98 99 using namespace std; 100 101 const int N = 1007; 102 103 string s; 104 bool write[N]; 105 106 int main(){ 107 cin >> s; 108 for(int i = 1; i < s.size(); ++i) 109 if(s[i] == 'a'){ 110 write[i - 1] ^= 1; 111 write[i] = 1; 112 } 113 114 for(int i = 0; i < s.size(); ++i) 115 printf("%d%c", write[i], i + 1 == (int)s.size() ? '\n' : ' '); 116 return 0; 117 } 118 ``` 119 120 Author: [Anadi](/profile/Anadi "Grandmaster Anadi") 121 122 #### [1043D — Mysterious Crime](//codeforces.com/contest/1043/problem/D) 123 124 **Tutorial** 125 126 Deleting prefix and suffix is nothing more than taking a subarray. If subarray is common for all permutations then it has to appear in first permutation. We renumber all permutations such that first permutation is 1, 2, ..., *n* - 1, *n*. 127 128 Now for every *i* in every permutation we count how long is subarray starting at *i* which looks like *i*, *i* + 1, ..., *i* + *k*. It can be easily done in *O*(*n*) for one permutation with two pointers technique. 129 130 Now for every element *i* we compute *reach*[*i*] equal the longest subarray starting in *i* which looks like *i*, *i* + 1, ..., *i* + *k* and it apears in all subarrays. It is just minimum over previously calculated values for all permutations. 131 132 Now we can see that our result is . Final complexity *O*(*nm*). 133 134 **Solution** 135 136 ``` 137 #include <bits/stdc++.h> 138 139 using namespace std; 140 141 typedef long long int LL; 142 143 const int N = 1e5 + 7; 144 145 int n, m; 146 int mn[N]; 147 int ren[N]; 148 int perm[15][N]; 149 150 int main(){ 151 scanf("%d %d", &n, &m); 152 for(int i = 1; i <= m; ++i) 153 for(int j = 1; j <= n; ++j) 154 scanf("%d", &perm[i][j]); 155 156 for(int i = 1; i <= n; ++i) 157 ren[perm[1][i]] = i; 158 159 for(int i = 1; i <= m; ++i) 160 for(int j = 1; j <= n; ++j) 161 perm[i][j] = ren[perm[i][j]]; 162 163 for(int i = 1; i <= n; ++i) 164 mn[i] = n; 165 166 for(int i = 1; i <= m; ++i){ 167 int cur = 1; 168 for(int j = 1; j <= n; ++j){ 169 if(cur < j) 170 ++cur; 171 172 while(cur < n && perm[i][cur + 1] == perm[i][cur] + 1) 173 ++cur; 174 mn[perm[i][j]] = min(mn[perm[i][j]], perm[i][cur]); 175 } 176 } 177 178 LL res = 0; 179 int now = 1; 180 while(now <= n){ 181 int cur = mn[now] - now + 1; 182 res += 1LL * (cur + 1) * cur / 2LL; 183 now = mn[now] + 1; 184 } 185 186 printf("%lld\n", res); 187 return 0; 188 } 189 ``` 190 191 Author: [Anadi](/profile/Anadi "Grandmaster Anadi") 192 193 #### [1043E — Train Hard, Win Easy](//codeforces.com/contest/1043/problem/E) 194 195 **Tutorial** 196 197 Let's compute result if there are no edges, we can add them later. If there are no edges then result for pair (*i*, *j*) is min(*x**i* + *y**j*, *x**j* + *y**i*). First let's fix *i* for which we want to compute result. Then calculate result with all pairs *j* such that *x**i* + *y**j* ≤ *x**j* + *y**i*. After some transformations we get that *x**i* - *y**i* ≤ *x**j* - *y**j*. Similarly we have that *y**i* + *x**j* < *x**i* + *y**j* if *x**i* - *y**i* > *y**j* - *x**j*. 198 199 So let's sort over differences of *x**i* - *y**i* and compute prefix sums of *x**i* and suffix sums of *y**i*. Now we can compute for every *i* result in *O*(1). Then we can iterate over every edge (*u*, *v*) and subtract min(*x**u* + *y**v*, *x**v* + *y**u*) from result of *u* and *v*. 200 201 Complexity *O*(*nlogn*). 202 203 **Solution** 204 205 ``` 206 #include <bits/stdc++.h> 207 208 using namespace std; 209 210 typedef long long int LL; 211 212 #define st first 213 #define nd second 214 #define PII pair <int, int> 215 216 const int N = 3e5 + 7; 217 218 int n, m; 219 PII diff[N]; 220 int place[N]; 221 vector <int> G[N]; 222 223 LL ans[N]; 224 int x[N], y[N]; 225 LL pref[N], suf[N]; 226 227 int main(){ 228 scanf("%d %d", &n, &m); 229 for(int i = 1; i <= n; ++i){ 230 scanf("%d %d", &x[i], &y[i]); 231 diff[i] = {y[i] - x[i], i}; 232 } 233 234 for(int i = 1; i <= m; ++i){ 235 int u, v; 236 scanf("%d %d", &u, &v); 237 238 G[u].push_back(v); 239 G[v].push_back(u); 240 } 241 242 sort(diff + 1, diff + n + 1); 243 for(int i = 1; i <= n; ++i) 244 place[diff[i].nd] = i; 245 246 for(int i = 1; i <= n; ++i) 247 pref[i] = pref[i - 1] + y[diff[i].nd]; 248 249 for(int i = n; i >= 1; --i) 250 suf[i] = suf[i + 1] + x[diff[i].nd]; 251 252 for(int i = 1; i <= n; ++i){ 253 int u = diff[i].nd; 254 LL res = pref[i - 1] + suf[i + 1] + 1LL * (i - 1) * x[u] + 1LL * (n - i) * y[u]; 255 256 for(int v: G[u]) 257 res -= min(x[u] + y[v], x[v] + y[u]); 258 ans[u] = res; 259 } 260 261 for(int i = 1; i <= n; ++i) 262 printf("%lld ", ans[i]); 263 return 0; 264 } 265 ``` 266 267 Author: [Rzepa](/profile/Rzepa "International Master Rzepa") 268 269 #### [1043F — Make It One](//codeforces.com/contest/1043/problem/F) 270 271 **Tutorial** 272 273 First let's observe that if there exists valid subset then it's size is at most 7 (because product of 7 smallest primes is bigger then 3 * 105). Let's define *dp*[*i*][*j*] — number of ways to pick *i* different elements such that their gcd is equal to *j*. We can use inclusion--exclusion principle to calculate it. Then *dp*[*i*][*j*] =  — , where *cnt**j* denotes number of *a**i* such that *j* | *a**i*. Because for *k* * *j* > 3 * 105, *dp*[*i*][*k* * *j*] = 0 we have to check only *k* * *j* ≤ 3 * 105. 274 275 Our answer is the smallest *i* such that *dp*[*i*][1] is non-zero. Since *dp*[*i*][*j*] can be quite big we should compute it modulo some big prime. 276 277 Final complexity is *O*(*logM* * (*n* + *M*)), where M is equal to maximum of *a**i*. 278 279 **Solution 1** 280 281 ``` 282 #include <bits/stdc++.h> 283 284 using namespace std; 285 286 const int N = 3e5 + 7; 287 const int MX = 1e9 + 7; 288 289 int n; 290 int cnt[N]; 291 int sil[N]; 292 int odw[N]; 293 int dp[20][N]; 294 295 int fast(int a, int b){ 296 int ret = 1; 297 while(b){ 298 if(b & 1) 299 ret = (1LL * ret * a)%MX; 300 301 b >>= 1; 302 a = (1LL * a * a)%MX; 303 } 304 305 return ret; 306 } 307 308 int newton(int a, int b){ 309 if(b < 0 || a < b) return 0; 310 return (((1LL * sil[a] * odw[b])%MX) * odw[a - b])%MX; 311 } 312 313 void sub(int &a, int b){ 314 a -= b; 315 if(a < 0) 316 a += MX; 317 } 318 319 int main(){ 320 sil[0] = 1; 321 for(int i = 1; i < N; ++i) 322 sil[i] = (1LL * sil[i - 1] * i)%MX; 323 324 odw[N - 1] = fast(sil[N - 1], MX - 2); 325 for(int i = N - 1; i >= 1; --i) 326 odw[i - 1] = (1LL * odw[i] * i)%MX; 327 328 scanf("%d", &n); 329 for(int i = 1; i <= n; ++i){ 330 int a; 331 scanf("%d", &a); 332 cnt[a]++; 333 } 334 335 for(int i = 1; i < N; ++i) 336 for(int j = i + i; j < N; j += i) 337 cnt[i] += cnt[j]; 338 339 for(int i = 1; i < 20; ++i){ 340 for(int j = N - 1; j >= 1; --j){ 341 dp[i][j] = newton(cnt[j], i); 342 for(int k = j + j; k < N; k += j) 343 sub(dp[i][j], dp[i][k]); 344 } 345 346 if(dp[i][1] > 0){ 347 printf("%d\n", i); 348 return 0; 349 } 350 } 351 352 puts("-1"); 353 return 0; 354 } 355 ``` 356 357 **Solution 2** 358 359 ``` 360 #include <bits/stdc++.h> 361 362 using namespace std; 363 364 const int N = 3e5 + 7; 365 366 int n; 367 int cnt[N]; 368 int roz[N]; 369 int dist[N]; 370 queue <int> Q; 371 vector <int> dv[N]; 372 373 int base(int a){ 374 int ret = 1; 375 while(a > 1){ 376 if(ret%roz[a] != 0) 377 ret *= roz[a]; 378 a /= roz[a]; 379 } 380 381 return ret; 382 } 383 384 void getEdges(int u, int d){ 385 vector <int> cur; 386 vector <int> val; 387 388 while(u > 1){ 389 cur.push_back(roz[u]); 390 u /= roz[u]; 391 } 392 393 for(int v: cur) 394 u *= v; 395 396 int T = 1 << (int)cur.size(); 397 val.resize(T); 398 399 for(int i = 0; i < T; ++i){ 400 val[i] = u; 401 for(int j = 0; j < (int)cur.size(); ++j) 402 if(i & (1 << j)) 403 val[i] /= cur[j]; 404 } 405 406 for(int i = 0; i < T; ++i){ 407 int s = 0; 408 for(int j = i; true; j = (j - 1) & i){ 409 if(__builtin_popcount(i ^ j) & 1) 410 s -= cnt[val[j]]; 411 else 412 s += cnt[val[j]]; 413 414 if(j == 0) 415 break; 416 } 417 418 assert(s >= 0); 419 if(s && dist[val[i]] == -1){ 420 dist[val[i]] = d; 421 Q.push(val[i]); 422 } 423 } 424 } 425 426 int main(){ 427 scanf("%d", &n); 428 for(int i = 2; i < N; ++i){ 429 if(roz[i] != 0) 430 continue; 431 432 for(int j = i; j < N; j += i) 433 roz[j] = i; 434 } 435 436 for(int i = 1; i < N; ++i) 437 for(int j = i; j < N; j += i) 438 dv[j].push_back(i); 439 440 for(int i = 1; i < N; ++i) 441 dist[i] = -1; 442 443 for(int i = 1; i <= n; ++i){ 444 int a; 445 scanf("%d", &a); 446 a = base(a); 447 448 if(dist[a] != -1) 449 continue; 450 451 dist[a] = 1; 452 Q.push(a); 453 454 for(int v: dv[a]) 455 cnt[v]++; 456 } 457 458 while(!Q.empty()){ 459 int u = Q.front(); 460 Q.pop(); 461 getEdges(u, dist[u] + 1); 462 } 463 464 printf("%d\n", dist[1]); 465 return 0; 466 } 467 ``` 468 469 Author: [Anadi](/profile/Anadi "Grandmaster Anadi") 470 471 #### [1043G — Speckled Band](//codeforces.com/contest/1043/problem/G) 472 473 **Tutorial** 474 475 Let's solve the problem for some string *s* for any time. 476 477 Let's say, that partition of string *s* into *k* strings *s*1*s*2... *s**i*1, *s**i*1 + 1... *s**i*2, ..., {*s**i**k* - 1 + 1}... *s**i**k* is good if at least one pair of this strings are equal. We want to find a minimal possible number of different strings in all good partitions. 478 479 It's easy to see, that the answer is - 1 if and only if all symbols in *s* are different. And if we have two equal symbols *s**i* = *s**j* (*i* < *j*) we can cut a string into strings *s*1... *s**i* - 1, *s**i*, *s**i* + 1... *s**j* - 1, *s**j*, *s**j* + 1... *s**n* and it is a good partition. In this partition there is at most 4 different strings. 480 481 So the answer can be - 1, 1, 2, 3, 4. 482 483 The answer is - 1 if all symbols in *s* are different (case 0). 484 485 The answer is 1 if the string *s* = *aaa*... *a*, for some string *a* (case 1). 486 487 The answer is 2 if the string *s* is *aab*, *aba* or *baa* for some strings *a* and *b* (case 2). 488 489 The answer is 3 if the string *s* is *baac*, *bcaa* or *aabc* for some strings *a*, *b*, *c*. In two last cases it's easy to see, that |*a*| = 1 (case 3). 490 491 To solve our problem let's build suffix array with lcp for string *s*. And let's find *lt**i*~--- minimal possible number *r*, such that *s**is**i* + 1... *s**r* is a tandem (the string, that can be presented as *aa* for some string *a*) and *rt**i*~--- maximal possible number *l* such that *s**ls**l* + 1... *s**i* is a tandem. This numbers can be found using Main and Lorentz algorithm for finding tandem repetitions in the string. 492 493 Now we can solve query for segment [*l*, *r*]: \begin{itemize} \item Case 0: if *r* - *l* ≥ 26, there exists equal symbols, otherwise we can check it by *O*(*r* - *l*); \item Case 1: to check that *s*[*l*... *r*] = *aa*... *a* we can see that |*a*| is a divisor of (*r* - *l* + 1) and (*r* - *l* + 1) / |*a*| is a prime number (if we take a longest possible string *a*). So we should check only *O*(*log*(*n*)) lenghts of string *a*; \item Case 2: *s* = *aab*  *lt**l* ≤ *r*, *s* = *baa*  *rt**r* ≥ *l*. In the last case we should check, that *s*[*l*... *r*] has a border. It's the most interesting part of the problem, let's solve it in the end; \item Case 3: *s* = *abac*  *s**l* exists on *s**l* + 1... *s**r* (can be done using prefix sums), *s* = *baca*  *s**r* exists on *s**l*... *s**r* - 1 (can be done using prefix sums). To check *s* = *baac* we can check, that *lt**i* ≤ *r* for some *l* ≤ *i* ≤ *r*, that can be done using minimum on segment in the array *lt*. \end{itemize} 494 495 Now we should the hardest part of this problem~--- we have some segments [*l*, *r*]. For all of them, we should check that the border of *s*[*l*... *r*] exists. Here I know two methods, that uses only suffix array. Easiest of them: 496 497 We have segment [*l*, *r*]. Let's check for all lengths , that *s*[*l*... (*l* + *b* - 1)] = *s*[(*r* - *b* + 1)... *r*]. If we don't find border, if it exists, it's length . Let's define *i*~--- maximal index *i* such that *lcp*(*l*, *i*) ≥ *r* - *i* + 1, and string *s*[*i*... *r*] is a border of *s*[*l*... *r*]. So . But it's easy to see, that the distance between *l* and *i* in suffix array  , so we need to check only  variants of *i*. 498 499 Another method can check that border exists for all segments [*l*, *r*] using offline algorithm by *O*(*q*·*log*(*n*)2) time. 500 501 So the total complexity will be  or *O*((*n* + *q*)·*log*(*n*)2). 502 503 **Solution 1** 504 505 ``` 506 #include <bits/stdc++.h> 507 508 using namespace std; 509 510 const int BIG = 1e9 + 239; 511 const int M = 2 * 1e5 + 239; 512 const int L = 19; 513 const int A = 30; 514 const int T = (1 << 19); 515 const int two = 2; 516 517 int flm[two][M]; 518 519 inline void z_function(string &s, int c) 520 { 521 int n = s.length(); 522 flm[c][0] = 0; 523 int l = 0; 524 int r = 0; 525 for (int i = 1; i < n; i++) 526 { 527 flm[c][i] = min(flm[c][i - l], r - i); 528 if (flm[c][i] < 0) flm[c][i] = 0; 529 while (i + flm[c][i] < n && s[flm[c][i]] == s[i + flm[c][i]]) flm[c][i]++; 530 if (i + flm[c][i] > r) 531 { 532 l = i; 533 r = i + flm[c][i]; 534 } 535 } 536 } 537 538 int a[M], lcp[M], pos[M]; 539 540 inline void suffix_array(string s) 541 { 542 s += (char)(31); 543 int n = s.length(); 544 vector<pair<char, int> > v; 545 for (int i = 0; i < n; i++) 546 v.push_back(make_pair(s[i], i)); 547 sort(v.begin(), v.end()); 548 vector<pair<int, int> > num; 549 int last = 0; 550 for (int i = 0; i < n - 1; i++) 551 { 552 num.push_back(make_pair(last, v[i].second)); 553 if (v[i].first != v[i + 1].first) last++; 554 } 555 num.push_back(make_pair(last, v.back().second)); 556 vector<int> u(n); 557 for (int i = 0; i < n; i++) u[num[i].second] = num[i].first; 558 int d = 1; 559 vector<pair<pair<int, int>, int> > t; 560 vector<vector<pair<int, int> > > h; 561 while (d < n) 562 { 563 t.clear(); 564 h.clear(); 565 h.resize(n); 566 for (int i = 0; i < n; i++) 567 { 568 int l = num[i].second - d; 569 if (l < 0) l += n; 570 h[u[l]].push_back(make_pair(num[i].first, l)); 571 } 572 for (int i = 0; i < n; i++) 573 for (pair<int, int> r : h[i]) 574 t.push_back(make_pair(make_pair(i, r.first), r.second)); 575 last = 0; 576 num.clear(); 577 for (int i = 0; i < n - 1; i++) 578 { 579 num.push_back(make_pair(last, t[i].second)); 580 if (t[i].first != t[i + 1].first) last++; 581 } 582 num.push_back(make_pair(last, t.back().second)); 583 for (int i = 0; i < n; i++) u[num[i].second] = num[i].first; 584 d <<= 1; 585 } 586 for (int i = 1; i < n; i++) a[i - 1] = num[i].second; 587 } 588 589 string s; 590 591 inline void kasai() 592 { 593 int n = s.size(); 594 suffix_array(s); 595 for (int i = 0; i < n; i++) 596 pos[a[i]] = i; 597 int k = 0; 598 for (int i = 0; i < n; i++) 599 { 600 if (pos[i] == n - 1) continue; 601 while (s[i + k] == s[a[pos[i] + 1] + k] && a[pos[i] + 1] + k < n && i + k < n) k++; 602 lcp[pos[i]] = k; 603 k = max(0, k - 1); 604 } 605 } 606 607 int n, lw[M], rw[M]; 608 string prr, rvl; 609 vector<int> open_l[M], close_l[M]; 610 vector<int> open_r[M], close_r[M]; 611 multiset<int> nw; 612 613 inline void func(int l, int r) 614 { 615 if (r - l == 1) return; 616 int mid = (l + r) >> 1; 617 func(l, mid); 618 func(mid, r); 619 rvl = ""; 620 for (int i = mid - 1; i >= l; i--) rvl += s[i]; 621 z_function(rvl, 0); 622 prr = ""; 623 for (int i = mid; i < r; i++) prr += s[i]; 624 prr += '#'; 625 for (int i = l; i < mid; i++) prr += s[i]; 626 z_function(prr, 1); 627 for (int c = l; c < mid; c++) 628 { 629 int k1 = 0; 630 if (c > l) k1 = flm[0][mid - c]; 631 int k2 = flm[1][r - mid + 1 + c - l]; 632 int len = mid - c; 633 int lg = max(len - k2, 0); 634 int rg = min(len - 1, k1); 635 if (rg >= lg) 636 { 637 open_l[c - rg].push_back((2 * len)); 638 close_l[c - lg].push_back((2 * len)); 639 open_r[c - rg + 2 * len - 1].push_back((2 * len)); 640 close_r[c - lg + 2 * len - 1].push_back((2 * len)); 641 } 642 } 643 rvl = ""; 644 for (int i = mid; i < r; i++) rvl += s[i]; 645 z_function(rvl, 0); 646 prr = ""; 647 for (int i = mid - 1; i >= l; i--) prr += s[i]; 648 prr += '#'; 649 for (int i = r - 1; i >= mid; i--) prr += s[i]; 650 z_function(prr, 1); 651 for (int c = mid; c < r; c++) 652 { 653 int k1 = 0; 654 if (c != r - 1) k1 = flm[0][c + 1 - mid]; 655 int k2 = flm[1][r - c + mid - l]; 656 int len = c - mid + 1; 657 int lg = max(len - k2, 0); 658 int rg = min(len - 1, k1); 659 if (rg >= lg) 660 { 661 open_l[c + lg - 2 * len + 1].push_back((2 * len)); 662 close_l[c + rg - 2 * len + 1].push_back((2 * len)); 663 open_r[c + lg].push_back((2 * len)); 664 close_r[c + rg].push_back((2 * len)); 665 } 666 } 667 for (int i = l; i < r; i++) 668 { 669 for (int len : open_l[i]) nw.insert(len); 670 if (!nw.empty()) lw[i] = min(lw[i], *nw.begin()); 671 for (int len : close_l[i]) nw.erase(nw.lower_bound(len)); 672 open_l[i].clear(); 673 close_l[i].clear(); 674 } 675 for (int i = l; i < r; i++) 676 { 677 for (int len : open_r[i]) nw.insert(len); 678 if (!nw.empty()) rw[i] = min(rw[i], *nw.begin()); 679 for (int len : close_r[i]) nw.erase(nw.lower_bound(len)); 680 open_r[i].clear(); 681 close_r[i].clear(); 682 } 683 } 684 685 int mn[L][M], st2[M], lc[L][M], kol[A][M]; 686 687 inline int getmin(int l, int r) 688 { 689 int u = st2[r - l + 1]; 690 return min(mn[u][l], mn[u][r - (1 << u) + 1]); 691 } 692 693 inline int gett(int l, int r) 694 { 695 if (l == r) return (n - l); 696 l = pos[l]; 697 r = pos[r]; 698 if (l > r) swap(l, r); 699 r--; 700 int u = st2[r - l + 1]; 701 return min(lc[u][l], lc[u][r - (1 << u) + 1]); 702 } 703 704 int q, la[M], ra[M], has[M], mnp[M]; 705 706 inline void init() 707 { 708 for (int i = 0; i < n; i++) mn[0][i] = lw[i]; 709 for (int i = 0; i < n - 1; i++) lc[0][i] = lcp[i]; 710 for (int i = 1; i < L; i++) 711 for (int j = 0; j < n; j++) 712 { 713 int r = (j + (1 << (i - 1))); 714 if (r >= n) 715 { 716 mn[i][j] = mn[i - 1][j]; 717 continue; 718 } 719 mn[i][j] = min(mn[i - 1][j], mn[i - 1][r]); 720 } 721 for (int i = 1; i < L; i++) 722 for (int j = 0; j < n - 1; j++) 723 { 724 int r = (j + (1 << (i - 1))); 725 if (r >= n - 1) 726 { 727 lc[i][j] = lc[i - 1][j]; 728 continue; 729 } 730 lc[i][j] = min(lc[i - 1][j], lc[i - 1][r]); 731 } 732 st2[1] = 0; 733 for (int i = 2; i <= n; i++) 734 { 735 st2[i] = st2[i - 1]; 736 if ((1 << (st2[i] + 1)) <= i) st2[i]++; 737 } 738 } 739 740 int in[L][M], gl[T]; 741 742 inline void build(int i, int l, int r) 743 { 744 if (i == 0) gl[i] = 0; 745 else gl[i] = gl[(i - 1) / 2] + 1; 746 if (r - l == 1) 747 { 748 in[gl[i]][l] = a[l]; 749 return; 750 } 751 int mid = (l + r) >> 1; 752 build(2 * i + 1, l, mid); 753 build(2 * i + 2, mid, r); 754 merge(in[gl[i] + 1] + l, in[gl[i] + 1] + mid, in[gl[i] + 1] + mid, in[gl[i] + 1] + r, in[gl[i]] + l); 755 } 756 757 inline bool is_on(int i, int l, int r, int ql, int qr, int xl, int xr) 758 { 759 if (r <= ql || qr <= l) return false; 760 if (ql <= l && r <= qr) 761 { 762 int it = upper_bound(in[gl[i]] + l, in[gl[i]] + r, xl) - in[gl[i]] - l; 763 if (it == r - l) return false; 764 return (in[gl[i]][it + l] <= xr); 765 } 766 int mid = (l + r) >> 1; 767 if (is_on(2 * i + 1, l, mid, ql, qr, xl, xr)) return true; 768 return is_on(2 * i + 2, mid, r, ql, qr, xl, xr); 769 } 770 771 inline bool check_all(int l, int r) 772 { 773 int len = (r - l + 1); 774 int pl = pos[l]; 775 int lf = pl; 776 int rf = n; 777 while (rf - lf > 1) 778 { 779 int h = (lf + rf) / 2; 780 if (gett(a[h], l) >= len) lf = h; 781 else rf = h; 782 } 783 int rg = lf + 1; 784 lf = -1; 785 rf = pl; 786 while (rf - lf > 1) 787 { 788 int h = (lf + rf) / 2; 789 if (gett(a[h], l) >= len) rf = h; 790 else lf = h; 791 } 792 int lg = rf; 793 return is_on(0, 0, n, lg, rg, l, r); 794 } 795 796 int par[M]; 797 set<int> cmp[M]; 798 set<pair<int, int> > sc[M]; 799 vector<int> ok[M]; 800 vector<pair<int, int> > mg[M]; 801 802 inline void border_check() 803 { 804 for (int i = 0; i < q; i++) has[i] = false; 805 for (int i = 0; i < q; i++) ok[ra[i] - la[i]].push_back(i); 806 for (int i = 0; i < n - 1; i++) mg[lcp[i]].push_back(make_pair(a[i], a[i + 1])); 807 for (int i = 0; i < n; i++) 808 { 809 par[i] = i; 810 cmp[i].insert(i); 811 } 812 for (int c = n; c >= 1; c--) 813 { 814 for (int i : ok[c - 1]) 815 sc[par[la[i]]].insert(make_pair(ra[i], i)); 816 for (pair<int, int> t : mg[c]) 817 { 818 int l = par[t.first]; 819 int r = par[t.second]; 820 if (cmp[l].size() > cmp[r].size()) swap(l, r); 821 for (int x : cmp[l]) 822 while (true) 823 { 824 auto it = sc[r].lower_bound(make_pair(x, 0)); 825 if (it == sc[r].end() || it->first > x + c - 1) break; 826 has[it->second] = true; 827 sc[r].erase(it); 828 } 829 for (pair<int, int> u : sc[l]) 830 { 831 int id = u.second; 832 auto uk = cmp[r].lower_bound(ra[id] - c + 1); 833 if (uk != cmp[r].end() && (*uk) <= ra[id]) 834 has[id] = true; 835 else 836 sc[r].insert(u); 837 } 838 for (int x : cmp[l]) 839 { 840 par[x] = r; 841 cmp[r].insert(x); 842 } 843 } 844 } 845 for (int i = 0; i < q; i++) 846 if (!has[i] && check_all(la[i], ra[i])) 847 { 848 has[i] = true; 849 continue; 850 } 851 } 852 853 inline bool checkno(int l, int r) 854 { 855 if (r - l + 1 > 26) return false; 856 vector<int> kol(26, 0); 857 for (int x = l; x <= r; x++) 858 { 859 if (kol[s[x] - 'a'] > 0) return false; 860 kol[s[x] - 'a']++; 861 } 862 return true; 863 } 864 865 inline bool try_kol(int l, int r, int p) 866 { 867 int len = (r - l + 1) / p; 868 return (gett(l, l + len) >= (r - l + 1 - len)); 869 } 870 871 inline bool ison(int l, int r, char x) 872 { 873 return (kol[x - 'a'][r + 1] > kol[x - 'a'][l]); 874 } 875 876 inline int query(int l, int r, int id) 877 { 878 if (checkno(l, r)) return -1; 879 int len = (r - l + 1); 880 while (len > 1) 881 { 882 int p = mnp[len]; 883 if (try_kol(l, r, p)) return 1; 884 while ((len % p) == 0) len /= p; 885 } 886 if (lw[l] <= r) return 2; 887 if (rw[r] >= l) return 2; 888 if (has[id]) return 2; 889 if (ison(l + 1, r, s[l])) return 3; 890 if (ison(l, r - 1, s[r])) return 3; 891 if (getmin(l, r) <= r) return 3; 892 return 4; 893 } 894 895 int main() 896 { 897 cin.sync_with_stdio(0); 898 cin >> n >> s; 899 memset(mnp, -1, sizeof(mnp)); 900 for (int i = 2; i <= n; i++) 901 if (mnp[i] == -1) 902 for (int j = i; j <= n; j += i) 903 if (mnp[j] == -1) 904 mnp[j] = i; 905 memset(kol[0], 0, sizeof(kol[0])); 906 for (int i = 0; i < n; i++) 907 { 908 for (int x = 0; x < 26; x++) kol[x][i + 1] = kol[x][i]; 909 kol[s[i] - 'a'][i + 1]++; 910 } 911 for (int i = 0; i < n; i++) 912 { 913 lw[i] = n + 1; 914 rw[i] = n + 1; 915 } 916 func(0, n); 917 for (int i = 0; i < n; i++) 918 { 919 if (lw[i] == n + 1) lw[i] = n; 920 else lw[i] += (i - 1); 921 if (rw[i] == n + 1) rw[i] = -1; 922 else rw[i] = (i - rw[i] + 1); 923 } 924 kasai(); 925 init(); 926 build(0, 0, n); 927 cin >> q; 928 for (int i = 0; i < q; i++) 929 { 930 cin >> la[i] >> ra[i]; 931 la[i]--, ra[i]--; 932 } 933 border_check(); 934 for (int i = 0; i < q; i++) cout << query(la[i], ra[i], i) << "\n"; 935 return 0; 936 } 937 ``` 938 939 **Solution 2** 940 941 ``` 942 #include <bits/stdc++.h> 943 944 using namespace std; 945 946 #define TIME (clock() * 1.0 / CLOCKS_PER_SEC) 947 948 const int BIG = 1e9 + 239; 949 const int M = 2 * 1e5 + 239; 950 const int L = 19; 951 const int A = 30; 952 const int T = (1 << 19); 953 const int two = 2; 954 955 int flm[two][M]; 956 957 inline void z_function(string &s, int c) 958 { 959 int n = s.length(); 960 flm[c][0] = 0; 961 int l = 0; 962 int r = 0; 963 for (int i = 1; i < n; i++) 964 { 965 flm[c][i] = min(flm[c][i - l], r - i); 966 if (flm[c][i] < 0) flm[c][i] = 0; 967 while (i + flm[c][i] < n && s[flm[c][i]] == s[i + flm[c][i]]) flm[c][i]++; 968 if (i + flm[c][i] > r) 969 { 970 l = i; 971 r = i + flm[c][i]; 972 } 973 } 974 } 975 976 int a[M], lcp[M], pos[M]; 977 978 inline void suffix_array(string s) 979 { 980 s += (char)(31); 981 int n = s.length(); 982 vector<pair<char, int> > v; 983 for (int i = 0; i < n; i++) 984 v.push_back(make_pair(s[i], i)); 985 sort(v.begin(), v.end()); 986 vector<pair<int, int> > num; 987 int last = 0; 988 for (int i = 0; i < n - 1; i++) 989 { 990 num.push_back(make_pair(last, v[i].second)); 991 if (v[i].first != v[i + 1].first) last++; 992 } 993 num.push_back(make_pair(last, v.back().second)); 994 vector<int> u(n); 995 for (int i = 0; i < n; i++) u[num[i].second] = num[i].first; 996 int d = 1; 997 vector<pair<pair<int, int>, int> > t; 998 vector<vector<pair<int, int> > > h; 999 while (d < n) 1000 { 1001 t.clear(); 1002 h.clear(); 1003 h.resize(n); 1004 for (int i = 0; i < n; i++) 1005 { 1006 int l = num[i].second - d; 1007 if (l < 0) l += n; 1008 h[u[l]].push_back(make_pair(num[i].first, l)); 1009 } 1010 for (int i = 0; i < n; i++) 1011 for (pair<int, int> r : h[i]) 1012 t.push_back(make_pair(make_pair(i, r.first), r.second)); 1013 last = 0; 1014 num.clear(); 1015 for (int i = 0; i < n - 1; i++) 1016 { 1017 num.push_back(make_pair(last, t[i].second)); 1018 if (t[i].first != t[i + 1].first) last++; 1019 } 1020 num.push_back(make_pair(last, t.back().second)); 1021 for (int i = 0; i < n; i++) u[num[i].second] = num[i].first; 1022 d <<= 1; 1023 } 1024 for (int i = 1; i < n; i++) a[i - 1] = num[i].second; 1025 } 1026 1027 string s; 1028 1029 inline void kasai() 1030 { 1031 int n = s.size(); 1032 suffix_array(s); 1033 for (int i = 0; i < n; i++) 1034 pos[a[i]] = i; 1035 int k = 0; 1036 for (int i = 0; i < n; i++) 1037 { 1038 if (pos[i] == n - 1) continue; 1039 while (s[i + k] == s[a[pos[i] + 1] + k] && a[pos[i] + 1] + k < n && i + k < n) k++; 1040 lcp[pos[i]] = k; 1041 k = max(0, k - 1); 1042 } 1043 } 1044 1045 int n, lw[M], rw[M]; 1046 string prr, rvl; 1047 vector<int> open_l[M], close_l[M]; 1048 vector<int> open_r[M], close_r[M]; 1049 multiset<int> nw; 1050 1051 inline void func(int l, int r) 1052 { 1053 if (r - l == 1) return; 1054 int mid = (l + r) >> 1; 1055 func(l, mid); 1056 func(mid, r); 1057 rvl = ""; 1058 for (int i = mid - 1; i >= l; i--) rvl += s[i]; 1059 z_function(rvl, 0); 1060 prr = ""; 1061 for (int i = mid; i < r; i++) prr += s[i]; 1062 prr += '#'; 1063 for (int i = l; i < mid; i++) prr += s[i]; 1064 z_function(prr, 1); 1065 for (int c = l; c < mid; c++) 1066 { 1067 int k1 = 0; 1068 if (c > l) k1 = flm[0][mid - c]; 1069 int k2 = flm[1][r - mid + 1 + c - l]; 1070 int len = mid - c; 1071 int lg = max(len - k2, 0); 1072 int rg = min(len - 1, k1); 1073 if (rg >= lg) 1074 { 1075 open_l[c - rg].push_back((2 * len)); 1076 close_l[c - lg].push_back((2 * len)); 1077 open_r[c - rg + 2 * len - 1].push_back((2 * len)); 1078 close_r[c - lg + 2 * len - 1].push_back((2 * len)); 1079 } 1080 } 1081 rvl = ""; 1082 for (int i = mid; i < r; i++) rvl += s[i]; 1083 z_function(rvl, 0); 1084 prr = ""; 1085 for (int i = mid - 1; i >= l; i--) prr += s[i]; 1086 prr += '#'; 1087 for (int i = r - 1; i >= mid; i--) prr += s[i]; 1088 z_function(prr, 1); 1089 for (int c = mid; c < r; c++) 1090 { 1091 int k1 = 0; 1092 if (c != r - 1) k1 = flm[0][c + 1 - mid]; 1093 int k2 = flm[1][r - c + mid - l]; 1094 int len = c - mid + 1; 1095 int lg = max(len - k2, 0); 1096 int rg = min(len - 1, k1); 1097 if (rg >= lg) 1098 { 1099 open_l[c + lg - 2 * len + 1].push_back((2 * len)); 1100 close_l[c + rg - 2 * len + 1].push_back((2 * len)); 1101 open_r[c + lg].push_back((2 * len)); 1102 close_r[c + rg].push_back((2 * len)); 1103 } 1104 } 1105 for (int i = l; i < r; i++) 1106 { 1107 for (int len : open_l[i]) nw.insert(len); 1108 if (!nw.empty()) lw[i] = min(lw[i], *nw.begin()); 1109 for (int len : close_l[i]) nw.erase(nw.lower_bound(len)); 1110 open_l[i].clear(); 1111 close_l[i].clear(); 1112 } 1113 for (int i = l; i < r; i++) 1114 { 1115 for (int len : open_r[i]) nw.insert(len); 1116 if (!nw.empty()) rw[i] = min(rw[i], *nw.begin()); 1117 for (int len : close_r[i]) nw.erase(nw.lower_bound(len)); 1118 open_r[i].clear(); 1119 close_r[i].clear(); 1120 } 1121 } 1122 1123 int mn[L][M], st2[M], lc[L][M], kol[A][M]; 1124 1125 inline int getmin(int l, int r) 1126 { 1127 int u = st2[r - l + 1]; 1128 return min(mn[u][l], mn[u][r - (1 << u) + 1]); 1129 } 1130 1131 inline int gett(int l, int r) 1132 { 1133 if (l == r) return (n - l); 1134 l = pos[l]; 1135 r = pos[r]; 1136 if (l > r) swap(l, r); 1137 r--; 1138 int u = st2[r - l + 1]; 1139 return min(lc[u][l], lc[u][r - (1 << u) + 1]); 1140 } 1141 1142 int q, mnp[M]; 1143 1144 inline void init() 1145 { 1146 for (int i = 0; i < n; i++) mn[0][i] = lw[i]; 1147 for (int i = 0; i < n - 1; i++) lc[0][i] = lcp[i]; 1148 for (int i = 1; i < L; i++) 1149 for (int j = 0; j < n; j++) 1150 { 1151 int r = (j + (1 << (i - 1))); 1152 if (r >= n) 1153 { 1154 mn[i][j] = mn[i - 1][j]; 1155 continue; 1156 } 1157 mn[i][j] = min(mn[i - 1][j], mn[i - 1][r]); 1158 } 1159 for (int i = 1; i < L; i++) 1160 for (int j = 0; j < n - 1; j++) 1161 { 1162 int r = (j + (1 << (i - 1))); 1163 if (r >= n - 1) 1164 { 1165 lc[i][j] = lc[i - 1][j]; 1166 continue; 1167 } 1168 lc[i][j] = min(lc[i - 1][j], lc[i - 1][r]); 1169 } 1170 st2[1] = 0; 1171 for (int i = 2; i <= n; i++) 1172 { 1173 st2[i] = st2[i - 1]; 1174 if ((1 << (st2[i] + 1)) <= i) st2[i]++; 1175 } 1176 } 1177 1178 int u, len; 1179 1180 inline bool check(int l, int r) 1181 { 1182 for (int t = 1; t <= min(len, ((r - l + 1) / 2)); t++) 1183 if (gett(l, r - t + 1) >= t) 1184 return true; 1185 for (int i = max(0, pos[l] - len); i <= min(n - 1, pos[l] + len); i++) 1186 if (l < a[i] && a[i] <= r && gett(l, a[i]) >= r - a[i] + 1) 1187 return true; 1188 return false; 1189 } 1190 1191 inline bool checkno(int l, int r) 1192 { 1193 if (r - l + 1 > 26) return false; 1194 vector<int> kol(26, 0); 1195 for (int x = l; x <= r; x++) 1196 { 1197 if (kol[s[x] - 'a'] > 0) return false; 1198 kol[s[x] - 'a']++; 1199 } 1200 return true; 1201 } 1202 1203 inline bool try_kol(int l, int r, int p) 1204 { 1205 int len = (r - l + 1) / p; 1206 return (gett(l, l + len) >= (r - l + 1 - len)); 1207 } 1208 1209 inline bool ison(int l, int r, char x) 1210 { 1211 return (kol[x - 'a'][r + 1] > kol[x - 'a'][l]); 1212 } 1213 1214 inline int query(int l, int r) 1215 { 1216 if (checkno(l, r)) return -1; 1217 int len = (r - l + 1); 1218 while (len > 1) 1219 { 1220 int p = mnp[len]; 1221 if (try_kol(l, r, p)) return 1; 1222 while ((len % p) == 0) len /= p; 1223 } 1224 if (lw[l] <= r) return 2; 1225 if (rw[r] >= l) return 2; 1226 if (check(l, r)) return 2; 1227 if (ison(l + 1, r, s[l])) return 3; 1228 if (ison(l, r - 1, s[r])) return 3; 1229 if (getmin(l, r) <= r) return 3; 1230 return 4; 1231 } 1232 1233 int main() 1234 { 1235 cin.sync_with_stdio(0); 1236 cin >> n >> s; 1237 memset(mnp, -1, sizeof(mnp)); 1238 for (int i = 2; i <= n; i++) 1239 if (mnp[i] == -1) 1240 for (int j = i; j <= n; j += i) 1241 if (mnp[j] == -1) 1242 mnp[j] = i; 1243 memset(kol[0], 0, sizeof(kol[0])); 1244 for (int i = 0; i < n; i++) 1245 { 1246 for (int x = 0; x < 26; x++) kol[x][i + 1] = kol[x][i]; 1247 kol[s[i] - 'a'][i + 1]++; 1248 } 1249 for (int i = 0; i < n; i++) 1250 { 1251 lw[i] = n + 1; 1252 rw[i] = n + 1; 1253 } 1254 func(0, n); 1255 for (int i = 0; i < n; i++) 1256 { 1257 if (lw[i] == n + 1) lw[i] = n; 1258 else lw[i] += (i - 1); 1259 if (rw[i] == n + 1) rw[i] = -1; 1260 else rw[i] = (i - rw[i] + 1); 1261 } 1262 kasai(); 1263 init(); 1264 cin >> q; 1265 for (int i = 0; i < n; i++) 1266 if (i * i >= n) 1267 { 1268 len = i + 3; 1269 break; 1270 } 1271 for (int i = 0; i < q; i++) 1272 { 1273 int l, r; 1274 cin >> l >> r; 1275 l--, r--; 1276 cout << query(l, r) << "\n"; 1277 } 1278 return 0; 1279 } 1280 ``` 1281 1282 Author: [isaf27](/profile/isaf27 "Grandmaster isaf27")