1990.md (31190B)
1 Source: https://codeforces.com/blog/entry/131716 2 3 Thank you for participation and we hope you enjoy this round :) 4 5 Additionally, we sincerely invite you to join the unofficial round of TheForces Community tomorrow. Compete alongside many high-rated participants and earn your own rating in a our own rating system([TheForces Rating System](https://theforces.netlify.app/ratings))! 6 7 For more details, pls read <https://codeforces.com/blog/entry/131733>. 8 9 #### [A — Submission Bait](https://codeforces.com/contest/1990/problem/A) 10 11 **hint1** 12 13 For Alice, what if choosing the maximum value doesn't work? 14 15 **hint2** 16 17 Consider parity. 18 19 **solution 1** 20 21 Case $1$: When all values appear an even number of times, Alice will lose. This is because no matter which number Alice chooses, Bob can mimic Alice's move. 22 23 Case $2$: When at least one value appears an odd number of times, Alice will win. Alice only needs to choose the maximum value that appears an odd number of times, which will force Bob into Case $1$. 24 25 Time complexity: $O(n)$. 26 27 **solution 2** 28 29 Sort the array $a$ in non-increasing order. We can observe that any state can be represented as a prefix of the array $a$. Consider dynamic programming: let $dp_i$ denote whether the first player is guaranteed to win when the state is $a_{1...i}$ ($dp_i=1$ indicates a guaranteed win for the first player). We have the following formula: 30 31 * $dp_1=1$; 32 * $dp_i= \sim (dp_{i-1}$ & $dp_{id_1-1}$ & $dp_{id_2-1} \ldots)$, where $id_j$ satisfies $a_{id_j} \neq a_{id_j+1}$ and $id_j \lt i$. 33 34 Time complexity: $O(n^2)$. 35 36 **code(solution 1)** 37 38 ``` 39 #include <bits/stdc++.h> 40 using namespace std; 41 #define m_p make_pair 42 #define all(x) (x).begin(),(x).end() 43 #define sz(x) ((int)(x).size()) 44 #define fi first 45 #define se second 46 typedef long long ll; 47 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); 48 mt19937 rnf(2106); 49 const int N = 55; 50 51 int n; 52 int q[N]; 53 54 void solv() 55 { 56 cin >> n; 57 for (int i = 1; i <= n; ++i) 58 q[i] = 0; 59 for (int i = 1; i <= n; ++i) 60 { 61 int x; 62 cin >> x; 63 ++q[x]; 64 } 65 66 for (int i = 1; i <= n; ++i) 67 { 68 if (q[i] % 2 == 1) 69 { 70 cout << "YES\n"; 71 return; 72 } 73 } 74 cout << "NO\n"; 75 } 76 77 int main() 78 { 79 #ifdef SOMETHING 80 freopen("input.txt", "r", stdin); 81 //freopen("output.txt", "w", stdout); 82 #endif // SOMETHING 83 ios_base::sync_with_stdio(false), cin.tie(0); 84 85 int tt = 1; 86 cin >> tt; 87 while (tt--) 88 { 89 solv(); 90 } 91 return 0; 92 } 93 ``` 94 95 #### [B — Array Craft](https://codeforces.com/contest/1990/problem/B) 96 97 **hint1** 98 99 Starting from a trival construction. 100 101 **hint2** 102 103 Utilize the condition $x \gt y$. 104 105 **solution** 106 107 First, we consider making $presum_x \gt presum_j$ for all $x \lt i \le n$, and similarly for $y$. We can think of a trivial construction: $a[r, \ldots ,l]=[1, \ldots ,1], a[1, \ldots...,r-1]=[-1, \ldots, -1]$ and $a[l+1,\ldots,n]=[-1, \ldots, -1]$. 108 109 The construction doesn't works when $presum_x \lt 0$, but we are close to the correct solution. Next, we will make a little adjustment: $a[r, \ldots, l]=[1,\ldots,1], a[1, \ldots...,r-1]=[\ldots,1, -1]$ and $a[l+1,\ldots,n]=[-1,1, \ldots]$. 110 111 It is not hard to see $presum_x \ge presum_j$ for all $x \lt i \le n$, and for $1 \le i \le y$, $\max(presum_i)-min(presum_i)\le 1$. Thus, we get $presum_x \ge 2+presum_{y-1} \ge 2+min(presum_i) \ge 1+max(presum_i)$. The same applies to the suffix sum as well. Therefore, this construction is valid. 112 113 Time complexity: $O(n)$. 114 115 **Bonus** 116 117 Solve the problem when $x \le y$. 118 119 **code** 120 121 ``` 122 #include<bits/stdc++.h> 123 124 using namespace std; 125 126 int main(){ 127 ios::sync_with_stdio(false); 128 cin.tie(nullptr); 129 int t; 130 cin >> t; 131 while(t>0){ 132 t--; 133 int n,x,y; 134 cin >> n >> x >> y; 135 x--; y--; 136 vector<int> a(n,1); 137 int e; 138 e=-1; 139 for(int i=x+1;i<n;i++){ 140 a[i]=e; 141 e*=-1; 142 } 143 e=-1; 144 for(int i=y-1;i>=0;i--){ 145 a[i]=e; 146 e*=-1; 147 } 148 for(int i=0;i<n;i++){ 149 if(i){cout << " ";} 150 cout << a[i]; 151 }cout << "\n"; 152 } 153 return 0; 154 } 155 ``` 156 157 #### [C — Mad MAD Sum](https://codeforces.com/contest/1990/problem/C) 158 159 **hint1** 160 161 After one operation, the array becomes non-decreasing. 162 163 **hint2** 164 165 Consider $a_1=a_2=\ldots=a_n$, the operation seems to have shifted the array right. 166 167 **hint3** 168 169 When does the "right shift" parttern happen? 170 171 **solution** 172 173 Read hints first. 174 175 Let's consider only non-decreasing arrays. Observe a continuous segments $a[l...r]=x(l \lt r,x \gt 0)$, after one operation, we get $a[l+1,min(r+1,n)]=x$ holds. We can conclude that if, for all non-zero contiguous segments in the array (except the last one), their lengths are all greater than $1$, then the array follows the "right shift" parttern. Let's say this kind of array "good". 176 177 The last problem is when will the array become "good". Let's assume we get the array $b$ after one operation on array $a$, we get $b_i \lt b_{i+1} \lt b_{i+2}$. We can infer that $b_i=a_i,b_{i+1}=a_{i+1}$ and there is at least $a_j=a_{i+1}(j \le i)$, which shows that $a$ is not non-decreasing. In other words, after two operations, we can always get a "good" array. Then the calculating is trival. 178 179 Time complexity: $O(n)$. 180 181 **code** 182 183 ``` 184 #include <bits/stdc++.h> 185 using namespace std; 186 #define m_p make_pair 187 #define all(x) (x).begin(),(x).end() 188 #define sz(x) ((int)(x).size()) 189 #define fi first 190 #define se second 191 typedef long long ll; 192 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); 193 mt19937 rnf(2106); 194 const int N = 200005; 195 196 int n; 197 int a[N]; 198 199 bool c[N]; 200 void doit() 201 { 202 for (int i = 1; i <= n; ++i) 203 c[i] = false; 204 int maxu = 0; 205 for (int i = 1; i <= n; ++i) 206 { 207 if (c[a[i]]) 208 maxu = max(maxu, a[i]); 209 c[a[i]] = true; 210 a[i] = maxu; 211 } 212 } 213 214 void solv() 215 { 216 cin >> n; 217 for (int i = 1; i <= n; ++i) 218 cin >> a[i]; 219 220 ll ans = 0; 221 for (int i = 1; i <= n; ++i) 222 ans += a[i]; 223 doit(); 224 for (int i = 1; i <= n; ++i) 225 ans += a[i]; 226 doit(); 227 228 for (int i = 1; i <= n; ++i) 229 ans += (n - i + 1) * 1LL * a[i]; 230 cout << ans << "\n"; 231 } 232 233 int main() 234 { 235 #ifdef SOMETHING 236 freopen("input.txt", "r", stdin); 237 //freopen("output.txt", "w", stdout); 238 #endif // SOMETHING 239 ios_base::sync_with_stdio(false), cin.tie(0); 240 241 int tt = 1; 242 cin >> tt; 243 while (tt--) 244 { 245 solv(); 246 } 247 return 0; 248 } 249 ``` 250 251 **fun fact** 252 253 The title "Mad MAD Sum" is not only a pun on the words Mad and MAD (Maximum Appearing Duplicate), but also implies the solution to the problem :) 254 255 #### [D Grid Puzzle](https://codeforces.com/contest/1990/problem/D) 256 257 **hint1** 258 259 Obviously, when $a_i$ is large enough, we will definitely use operation $2$ on the $i$-th row. What is its specific value? 260 261 **hint2** 262 263 It is $5$(try to prove it). Now we can only consider $a_i \le 4$ cases. 264 265 **hint3** 266 267 From left to right, consider a greedy solution or a DP solution. 268 269 **solution** 270 271 Read hints first. 272 273 For $a_i \ge 5$, we will definitely use operation $2$ on the $i$-th row because at least three $2 \times 2$ subgrid are needed to cover it, which is not better then do three times operation $2$ in the $i-1,i$ and $i+1$ row. 274 275 Now we can only consider $a_i \le 4$ cases. Let's consider from left to right. 276 277 In the left most row, there are $3$ cases: 278 279 * there is no black cells Do nothing; 280 * there is $\le 2$ black cells. We can put one $2 \times 2$ subgrid greedily; 281 * there is $ \gt 2$ black cells. We just use one time operation $2$ in this row(try to prove it). 282 283 We can summarize that for the $i$-th row, there are only three situations where it is affected by the $i-1$-th row: 284 285 * it is not affected; 286 * the cells in the third and fourth columns have been colored white; 287 * the cells in the first and second columns have been colored white. 288 289 We can greedily process this process from left to right, or use DP. 290 291 Time complexity: $O(n)$. 292 293 **code(greedy)** 294 295 ``` 296 #include<bits/stdc++.h> 297 using namespace std; 298 #define MOD 1000000007 299 #define MODD 998244353 300 301 long long int bigmod(long long int a,long long int b){ 302 long long int ans=1,powa=a; 303 while(b>0){ 304 if(b%2==1){ 305 ans*=powa; 306 ans%=MOD; 307 } 308 powa=powa*powa; 309 powa%=MOD; 310 b/=2; 311 } 312 return ans; 313 } 314 315 void func(){ 316 int n; 317 cin >> n; 318 int arr[n]; 319 for(int i=0;i<n;i++){ 320 cin >> arr[i]; 321 } 322 bool b1=0,b2=0; 323 int ans=0; 324 for(int i=0;i<n;i++){ 325 if((!b1)&&(!b2)){ 326 if(arr[i]==0) continue; 327 ans++; 328 if(arr[i]<=2) b1=1; 329 } 330 else if(b1){ 331 b1=0; 332 if(arr[i]<=2) continue; 333 ans++; 334 if(arr[i]<=4) b2=1; 335 } 336 else{ 337 b2=0; 338 if(arr[i]==0) continue; 339 ans++; 340 if(arr[i]<=4) b1=1; 341 } 342 } 343 cout << ans << '\n'; 344 return; 345 } 346 347 int main(){ 348 ios_base::sync_with_stdio(false); 349 cin.tie(NULL); cout.tie(NULL); 350 int t; 351 cin >> t; 352 while(t--){ 353 func(); 354 } 355 } 356 //i added the bigmod func to my code cause yes 357 ``` 358 359 **code(DP)** 360 361 ``` 362 #include <bits/stdc++.h> 363 using namespace std; 364 #define m_p make_pair 365 #define all(x) (x).begin(),(x).end() 366 #define sz(x) ((int)(x).size()) 367 #define fi first 368 #define se second 369 typedef long long ll; 370 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); 371 mt19937 rnf(2106); 372 const int N = 200005; 373 374 int n; 375 int a[N]; 376 377 int dp[N]; 378 void minh(int& x, int y) 379 { 380 x = min(x, y); 381 } 382 383 void solv() 384 { 385 cin >> n; 386 for (int i = 1; i <= n; ++i) 387 cin >> a[i]; 388 389 int minu[2] = {N, N}; 390 for (int i = 1; i <= n; ++i) 391 { 392 dp[i] = dp[i - 1] + 1; 393 if (a[i] == 0) 394 minh(dp[i], dp[i - 1]); 395 if (a[i] <= 2) 396 minh(dp[i], i + minu[1 - i % 2]); 397 398 if (a[i] <= 2) 399 minh(minu[i % 2], dp[i - 1] - i); 400 else if (a[i] > 4) 401 minu[0] = minu[1] = N; 402 } 403 404 cout << dp[n] << "\n"; 405 } 406 407 int main() 408 { 409 #ifdef SOMETHING 410 freopen("input.txt", "r", stdin); 411 //freopen("output.txt", "w", stdout); 412 #endif // SOMETHING 413 ios_base::sync_with_stdio(false), cin.tie(0); 414 415 int tt = 1; 416 cin >> tt; 417 while (tt--) 418 { 419 solv(); 420 } 421 return 0; 422 } 423 ``` 424 425 #### [E Catch the Mole](https://codeforces.com/contest/1990/problem/E2) 426 427 **hint1** 428 429 Consider querying a subtree. If the jury returns $0$, we can delete the entire subtree. 430 431 **hint2** 432 433 We can query any leaf node. If the jury returns $1$, we are done; otherwise, the mole will move up. 434 435 **hint3** 436 437 Consider querying a subtree. If the jury returns $1$, we can "drive" it out of this subtree using the method in hint2. 438 439 **hint4** 440 441 Combime the idea in hint $1$ and $3$. 442 443 **solution1** 444 445 Read hints first. 446 447 For easy version, we can pick a vertex $v$ such that $maxdep_v-dep_v+1=50$: 448 449 1. if the jury returns $0$, we can delete the entire subtree; 450 2. otherwise, make queries until it is out and answer $fa_v$(a special case is $v=1$); 451 3. if there is no such vertex, then make $100$ queries and answer the root node $1$. 452 453 This costs about $200$ queries, which can not pass hard version. But we can optimize it. 454 455 The bottleneck is the step $2$, when we drive away this mole once, we need to immediately check if it is still in the subtree $v$, which can be optimized. In fact, we can drive the mole 50 times and then perform a binary search on the chain from $v$ to the root node. 456 457 Number of queries: $O(2sqrt(n)+log(n))$ 458 459 **solution2** 460 461 Query any leaf $70$ times, then delete all nodes $x$ such that $maxdep_v-dep_v+1 \lt =70$. Then the tree can be split into $\le 70$ chains. Do binary search for these chains. 462 463 **bonus** 464 465 Solve the problem in $100$ queries. 466 467 **code(hard version)** 468 469 ``` 470 #include<bits/stdc++.h> 471 using namespace std; 472 473 #define all(a) a.begin(),a.end() 474 #define pb push_back 475 #define sz(a) ((int)a.size()) 476 477 using ll=long long; 478 using u32=unsigned int; 479 using u64=unsigned long long; 480 using i128=__int128; 481 using u128=unsigned __int128; 482 using f128=__float128; 483 484 using pii=pair<int,int>; 485 using pll=pair<ll,ll>; 486 487 template<typename T> using vc=vector<T>; 488 template<typename T> using vvc=vc<vc<T>>; 489 template<typename T> using vvvc=vc<vvc<T>>; 490 491 using vi=vc<int>; 492 using vll=vc<ll>; 493 using vvi=vc<vi>; 494 using vvll=vc<vll>; 495 496 #define vv(type,name,n,...) \ 497 vector<vector<type>> name(n,vector<type>(__VA_ARGS__)) 498 #define vvv(type,name,n,m,...) \ 499 vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__))) 500 501 template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>; 502 template<typename T> using max_heap=priority_queue<T>; 503 504 // https://trap.jp/post/1224/ 505 #define rep1(n) for(ll i=0; i<(ll)(n); ++i) 506 #define rep2(i,n) for(ll i=0; i<(ll)(n); ++i) 507 #define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i) 508 #define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c)) 509 #define cut4(a,b,c,d,e,...) e 510 #define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) 511 #define per1(n) for(ll i=((ll)n)-1; i>=0; --i) 512 #define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i) 513 #define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i) 514 #define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c)) 515 #define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__) 516 #define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s))) 517 518 template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);} 519 template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);} 520 521 template<typename T> 522 void sort_unique(vector<T> &vec){ 523 sort(vec.begin(),vec.end()); 524 vec.resize(unique(vec.begin(),vec.end())-vec.begin()); 525 } 526 527 template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;} 528 template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;} 529 530 template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;} 531 template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;} 532 533 #ifdef i_am_noob 534 #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) 535 template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 536 template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 537 template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 538 template<typename T> void _do(T && x) {cerr << x << endl;} 539 template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);} 540 #else 541 #define bug(...) 777771449 542 #endif 543 544 template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 545 template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 546 template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 547 template<typename T> void print(T && x) {cout << x << "\n";} 548 template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);} 549 550 template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;} 551 552 vvi read_graph(int n, int m, int base=1){ 553 vvi adj(n); 554 for(int i=0,u,v; i<m; ++i){ 555 cin >> u >> v,u-=base,v-=base; 556 adj[u].pb(v),adj[v].pb(u); 557 } 558 return adj; 559 } 560 561 vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);} 562 563 template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};} 564 565 template<typename T> constexpr T inf=0; 566 template<> constexpr int inf<int> = 0x3f3f3f3f; 567 template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f; 568 569 template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;} 570 571 template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;} 572 573 #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) 574 575 //#include<atcoder/all> 576 //using namespace atcoder; 577 578 //using mint=modint998244353; 579 //using mint=modint1000000007; 580 581 struct Tree{ 582 int n; 583 vector<vector<int>> adj,anc; 584 vector<int> par,tl,tr,dep,ord,siz,ch,head; 585 Tree(int _n=0){ 586 n=_n; 587 adj.resize(n); 588 } 589 void add_edge(int u, int v){ 590 adj[u].push_back(v); 591 adj[v].push_back(u); 592 } 593 void init(){ 594 par.resize(n),tl.resize(n),tr.resize(n),dep.resize(n),anc.resize(n),siz.resize(n),ch.resize(n),head.resize(n); 595 int cur=-1,m=0; 596 while((1<<m)<=n) m++; 597 for(int i=0; i<n; ++i) anc[i].resize(m),ch[i]=-1; 598 auto dfs1=[&](auto &self, int u, int fa) -> void{ 599 par[u]=fa; 600 siz[u]=1; 601 for(int v: adj[u]) if(v!=fa) self(self,v,u),siz[u]+=siz[v]; 602 for(int v: adj[u]) if(v!=fa&&(ch[u]==-1||siz[v]>siz[ch[u]])) ch[u]=v; 603 }; 604 auto dfs2=[&](auto &self, int u, int fa) -> void{ 605 ord.push_back(u); 606 tl[u]=++cur; 607 anc[u][0]=fa; 608 if(fa==-1) dep[u]=0; 609 else dep[u]=dep[fa]+1; 610 for(int i=1; i<m; ++i){ 611 if(anc[u][i-1]==-1) anc[u][i]=-1; 612 else anc[u][i]=anc[anc[u][i-1]][i-1]; 613 } 614 if(ch[u]!=-1) self(self,ch[u],u); 615 for(int v: adj[u]) if(v!=fa&&v!=ch[u]) self(self,v,u); 616 tr[u]=cur; 617 }; 618 dfs1(dfs1,0,-1); 619 dfs2(dfs2,0,-1); 620 head[0]=0; 621 for(int u: ord){ 622 for(int v: adj[u]) if(v!=par[u]){ 623 if(v==ch[u]) head[v]=head[u]; 624 else head[v]=v; 625 } 626 } 627 } 628 bool is_anc(int u, int v){return tl[u]<=tl[v]&&tr[u]>=tr[v];} 629 int get_anc(int u, int x){ 630 for(int i=anc[0].size()-1; i>=0; --i) if(u!=-1&&(x>>i&1)) u=anc[u][i]; 631 return u; 632 } 633 int lca(int u, int v){ 634 if(is_anc(u,v)) return u; 635 for(int i=anc[0].size()-1; i>=0; --i) if(anc[u][i]!=-1&&!is_anc(anc[u][i],v)) u=anc[u][i]; 636 return par[u]; 637 } 638 }; 639 640 void ahcorz(){ 641 int lft=150; 642 auto query=[&](int u){ 643 assert(lft>0); 644 cout << "? " << u+1 << endl; 645 lft--; 646 int res; cin >> res; return res; 647 }; 648 int n; cin >> n; 649 Tree tree(n); 650 rep(n-1){ 651 int u,v; cin >> u >> v; u--,v--; 652 tree.add_edge(u,v); 653 } 654 tree.init(); 655 vi vis(n); 656 auto fill_vis=[&](auto &self, int u){ 657 if(vis[u]) return; 658 vis[u]=1; 659 for(int v: tree.adj[u]) if(v!=tree.par[u]) self(self,v); 660 }; 661 vi ord(n); iota(all(ord),0); 662 sort(all(ord),[&](int i, int j){return tree.dep[i]<tree.dep[j];}); 663 per(n){ 664 int u=ord[i]; 665 if(vis[u]) continue; 666 int v=u; 667 rep(_,(lft-1)/2-1){ 668 if(v==0) break; 669 v=tree.par[v]; 670 } 671 if(!query(v)){ 672 fill_vis(fill_vis,v); 673 continue; 674 } 675 int x=tree.ord.back(); 676 int m=tree.dep[u]-tree.dep[v]+1; 677 rep(_,m){ 678 if(query(x)){ 679 cout << "! " << x+1 << endl; 680 return; 681 } 682 if(!query(v)){ 683 int y=tree.par[v]; 684 if(y!=-1) y=tree.par[y]; 685 if(y==-1) y=0; 686 cout << "! " << y+1 << endl; 687 return; 688 } 689 } 690 cout << "! 1" << endl; 691 return; 692 } 693 assert(0); 694 } 695 696 signed main(){ 697 ios_base::sync_with_stdio(0),cin.tie(0); 698 cout << fixed << setprecision(20); 699 int t=1; 700 cin >> t; 701 while(t--) ahcorz(); 702 } 703 ``` 704 705 #### [F Polygonal Segments](https://codeforces.com/contest/1990/problem/F) 706 707 **solution1** 708 709 Consider using a segment tree to solve this problem. We need to merge the information of two intervals. First, we take the maximum value of the answers in the two intervals, and then calculate the polygon segment spanning the two intervals. 710 711 We notice that a local maximal polygon segment $[l, r]$ must satisfy $min(a_{l-1}, a_{r+1}) \gt = 2(a_l + ... + a_r)$(or $l=1$,$r=n$). 712 713 Define the suffix $[i, r]$ of the interval $[l, r]$ as a **special suffix** if and only if $a_i+ \ldots +a_r$ $\le 2 \cdot a_i$. The same principle applies to special prefixes. 714 715 We can observe that there are at most $O(log(maxa))$ special suffixes, because the sum of one special suffix is at least twice the sum of the previous special suffix. Therefore, we can merge the special suffixes of the left interval and the special prefixes of the right interval (using the two-pointer algorithm) to obtain the answer spanning the two intervals. 716 717 Number of queries: $O(nlog^2(n))$ 718 719 **solution2** 720 721 Consider the following process: 722 723 ``` 724 query(l,r) 725 if r-l+1<3 return -1 726 mxp=getmaxpos(l,r) 727 if 2*a[mxp]<getsum(l,r) return r-l+1 728 else return max(query(l,mxp-1),query(mxp+1,r)) 729 ``` 730 731 This looks $O(n^2)$ when $a=[1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,... ]$. However, if we store all the ranges which are already calculated, it becomes $O(n log n)$. 732 733 Why? Let's call a range $[l,r]$ "key range" when $sum(a[l...r]) \lt =2min(a[l-1],a[r+1])$. We can see: 734 735 1.There're only $O(n log n)$ different key ranges; 736 737 2.We only visit at most $2$ ranges which are not key range in each query. 738 739 Assume we have changed $a_p$. We need to clear all the answer of key ranges which pass through $p$. We can use [interval tree](https://en.wikipedia.org/wiki/Interval_tree) to achieve it. 740 741 **code(solution 1)** 742 743 ``` 744 #include <map> 745 #include <set> 746 #include <cmath> 747 #include <ctime> 748 #include <queue> 749 #include <stack> 750 #include <cstdio> 751 #include <cstdlib> 752 #include <vector> 753 #include <cstring> 754 #include <algorithm> 755 #include <iostream> 756 #include <bitset> 757 using namespace std; 758 typedef double db; 759 typedef long long ll; 760 typedef unsigned long long ull; 761 const int N=1000010; 762 const int LOGN=28; 763 const ll TMD=0; 764 const ll INF=2147483647; 765 int T,n,q; 766 ll a[N]; 767 768 //---------------------------------------------------------- 769 770 struct INFO 771 { 772 int ans,l,r; 773 ll sum; 774 vector<int> lpos,rpos; 775 vector<ll> lsum,rsum; 776 }; 777 778 struct nod 779 { 780 INFO info; 781 nod *lc,*rc; 782 }; 783 784 struct Segtree 785 { 786 nod *root; 787 788 Segtree() 789 { 790 build(&root,1,n); 791 } 792 793 void newnod(nod **p,int l,int r) 794 { 795 *p=new nod; 796 (*p)->info.l=l; 797 (*p)->info.r=r; 798 (*p)->info.sum=(*p)->info.ans=0; 799 (*p)->lc=(*p)->rc=NULL; 800 } 801 802 INFO merge_info(INFO x,INFO y) 803 { 804 INFO z; 805 z.l=x.l; 806 z.r=y.r; 807 z.sum=x.sum+y.sum; 808 z.ans=max(x.ans,y.ans); 809 int px=(int)x.lpos.size()-1,py=0; 810 ll mx=0; 811 // 812 //return z; 813 // 814 // 815 while(1) //two pointer 816 { 817 int len=0; 818 ll sum=0; 819 if(px<0) 820 { 821 sum+=x.sum; 822 len+=(x.r-x.l+1); 823 } 824 else 825 { 826 sum+=x.lsum[px]-a[x.lpos[px]]; 827 len+=(x.r-x.lpos[px]); 828 } 829 if(py<y.rpos.size()) 830 { 831 sum+=y.rsum[py]-a[y.rpos[py]]; 832 len+=(y.rpos[py]-y.l); 833 } 834 else 835 { 836 sum+=y.sum; 837 len+=(y.r-y.l+1); 838 } 839 if(sum>2*mx) z.ans=max(z.ans,len); 840 if(px<0&&py>=y.rpos.size()) break; 841 else if(px<0) mx=max(mx,a[y.rpos[py]]),py++; 842 else if(py>=y.rpos.size()) mx=max(mx,a[x.lpos[px]]),px--; 843 else if(a[x.lpos[px]]<a[y.rpos[py]]) mx=max(mx,a[x.lpos[px]]),px--; 844 else mx=max(mx,a[y.rpos[py]]),py++; 845 } 846 // 847 /* 848 z.lpos.resize(1); 849 z.rpos.resize(1); 850 z.lsum.resize(1); 851 z.rsum.resize(1); 852 */ 853 // 854 if(z.ans<3) z.ans=-1; 855 for(int i=0;i<x.lpos.size();i++) 856 if(2*a[x.lpos[i]]>=x.lsum[i]+y.sum) z.lpos.push_back(x.lpos[i]),z.lsum.push_back(x.lsum[i]+y.sum); 857 for(int i=0;i<y.lpos.size();i++) 858 z.lpos.push_back(y.lpos[i]),z.lsum.push_back(y.lsum[i]); 859 for(int i=0;i<x.rpos.size();i++) 860 z.rpos.push_back(x.rpos[i]),z.rsum.push_back(x.rsum[i]); 861 for(int i=0;i<y.rpos.size();i++) 862 if(2*a[y.rpos[i]]>=y.rsum[i]+x.sum) z.rpos.push_back(y.rpos[i]),z.rsum.push_back(y.rsum[i]+x.sum); 863 // 864 return z; 865 } 866 867 void build(nod **p,int L,int R) 868 { 869 newnod(p,L,R); 870 if(L==R) 871 { 872 (*p)->info.sum=a[L]; 873 (*p)->info.ans=-1; 874 (*p)->info.lpos.push_back(L); 875 (*p)->info.rpos.push_back(L); 876 (*p)->info.lsum.push_back(a[L]); 877 (*p)->info.rsum.push_back(a[L]); 878 return ; 879 } 880 int M=(L+R)>>1; 881 build(&(*p)->lc,L,M); 882 build(&(*p)->rc,M+1,R); 883 (*p)->info=merge_info((*p)->lc->info,(*p)->rc->info); 884 } 885 886 void modify(int pos,ll val) 887 { 888 _modify(root,pos,val); 889 } 890 891 void _modify(nod *p,int pos,ll val) 892 { 893 if(p->info.l==p->info.r) 894 { 895 p->info.sum=val; 896 p->info.lpos[0]=pos; 897 p->info.rpos[0]=pos; 898 p->info.lsum[0]=val; 899 p->info.rsum[0]=val; 900 return ; 901 } 902 int M=(p->info.l+p->info.r)>>1; 903 if(pos<=M) _modify(p->lc,pos,val); 904 else _modify(p->rc,pos,val); 905 p->info=merge_info(p->lc->info,p->rc->info); 906 } 907 908 ll getans(int L,int R) 909 { 910 return _getans(root,L,R).ans; 911 } 912 913 INFO _getans(nod *p,int L,int R) 914 { 915 if(p->info.l==L&&p->info.r==R) return p->info; 916 int M=(p->info.l+p->info.r)>>1; 917 if(R<=M) return _getans(p->lc,L,R); 918 else if(L>M) return _getans(p->rc,L,R); 919 else return merge_info(_getans(p->lc,L,M),_getans(p->rc,M+1,R)); 920 } 921 }; 922 923 //---------------------------------------------------------- 924 925 int main() 926 { 927 //freopen("test.in","r",stdin); 928 929 scanf("%d",&T); 930 while(T--) 931 { 932 scanf("%d%d",&n,&q); 933 for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); 934 Segtree TR; 935 for(int i=1;i<=q;i++) 936 { 937 int t; 938 scanf("%d",&t); 939 if(t==1) 940 { 941 int l,r; 942 scanf("%d%d",&l,&r); 943 printf("%I64d\n",TR.getans(l,r)); 944 } 945 else 946 { 947 int p; 948 ll x; 949 scanf("%d%I64d",&p,&x); 950 a[p]=x; 951 TR.modify(p,x); 952 } 953 } 954 } 955 956 //fclose(stdin); 957 return 0; 958 } 959 ``` 960 961 **code(solution 2)** 962 963 ``` 964 // #pragma GCC optimize("O3,unroll-loops") 965 // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 966 #include "bits/stdc++.h" 967 using namespace std; 968 using ll = long long int; 969 mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count()); 970 971 /** 972 * Point-update Segment Tree 973 * Source: kactl 974 * Description: Iterative point-update segment tree, ranges are half-open i.e [L, R). 975 * f is any associative function. 976 * Time: O(logn) update/query 977 */ 978 979 template<class T, T unit = T()> 980 struct SegTree { 981 T f(T a, T b) { 982 a[0] += b[0]; 983 if (a[1] < b[1]) a[1] = b[1], a[2] = b[2]; 984 return a; 985 } 986 vector<T> s; int n; 987 SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {} 988 void update(int pos, T val) { 989 for (s[pos += n] = val; pos /= 2;) 990 s[pos] = f(s[pos * 2], s[pos * 2 + 1]); 991 } 992 T query(int b, int e) { 993 T ra = unit, rb = unit; 994 for (b += n, e += n; b < e; b /= 2, e /= 2) { 995 if (b % 2) ra = f(ra, s[b++]); 996 if (e % 2) rb = f(s[--e], rb); 997 } 998 return f(ra, rb); 999 } 1000 }; 1001 1002 #include <ext/pb_ds/assoc_container.hpp> 1003 1004 struct splitmix64_hash { 1005 static uint64_t splitmix64(uint64_t x) { 1006 // http://xorshift.di.unimi.it/splitmix64.c 1007 x += 0x9e3779b97f4a7c15; 1008 x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; 1009 x = (x ^ (x >> 27)) * 0x94d049bb133111eb; 1010 return x ^ (x >> 31); 1011 } 1012 1013 size_t operator()(uint64_t x) const { 1014 static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); 1015 return splitmix64(x + FIXED_RANDOM); 1016 } 1017 }; 1018 1019 template <typename K, typename V, typename Hash = splitmix64_hash> 1020 using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>; 1021 1022 template <typename K, typename Hash = splitmix64_hash> 1023 using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>; 1024 1025 int main() 1026 { 1027 ios::sync_with_stdio(false); cin.tie(0); 1028 1029 int t; cin >> t; 1030 while (t--) { 1031 int n, q; cin >> n >> q; 1032 vector<ll> a(n); 1033 for (auto &x : a) cin >> x; 1034 1035 map<ll, int> cache; 1036 1037 struct Node { 1038 int L, R, M; // [L, R) 1039 set<array<int, 2>> by_l, by_r; 1040 void ins(int l, int r) { 1041 by_l.insert({l, r}); 1042 by_r.insert({r, l}); 1043 } 1044 void del(int l, int r) { 1045 by_l.erase({l, r}); 1046 by_r.erase({r, l}); 1047 } 1048 }; 1049 vector<Node> ITree(4*n); 1050 auto build = [&] (const auto &self, int node, int l, int r) -> void { 1051 int mid = (l + r)/2; 1052 ITree[node].L = l; 1053 ITree[node].R = r; 1054 ITree[node].M = mid; 1055 if (l+1 == r) return; 1056 self(self, 2*node + 1, l, mid); 1057 self(self, 2*node + 2, mid, r); 1058 }; 1059 build(build, 0, 0, n); 1060 auto insert = [&] (const auto &self, int node, int l, int r) -> void { // Insert interval [l, r) into the tree 1061 if (ITree[node].L+1 == ITree[node].R) { 1062 ITree[node].ins(l, r); 1063 return; 1064 } 1065 1066 if (l >= ITree[node].M) self(self, 2*node+2, l, r); 1067 else if (r <= ITree[node].M) self(self, 2*node+1, l, r); 1068 else ITree[node].ins(l, r); 1069 }; 1070 auto erase = [&] (const auto &self, int node, int x) -> void { // Delete all intervals covering point x 1071 if (x < ITree[node].M) { 1072 // Delete some prefix 1073 auto &st = ITree[node].by_l; 1074 while (!st.empty()) { 1075 auto [l, r] = *begin(st); 1076 if (l <= x) { 1077 ITree[node].del(l, r); 1078 ll id = 1ll*(n+1)*l + r; 1079 cache.erase(id); 1080 } 1081 else break; 1082 } 1083 } 1084 else { 1085 // Delete some suffix 1086 auto &st = ITree[node].by_r; 1087 while (!st.empty()) { 1088 auto [r, l] = *rbegin(st); 1089 if (r > x) { 1090 ITree[node].del(l, r); 1091 ll id = 1ll*(n+1)*l + r; 1092 cache.erase(id); 1093 } 1094 else break; 1095 } 1096 } 1097 1098 if (ITree[node].L+1 == ITree[node].R) return; 1099 if (x < ITree[node].M) self(self, 2*node+1, x); 1100 else self(self, 2*node+2, x); 1101 }; 1102 1103 constexpr array<ll, 3> unit = {0, 0, -1}; 1104 SegTree<array<ll, 3>, unit> seg(n); 1105 for (int i = 0; i < n; ++i) seg.update(i, array<ll, 3>{a[i], a[i], i}); 1106 1107 auto solve = [&] (const auto &self, int L, int R) -> int { 1108 if (R-L <= 2) return -1; 1109 ll id = 1ll*L*(n+1) + R; 1110 if (cache.find(id) != cache.end()) return cache[id]; 1111 1112 auto [sm, mx, pivot] = seg.query(L, R); 1113 1114 insert(insert, 0, L, R); 1115 if (mx < sm - mx) { 1116 return cache[id] = R-L; 1117 } 1118 else { 1119 int ret = self(self, L, pivot); 1120 ret = max(ret, self(self, pivot+1, R)); 1121 return cache[id] = ret; 1122 } 1123 }; 1124 1125 while (q--) { 1126 int type; cin >> type; 1127 if (type == 1) { 1128 int l, r; cin >> l >> r; 1129 cout << solve(solve, l-1, r) << '\n'; 1130 } 1131 else { 1132 ll pos, val; cin >> pos >> val; --pos; 1133 1134 erase(erase, 0, pos); 1135 if (pos) erase(erase, 0, pos-1); 1136 if (pos+1 < n) erase(erase, 0, pos+1); 1137 seg.update(pos, array<ll, 3>{val, val, pos}); 1138 } 1139 } 1140 } 1141 } 1142 ```