codeforces-scrape

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

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 ```