codeforces-scrape

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

1868.md (42022B)


      1 Source: https://codeforces.com/blog/entry/116642
      2 
      3 [1869A - Make It Zero](/contest/1869/problem/A "Codeforces Round 896 (Div. 2)")
      4 
      5 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan")
      6 
      7 **Hint 1**
      8 
      9 Indeed at most $\bf 4$ operations will be used.
     10 
     11 **Hint 2**
     12 
     13 If $r-l+1$ is even, and you do the operation on $[l,r]$ twice, then the subarray $a[l;r]$ will all become $0$.
     14 
     15 **Solution**
     16 
     17 Tutorial is loading...
     18 
     19 **Implementation**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 #define all(s) s.begin(), s.end()
     24 using namespace std;
     25 using ll = long long;
     26 using ull = unsigned long long;
     27 
     28 const int _N = 1e5 + 5;
     29 
     30 int T;
     31 
     32 void solve() {
     33 	int n; cin >> n;
     34 	vector<int> a(n);
     35 	for (int i = 0; i < n; i++) cin >> a[i];
     36 	if (n & 1) {
     37 		cout << "4" << '\n';
     38 		cout << "1 " << n - 1 << '\n';
     39 		cout << "1 " << n - 1 << '\n';
     40 		cout << n - 1 << ' ' << n << '\n';
     41 		cout << n - 1 << ' ' << n << '\n';
     42 	} else {
     43 		cout << "2" << '\n';
     44 		cout << "1 " << n << '\n';
     45 		cout << "1 " << n << '\n';
     46 	}
     47 	return;
     48 }
     49 
     50 int main() {
     51 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
     52 	cin >> T;
     53 	while (T--) {
     54 		solve();
     55 	}
     56 }
     57 ```
     58 
     59 **Rate the problem**
     60 
     61 * Amazing problem:
     62 * Good problem:
     63 * Average problem:
     64 * Bad problem:
     65 * Didn't solve:
     66 
     67 [1869B - 2D Traveling](/contest/1869/problem/B "Codeforces Round 896 (Div. 2)")
     68 
     69 Author: [programpiggy](/profile/programpiggy "Expert programpiggy")
     70 
     71 **Hint**
     72 
     73 What will happen if there are no major cities?
     74 
     75 **Solution**
     76 
     77 Tutorial is loading...
     78 
     79 **Implementation**
     80 
     81 ```
     82 #include <bits/stdc++.h>
     83 #define all(s) s.begin(), s.end()
     84 using namespace std;
     85 using ll = long long;
     86 using ull = unsigned long long;
     87 
     88 const int _N = 1e5 + 5;
     89 
     90 int T;
     91 
     92 void solve() {
     93 	int n, k, s, t; cin >> n >> k >> s >> t;
     94 	vector<int> x(n + 1), y(n + 1);
     95 	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
     96 	ll ans = llabs(x[s] - x[t]) + llabs(y[s] - y[t]);
     97 	ll mins = LLONG_MAX / 2, mint = LLONG_MAX / 2;
     98 	for (int i = 1; i <= k; i++) {
     99 		mins = min(mins, llabs(x[s] - x[i]) + llabs(y[s] - y[i]));
    100 		mint = min(mint, llabs(x[t] - x[i]) + llabs(y[t] - y[i]));
    101 	}
    102 	ans = min(ans, mins + mint);
    103 	cout << ans << '\n';
    104 	return;
    105 }
    106 
    107 int main() {
    108 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    109 	cin >> T;
    110 	while (T--) {
    111 		solve();
    112 	}
    113 }
    114 ```
    115 
    116 **Rate the problem**
    117 
    118 * Amazing problem:
    119 * Good problem:
    120 * Average problem:
    121 * Bad problem:
    122 * Didn't solve:
    123 
    124 [1868A - Fill in the Matrix](/contest/1868/problem/A "Codeforces Round 896 (Div. 1)")
    125 
    126 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan")
    127 
    128 **Hint 1**
    129 
    130 What is the upper bound of $s$ according to $n$ and $m$? Can you construct such a matrix that reaches the upper bound?
    131 
    132 **Hint 2**
    133 
    134 If not, can you construct a matrix which maximizes $\sum_{i=1}^m v_i$? This is of some help to get the solution.
    135 
    136 **Solution**
    137 
    138 Tutorial is loading...
    139 
    140 **Implementation**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 #define all(s) s.begin(), s.end()
    145 using namespace std;
    146 using ll = long long;
    147 using ull = unsigned long long;
    148 
    149 const int _N = 1e5 + 5;
    150 
    151 int T;
    152 
    153 void solve() {
    154 	int n, m;
    155 	cin >> n >> m;
    156 	if (m == 1) cout << 0 << '\n';
    157 	else if (n > m - 1) cout << m << '\n';
    158 	else cout << n + 1 << '\n';
    159 	for (int i = 0; i < min(m - 1, n); i++) {
    160 		for (int j = 0; j < m; j++) {
    161 			cout << (j + i) % m << ' ';
    162 		}
    163 		cout << '\n';
    164 	}
    165 	if (n > m - 1) {
    166 		for (int i = m - 1; i < n; i++) {
    167 			for (int j = 0; j < m; j++) {
    168 				cout << j << ' ';
    169 			}
    170 			cout << '\n';
    171 		}
    172 	}
    173 	return;
    174 }
    175 
    176 int main() {
    177 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    178 	cin >> T;
    179 	while (T--) {
    180 		solve();
    181 	}
    182 }
    183 ```
    184 
    185 **Rate the problem**
    186 
    187 * Amazing problem:
    188 * Good problem:
    189 * Average problem:
    190 * Bad problem:
    191 * Didn't solve:
    192 
    193 [1868B1 - Candy Party (Easy Version)](/contest/1868/problem/B1 "Codeforces Round 896 (Div. 1)")
    194 
    195 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan")
    196 
    197 **Hint 1**
    198 
    199 You can calculate the number of candies of each person after the swap easily. Denote the number as $s$.
    200 
    201 **Hint 2**
    202 
    203 Since a person gives candies to and receives candies from exactly one person, assume he gives away $2^x$ candies and receives $2^y$ candies, then we have $a_i - 2^x + 2^y = s$. If $a_i \ne s$, at most how many pairs $(x,y)$ can satisfy this equation?
    204 
    205 **Hint 3**
    206 
    207 Do the two restrictions in the statement,
    208 
    209 > Note that one cannot give more candies than currently he has (he might receive candies from someone else before) and he cannot give candies to himself, either.
    210 
    211 really make any difference to the answer?
    212 
    213 **Solution**
    214 
    215 Tutorial is loading...
    216 
    217 **Implementation**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221 #define all(s) s.begin(), s.end()
    222 using namespace std;
    223 using ll = long long;
    224 using ull = unsigned long long;
    225 
    226 const int _N = 1e5 + 5;
    227 
    228 int T;
    229 
    230 void solve() {
    231 	int n; cin >> n;
    232 	vector<ll> a(n); ll sum = 0;
    233 	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
    234 	if (sum % n) return cout << "No" << '\n', void();
    235 	sum /= n;
    236 	vector<int> bit(31, 0);
    237 	auto lowbit = [](int x) {
    238 	    return x & (-x);
    239 	};
    240 	for (int i = 0; i < n; i++) {
    241 		if (a[i] == sum) continue;
    242 		int d = abs(a[i] - sum);
    243 		int p = lowbit(d);
    244 		int e = d + p;
    245 		if (__builtin_popcount(e) == 1) {
    246 		    if (a[i] > sum) bit[__lg(e)]++, bit[__lg(p)]--;
    247 		    else bit[__lg(e)]--, bit[__lg(p)]++;
    248 		} else {
    249 		    cout << "No" << '\n';
    250 		    return;
    251 		}
    252 	}
    253 	for (int i = 0; i < 31; i++) {
    254 		if (bit[i]) {
    255 			cout << "No" << '\n';
    256 			return;
    257 		}
    258 	}
    259 	cout << "Yes" << '\n';
    260 	return;
    261 }
    262 
    263 int main() {
    264 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    265 	cin >> T;
    266 	while (T--) {
    267 		solve();
    268 	}
    269 }
    270 ```
    271 
    272 **Rate the problem**
    273 
    274 * Amazing problem:
    275 * Good problem:
    276 * Average problem:
    277 * Bad problem:
    278 * Didn't solve:
    279 
    280 [1868B2 - Candy Party (Hard Version)](/contest/1868/problem/B2 "Codeforces Round 896 (Div. 1)")
    281 
    282 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan")  
    283 Please, read the tutorial for B1 first.
    284 
    285 **Hint 4**
    286 
    287 For whom may not give or receive candies?
    288 
    289 **Hint 5**
    290 
    291 When $|a_i-s|$ is a power of $2$, how many ways can the person gives/receives candies at most?
    292 
    293 **Hint 6**
    294 
    295 Try to determine some people's way to give/receive candies first, then others.
    296 
    297 **How to do this?**
    298 
    299 Bit-by-bit.
    300 
    301 **Solution**
    302 
    303 Tutorial is loading...
    304 
    305 **Implementation**
    306 
    307 ```
    308 #include <bits/stdc++.h>
    309 #define all(s) s.begin(), s.end()
    310 using namespace std;
    311 using ll = long long;
    312 using ull = unsigned long long;
    313 
    314 const int _N = 1e5 + 5;
    315 
    316 int T;
    317 
    318 void solve() {
    319 	int n; cin >> n;
    320 	vector<ll> a(n); ll sum = 0;
    321 	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
    322 	if (sum % n) return cout << "No" << '\n', void();
    323 	sum /= n;
    324 	vector<int> bit(31, 0), pow1(31, 0), pow2(31, 0);
    325 	for (int i = 0; i < n; i++) {
    326 		int flag = 0;
    327 		if (a[i] == sum) continue;
    328 		for (int j = 0; j < 31; j++) {
    329 			if (a[i] + (1 << j) == sum) {
    330 				pow1[j]++;
    331 				flag = 1;
    332 				continue;
    333 			}
    334 			if (a[i] - (1 << j) == sum) {
    335 				pow2[j]++;
    336 				flag = 1;
    337 				continue;
    338 			}
    339 		}
    340 		if (flag) continue;
    341 		flag = 0;
    342 		for (int j = 0; j < 31; j++) {
    343 			for (int k = 0; k < 31; k++) {
    344 			    if (a[i] + (1 << j) - (1 << k) == sum) {
    345 			        flag = 1;
    346 			        bit[j]++;
    347 			        bit[k]--;
    348 			    }
    349 			}
    350 		}
    351 		if (!flag) {
    352 			cout << "No" << '\n';
    353 			return;
    354 		}
    355 	}
    356 	for (int i = 30; i >= 0; i--) {
    357 		bit[i] += (pow1[i] - pow2[i]);
    358 		if (i == 0) break;
    359 		if (bit[i] < 0) {
    360 			pow1[i - 1] -= -bit[i];
    361 			bit[i - 1] -= -bit[i];
    362 			if (pow1[i - 1] < 0) {
    363 				cout << "No" << '\n';
    364 				return;
    365 			}
    366 		} else {
    367 			pow2[i - 1] -= bit[i];
    368 			bit[i - 1] += bit[i];
    369 			if (pow2[i - 1] < 0) {
    370 				cout << "No" << '\n';
    371 				return;
    372 			}
    373 		}
    374 	}
    375 	if (bit[0] == 0) cout << "Yes" << '\n';
    376 	else cout << "No" << '\n';
    377 	return;
    378 }
    379 
    380 int main() {
    381 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    382 	cin >> T;
    383 	while (T--) {
    384 		solve();
    385 	}
    386 }
    387 ```
    388 
    389 **Rate the problem**
    390 
    391 * Amazing problem:
    392 * Good problem:
    393 * Average problem:
    394 * Bad problem:
    395 * Didn't solve:
    396 
    397 [1868C - Travel Plan](/contest/1868/problem/C "Codeforces Round 896 (Div. 1)")
    398 
    399 Author: [programpiggy](/profile/programpiggy "Expert programpiggy")
    400 
    401 **Hint 1**
    402 
    403 For any simple path length $t$, what's the sum of the maximum value of cities in all assignments? For the cities out of the path, their value doesn't matter.
    404 
    405 **Hint 2**
    406 
    407 Consider an easy dp to calculate the number of paths with different lengths.
    408 
    409 **Hint 3**
    410 
    411 How many different subtrees are there in this tree?
    412 
    413 **Hint 4**
    414 
    415 What's the maximum length of the paths?
    416 
    417 **Hint 5**
    418 
    419 Try to optimize the dp with the conclusion you get in Hint 3 and Hint 4.
    420 
    421 **Solution**
    422 
    423 Tutorial is loading...
    424 
    425 $\mathcal O(\sum(m\log n+\log^3n))$ solution by [programpiggy](/profile/programpiggy "Expert programpiggy"):
    426 
    427 **Implementation**
    428 
    429 ```
    430 #include <bits/stdc++.h>
    431 #define ll long long
    432 #define ull unsigned long long
    433 using namespace std;
    434 #pragma GCC optimize("Ofast")
    435 
    436 ll tot[505],n,m,dp[125][125],dp2[125],g[125][125],g2[125],f[125],pw[100005][125];
    437 const ll mod=998244353;
    438 
    439 inline ll dep( ll root) {
    440 	if (root>n)return 0;
    441 	return dep(root*2)+1;
    442 }
    443 
    444 inline ll dep2( ll root) {
    445 	if (root>n)return 0;
    446 	return dep2(root*2+1)+1;
    447 }
    448 
    449 inline bool full( ll root) {
    450 	return dep(root)==dep2(root);
    451 }
    452 
    453 void dfs( ll root) {
    454 	if (root*2>n) {
    455 		g2[0]=dp2[0]=1;
    456 		return;
    457 	}
    458 	if (root*2==n) {
    459 		g2[0]=2,g2[1]=1;
    460 		dp2[0]=1,dp2[1]=1;
    461 		return;
    462 	}
    463 	ll d=0;
    464 	if (full(root*2)) {
    465 
    466 		d=dep(root*2);
    467 		dfs(root*2+1);
    468 	} else {
    469 		d=dep(root*2+1);
    470 		dfs(root*2);
    471 	}
    472 	ll mx=2*d+4;
    473 	for (ll i=0; i<=mx; i++) {
    474 		g2[i]+=g[d][i];
    475 		for (ll j=0; j<=min(d+2,i); j++) {
    476 			g2[i+2]+=dp2[j]*dp[d][i-j]%mod;
    477 		}
    478 	}
    479 	for (ll i=mx; i>0; i--)dp2[i]=(dp2[i-1]+dp[d][i-1])%mod;
    480 	dp2[0]=1;
    481 	for (ll i=0; i<=mx; i++)g2[i]+=dp2[i],g2[i]%=mod;
    482 }
    483 
    484 inline ll qkp(ll a,ll k) {
    485 	ll ans=1;
    486 	while (k) {
    487 		if (k&1)ans*=a,ans%=mod;
    488 		a*=a,a%=mod;
    489 		k>>=1;
    490 	}
    491 	return ans;
    492 }
    493 
    494 int main() {
    495 	ll t;
    496 	scanf("%lld",&t);
    497 	for (ll i=1; i<=60; i++) {
    498 			dp[i][0]=1;
    499 			for (ll j=1; j<=i-1; j++) {
    500 				dp[i][j]=2*dp[i-1][j-1]%mod;
    501 			}
    502 			for (ll j=0; j<=2*i-2; j++) {
    503 				g[i][j]+=g[i-1][j]*2;
    504 				g[i][j]+=dp[i][j];
    505 				g[i][j]%=mod;
    506 				for (ll k=0; k<=j; k++) {
    507 					g[i][j+2]+=dp[i-1][k]*dp[i-1][j-k]%mod;
    508 					g[i][j+2]%=mod;
    509 				}
    510 			}
    511 		}
    512 	while (t--) {
    513 		scanf("%lld%lld",&n,&m);
    514 		
    515 		// log n^3
    516 		dfs(1);
    517 		ll d=dep(1),ans=0;
    518 		for (ll j=0; j<=m; j++) {
    519 			pw[j][0]=1;
    520 			for (ll i=1; i<=2*d; i++) {
    521 				pw[j][i]=pw[j][i-1]*j%mod;
    522 			}
    523 		}
    524 
    525 		for (ll i=0; i<=2*d-2; i++) {
    526 			for (ll j=1; j<=m; j++) {
    527 				f[i]+=(pw[j][i+2]+mod-pw[j-1][i+1]*j%mod)%mod;
    528 				f[i]%=mod;
    529 			}
    530 			if (n>=i+1)
    531 				ans+=f[i]*g2[i]%mod*qkp(m,n-i-1)%mod;
    532 			ans%=mod;
    533 		}
    534 		printf("%lld\n",ans);
    535 		for (ll i=1;i<=60;i++){
    536 			for (ll j=0;j<=2*i-2;j++){
    537 				f[j]=g2[j]=dp2[j]=0;
    538 			}
    539 		}
    540 	}
    541 
    542 	return 0;
    543 }
    544 ```
    545 
    546 $\mathcal O(\sum \log^3n)$ solution by [sszcdjr](/profile/sszcdjr "Master sszcdjr"):
    547 
    548 **Implementation**
    549 
    550 ```
    551 #include <bits/stdc++.h>
    552 #define int long long
    553 #define double long double
    554 #define mid ((l+r)>>1)
    555 using namespace std;
    556 const int mod=998244353;
    557 int qp(int a,int b){
    558 	int ans=1;
    559 	while(b){
    560 		if(b&1) ans=(ans*a)%mod;
    561 		a=(a*a)%mod;
    562 		b>>=1;
    563 	}
    564 	return ans;
    565 }
    566 int fac[1000005],inv[1000005];
    567 void init(){
    568 	fac[0]=1;
    569 	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
    570 	inv[1000000]=qp(fac[1000000],mod-2);
    571 	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    572 }
    573 int C(int i,int j){
    574 	if(i<0||j<0||i<j) return 0;
    575 	return fac[i]*inv[i-j]%mod*inv[j]%mod;
    576 }
    577 int cnt=0;
    578 int reg[100005][131],reg2[100005][131];
    579 unordered_map<int,int> mp;
    580 void dfs(int now){
    581 	if(mp[now]) return ;
    582 	mp[now]=++cnt;
    583 	if(now==0) return ;
    584 	reg[cnt][0]++,reg2[cnt][0]++;
    585 	if(now==1) return ;
    586 	int i=0;
    587 	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
    588 	i-=2;
    589 	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
    590 	if(lft<=(1LL<<i)) lnum+=lft;
    591 	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
    592 	dfs(lnum),dfs(rnum);
    593 	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
    594 	for(int i=0;i<=130;i++){
    595 		for(int j=0;j<=130;j++){
    596 			if(i+j+2>=130) break;
    597 			(reg2[mn][i+j+2]+=(reg[ml][i]*reg[mr][j]))%=mod; 
    598 		}
    599 	}
    600 	for(int i=0;i<=129;i++) (reg[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i]+=reg2[ml][i]+reg2[mr][i])%=mod;
    601 }
    602 int pw[100005][150],tot[205];
    603 signed main(){
    604 	init();
    605 	int t; cin>>t;
    606 	while(t--){
    607 		int n,m;
    608 		cin>>n>>m;
    609 		dfs(n);
    610 		int nn=mp[n];
    611 		int ans=0;
    612 		tot[0]=(m-1)%mod;
    613 		for(int i=2;i<=135;i++){
    614 			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
    615 			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
    616 		    (tot[i-1]*=qp(i,mod-2))%=mod;
    617 		}
    618 		for(int i=0;i<=min(130ll,n-1);i++){
    619 			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
    620 			(ans+=tmp*reg2[nn][i]%mod*qp(m%mod,n-(i+1)))%=mod;
    621 		}
    622 		cout<<ans<<"\n";
    623 	}
    624 	return 0;
    625 }
    626 ```
    627 
    628 $\mathcal O(\sum \log^2n)$ solution by [sszcdjr](/profile/sszcdjr "Master sszcdjr"):
    629 
    630 **Implementation**
    631 
    632 ```
    633 #include <bits/stdc++.h>
    634 #define int long long
    635 #define double long double
    636 #define mid ((l+r)>>1)
    637 using namespace std;
    638 const int mod=998244353;
    639 int qp(int a,int b){
    640 	int ans=1;
    641 	while(b){
    642 		if(b&1) ans=(ans*a)%mod;
    643 		a=(a*a)%mod;
    644 		b>>=1;
    645 	}
    646 	return ans;
    647 }
    648 int fac[1000005],inv[1000005];
    649 void init(){
    650 	fac[0]=1;
    651 	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
    652 	inv[1000000]=qp(fac[1000000],mod-2);
    653 	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    654 }
    655 int C(int i,int j){
    656 	if(i<0||j<0||i<j) return 0;
    657 	return fac[i]*inv[i-j]%mod*inv[j]%mod;
    658 }
    659 int cnt=0;
    660 int reg[100005][131],dep[100005],depc[100005],rett[131],invi[131];
    661 unordered_map<int,int> mp;
    662 void dfs(int now){
    663 	if(mp[now]) return ;
    664 	mp[now]=++cnt;
    665 	if(now==0) return ;
    666 	dep[cnt]=1,depc[cnt]=1,reg[cnt][0]++;
    667 	if(now==1) return ;
    668 	int i=0;
    669 	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
    670 	i-=2;
    671 	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
    672 	if(lft<=(1LL<<i)) lnum+=lft;
    673 	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
    674 	dfs(lnum),dfs(rnum);
    675 	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
    676 	if(dep[ml]>dep[mr]){
    677 		dep[mn]=dep[ml]+1; depc[mn]=depc[ml];
    678 		for(int i=0;i<=129;i++) reg[mn][i]=reg[ml][i];
    679 	}
    680 	else{
    681 		dep[mn]=dep[ml]+1; depc[mn]=(depc[ml]+depc[mr])%mod;
    682 		for(int i=0;i<=129;i++) reg[mn][i]=(reg[ml][i]+reg[mr][i])%mod;
    683 		(reg[mn][dep[mn]*2-2]+=depc[ml]*depc[mr])%=mod;
    684 	}
    685 }
    686 int pw[100005][150],tot[205],pw2[135];
    687 signed main(){
    688 	pw2[0]=1;
    689 	for(int i=1;i<=130;i++) pw2[i]=pw2[i-1]*2%mod,invi[i]=qp(i,mod-2);
    690 	init();
    691 	int t; cin>>t;
    692 	while(t--){
    693 		int n,m;
    694 		cin>>n>>m;
    695 		int lg=0,lft;
    696 		for(int i=0;i<=130;i++) rett[i]=0;
    697 		for(lg=61;lg>=0;lg--){
    698 			if(n>=(1LL<<(lg+1))-1){
    699 				lft=n-((1LL<<(lg+1))-1);
    700 				lft%=mod;
    701 				break;
    702 			}
    703 		}
    704 		for(int i=0;i<=lg;i++){
    705 			for(int j=0;j<=lg;j++){
    706 				int tt=max(i,j);
    707 				(rett[i+j]+=(pw2[lg-tt+1]-1)*pw2[max(0ll,i-1)+max(0ll,j-1)]%mod)%=mod;
    708 			}
    709 		}
    710 		for(int i=1;i<=lg+1;i++){
    711 			for(int j=0;j<i;j++){
    712 				(rett[i+j]+=lft*pw2[max(0ll,j-1)]%mod)%=mod;
    713 			}
    714 		}
    715 		dfs(n);
    716 		int nn=mp[n];
    717 		if(n!=(1ll<<(lg+1))-1) for(int i=0;i<=130;i++) (rett[i]+=reg[nn][i])%=mod;
    718 		int ans=0;
    719 		tot[0]=(m-1)%mod;
    720 		for(int i=2;i<=130;i++){
    721 			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
    722 			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
    723 		    (tot[i-1]*=invi[i])%=mod;
    724 		}
    725 		for(int i=0;i<=min(130ll,n-1);i++){
    726 			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
    727 			(ans+=tmp*rett[i]%mod*qp(m%mod,n-(i+1)))%=mod;
    728 		}
    729 		cout<<ans<<"\n";
    730 	}
    731 	return 0;
    732 }
    733 ```
    734 
    735 $\mathcal O(\sum m\log n)$ solution by [ling_luo](/profile/ling_luo "Grandmaster ling_luo"):
    736 
    737 **Implementation**
    738 
    739 ```
    740 #include <bits/stdc++.h>
    741 #define rep(i,n) for(int i=0,_##i##__end=(n);i<_##i##__end;++i)
    742 #define rep1(i,n) for(int i=1,_##i##__end=(n);i<=_##i##__end;++i)
    743 #define mp make_pair
    744 #define fi first
    745 #define se second
    746 typedef long long ll;
    747 using namespace std;
    748 const ll mod1=998244353;
    749 int t;
    750 ll n;
    751 int m;
    752 ll qkpw(ll a,ll b)
    753 {
    754 	ll ret=1;
    755 	while(b)
    756 	{
    757 		if(b&1) ret=ret*a%mod1;
    758 		a=a*a%mod1;
    759 		b>>=1;
    760 	}
    761 	return ret;
    762 }
    763 ll val_full[114];
    764 ll val_link[114];
    765 pair<ll,ll> realget(ll P,unsigned long long c)
    766 {
    767 	if((c&(c+1))==0)
    768 	return mp(val_link[bit_width(c)-1],val_full[bit_width(c)-1]);
    769 	if(c==2)
    770 	return mp((P*P+P)%mod1,(P*P+P+P)%mod1);
    771 	if(c&(bit_floor(c)>>1))
    772 	{
    773 		pair<ll,ll> A=realget(P,bit_floor(c)-1),B=realget(P,c-bit_floor(c));
    774 		return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
    775 	}
    776 	pair<ll,ll> A=realget(P,c-(bit_floor(c)>>1)),B=realget(P,(bit_floor(c)>>1)-1);
    777 	return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
    778 }
    779 ll get_value(ll P,ll c)
    780 {
    781 	val_full[0]=P;val_link[0]=P;
    782 	rep1(i,64)
    783 	{
    784 		val_full[i]=(val_full[i-1]*2+(1+val_link[i-1])*(1+val_link[i-1])%mod1*P)%mod1;
    785 		val_link[i]=((val_link[i-1]*2+1)*P)%mod1;
    786 	}
    787 	return realget(P,c).second;
    788 }
    789 void Q()
    790 {
    791 	cin>>n>>m;
    792 	ll cur=((n%mod1)*(n%mod1+1)/2%mod1)*qkpw(m,n+1)%mod1;
    793 	ll INV_M=qkpw(m,mod1-2);
    794 	rep(i,m) cur=(cur-qkpw(m,n)*get_value(i*INV_M%mod1,n)%mod1+mod1)%mod1;
    795 	cout<<cur<<endl;
    796 }
    797 int main()
    798 {
    799 	cin>>t;while(t--)Q();
    800 }
    801 ```
    802 
    803 **Rate the problem**
    804 
    805 * Amazing problem:
    806 * Good problem:
    807 * Average problem:
    808 * Bad problem:
    809 * Didn't solve:
    810 
    811 [1868D - Flower-like Pseudotree](/contest/1868/problem/D "Codeforces Round 896 (Div. 1)")
    812 
    813 Author: [sszcdjr](/profile/sszcdjr "Master sszcdjr")
    814 
    815 **Hint 1**
    816 
    817 In fact, vertices with degree $1$ are useless, let's first ignore them. It's easy to see that when $\sum_{i=1}^nd_i=2n$, we can simply hang them under the vertices which haven't reached their degree limit.
    818 
    819 **Hint 2**
    820 
    821 In most cases, we can simply put two vertices on the cycle.
    822 
    823 **Hint 3**
    824 
    825 Sort $d_i$ from the largest to the smallest. Can we construct a flower-like psuedotree when $d_1=2$? Can we construct a flower-like psuedotree when $d_1\neq 2$ and $d_2=2$?
    826 
    827 **Hint 4**
    828 
    829 Can you find an easy way to construct the flower-like psuedotree when the number of $d_i \gt 1$ is even?
    830 
    831 **Hint 5**
    832 
    833 Try to extend the solution when the number of $d_i \gt 1$ is even to the odd case. Note some corner cases.
    834 
    835 **Solution**
    836 
    837 Tutorial is loading...
    838 
    839 **Implementation**
    840 
    841 ```
    842 #include <bits/stdc++.h>
    843 #define int long long
    844 #define double long double
    845 using namespace std;
    846 struct node{
    847 	int d,pos;
    848 }a[1000005];
    849 bool cmp(node x,node y){
    850 	return x.d>y.d;
    851 }
    852 void pe(int x,int y){
    853 	cout<<a[x].pos<<" "<<a[y].pos<<"\n";
    854 }
    855 signed main(){
    856 	ios::sync_with_stdio(false);
    857 	cin.tie(0),cout.tie(0);
    858 	int t; cin>>t;
    859 	while(t--){
    860 		int n,tot=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].d,a[i].pos=i,tot+=a[i].d;
    861 		if(tot!=2*n){
    862 			cout<<"No\n"; continue;
    863 		}
    864 		if(n==1){
    865 			cout<<"No\n"; continue;
    866 		}
    867 		sort(a+1,a+n+1,cmp);
    868 		if(a[1].d==2){
    869 			cout<<"Yes\n";
    870 			for(int i=1;i<=n;i++) pe(i,i%n+1);
    871 			continue;
    872 		}
    873 		if(a[2].d==2){
    874 			cout<<"No\n"; continue;
    875 		}
    876 		int cntb=0;
    877 		for(int i=3;i<=n;i++) cntb+=(a[i].d>1);
    878 		int num[n+1]; for(int i=1;i<=n;i++) num[i]=a[i].d;
    879 		if(!(cntb&1)){
    880 			cout<<"Yes\n";
    881 			pe(1,2),pe(1,2);
    882 			num[1]-=2,num[2]-=2;
    883 			for(int i=3;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
    884 			int it=1;
    885 			for(int i=cntb+3;i<=n;i++){
    886 				while(!num[it]) it++;
    887 				num[it]--,pe(i,it);
    888 			}
    889 			continue;
    890 		}
    891 		if(a[1].d==3){
    892 			if(a[3].d==2){
    893 				cout<<"No\n"; continue;
    894 			}
    895 			if(cntb==1){
    896 				cout<<"Yes\n";
    897 				pe(1,2),pe(2,3),pe(3,1);
    898 				pe(1,4),pe(2,5),pe(3,6);
    899 				continue;
    900 			}
    901 			if(a[5].d==2&&cntb==3){
    902 				cout<<"No\n"; continue;
    903 			}
    904 			if(cntb==3){
    905 				cout<<"Yes\n";
    906 				pe(1,2),pe(2,3),pe(3,4),pe(4,5),pe(5,1);
    907 				pe(1,6),pe(2,7),pe(3,8),pe(4,9),pe(5,10);
    908 				continue;
    909 			}
    910 			cout<<"Yes\n";
    911 			pe(1,2),pe(1,2),pe(1,3),pe(2,4),pe(3,5),pe(3,6),pe(4,7);
    912 			num[1]-=3,num[2]-=3,num[3]-=3,num[4]-=2,num[5]--,num[6]--,num[7]--;
    913 			for(int i=8;i<=cntb+2;i++) pe(i-2,i),num[i]--,num[i-2]--;
    914 			int it=1;
    915 			for(int i=cntb+3;i<=n;i++){
    916 				while(!num[it]) it++;
    917 				num[it]--,pe(i,it);
    918 			}
    919 			continue;
    920 		}
    921 		else{
    922 			if(a[3].d==2&&cntb==1){
    923 				cout<<"No\n"; continue;
    924 			}
    925 			if(cntb==1){
    926 				cout<<"Yes\n";
    927 				pe(1,2),pe(2,3),pe(3,1);
    928 				num[1]-=2,num[2]-=2,num[3]-=2;
    929 				int it=1;
    930 				for(int i=4;i<=n;i++){
    931 					while(!num[it]) it++;
    932 					num[it]--,pe(i,it);
    933 				}
    934 				continue;
    935 			}
    936 			cout<<"Yes\n";
    937 			pe(1,2),pe(1,2),pe(1,3),pe(1,4),pe(2,5);
    938 			num[1]-=4,num[2]-=3,num[3]-=1,num[4]-=1,num[5]-=1;
    939 			for(int i=6;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
    940 			int it=1;
    941 			for(int i=cntb+3;i<=n;i++){
    942 				while(!num[it]) it++;
    943 				num[it]--,pe(i,it);
    944 			}
    945 			continue;
    946 		}
    947 	}
    948 	return 0;
    949 }
    950 ```
    951 
    952 **Rate the problem**
    953 
    954 * Amazing problem:
    955 * Good problem:
    956 * Average problem:
    957 * Bad problem:
    958 * Didn't solve:
    959 
    960 [1868E - Min-Sum-Max](/contest/1868/problem/E "Codeforces Round 896 (Div. 1)")
    961 
    962 Author: [duck_pear](/profile/duck_pear "Master duck_pear")  
    963 Huge thanks to [Kubic](/profile/Kubic "International Grandmaster Kubic") for the development of this problem!
    964 
    965 **Hint 1**
    966 
    967 Consider this problem on the prefix sum array.
    968 
    969 **Hint 2**
    970 
    971 Try to make some observations about the prefix sum array. Consider dp.
    972 
    973 **Hint 3**
    974 
    975 Go for a slow solution first, for example, $\mathcal{O}(n^6)$ or $\mathcal{O}(n^4)$.
    976 
    977 **Hint 4**
    978 
    979 The last step is to optimize your dp to $\mathcal{O}(n^3)$. :)
    980 
    981 **Fun Fact**
    982 
    983 $\mathcal{O}(n^6)$ can pass $n\le 100$ easily so we have to raise the limit for $\sum n$ to $1~000$.
    984 
    985 **Solution**
    986 
    987 Tutorial is loading...
    988 
    989 **Implementation (by Artyom123)**
    990 
    991 ```
    992 #include <iostream>
    993 #include <vector>
    994 #include <string>
    995 #include <algorithm>
    996 #include <set>
    997 #include <map>
    998 #include <math.h>
    999 #include <iomanip>
   1000 #include <bitset>
   1001 #include <random>
   1002 #include <ctime>
   1003 #include <string_view>
   1004 #include <queue>
   1005 #include <cassert>
   1006 
   1007 using namespace std;
   1008 
   1009 #define fi first
   1010 #define se second
   1011 #define all(x) (x).begin(), (x).end()
   1012 #define pb emplace_back
   1013 #define ll long long
   1014 #define mp make_pair
   1015 #define pii pair<int, int>
   1016 #define ld long double
   1017 
   1018 const int INF = 1e9 + 1;
   1019 const ll INFLL = 1e18;
   1020 
   1021 bool contains(ll x, ll l, ll r) {
   1022     return (x >= l) && (x <= r);
   1023 }
   1024 
   1025 void solve() {
   1026     int n;
   1027     cin >> n;
   1028     vector<ll> a(n + 1);
   1029     for (int i = 1; i <= n; i++) cin >> a[i];
   1030     if (n == 1) {
   1031         cout << 1 << "\n";
   1032         return;
   1033     }
   1034     vector<ll> pr(n + 1);
   1035     for (int i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i + 1];
   1036     vector<vector<vector<int>>> dp_leftmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
   1037     vector<vector<vector<int>>> dp_leftmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
   1038     vector<vector<vector<int>>> dp_rightmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
   1039     vector<vector<vector<int>>> dp_rightmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
   1040     vector<pair<ll, int>> b(n + 1);
   1041     for (int i = 0; i <= n; i++) b[i] = mp(pr[i], i);
   1042     sort(all(b));
   1043     vector<vector<int>> next_left(n + 1, vector<int>(n + 1, -1));
   1044     vector<vector<int>> next_right(n + 1, vector<int>(n + 1, -1));
   1045     for (int i = 0; i <= n; i++) {
   1046         int prev = -1;
   1047         for (int j = 0; j <= n; j++) {
   1048             next_left[i][j] = prev;
   1049             if (pr[j] == pr[i]) prev = j;
   1050         }
   1051         prev = n + 1;
   1052         for (int j = n; j >= 0; j--) {
   1053             next_right[i][j] = prev;
   1054             if (pr[j] == pr[i]) prev = j;
   1055         }
   1056     }
   1057     for (int len = 0; len <= n; len++) {
   1058         for (int i = 0; i <= n && i + len <= n; i++) {
   1059             int j = i + len;
   1060             for (int k = 0; k <= n; k++) {
   1061                 if (contains(pr[i], pr[i], pr[k]) && contains(pr[j], pr[i], pr[k])) dp_leftmin[i][j][k] = min(len, 1);
   1062                 if (contains(pr[i], pr[k], pr[i]) && contains(pr[j], pr[k], pr[i])) dp_leftmax[i][j][k] = min(len, 1);
   1063                 if (contains(pr[i], pr[j], pr[k]) && contains(pr[j], pr[j], pr[k])) dp_rightmin[i][j][k] = min(len, 1);
   1064                 if (contains(pr[i], pr[k], pr[j]) && contains(pr[j], pr[k], pr[j])) dp_rightmax[i][j][k] = min(len, 1);
   1065             }
   1066             if (len <= 1) continue;
   1067             for (int x = i; x <= j; x++) {
   1068                 if (next_left[i][x] >= i) {
   1069                     int y = next_left[i][x];
   1070                     if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][y][x] + dp_leftmax[x][j][i] + 1);
   1071                     if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][y][x] + dp_leftmin[x][j][i] + 1);
   1072                 }
   1073                 if (next_left[j][x] >= i) {
   1074                     int y = next_left[j][x];
   1075                     if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[x][j][x] + dp_rightmin[i][y][x] + 1);
   1076                     if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[x][j][x] + dp_rightmax[i][y][x] + 1);
   1077                 }
   1078                 if (next_right[i][x] <= j) {
   1079                     int y = next_right[i][x];
   1080                     if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][x][x] + dp_leftmin[y][j][x] + 1);
   1081                     if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][x][x] + dp_leftmax[y][j][x] + 1);
   1082                 }
   1083                 if (next_right[j][x] <= j) {
   1084                     int y = next_right[j][x];
   1085                     if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[y][j][x] + dp_rightmax[i][x][j] + 1);
   1086                     if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[y][j][x] + dp_rightmin[i][x][j] + 1);
   1087                 }
   1088             }
   1089             int mx_left = -INF;
   1090             int mx_right = -INF;
   1091             for (int k = 0; k <= n; k++) {
   1092                 int p = k;
   1093                 while (p <= n && b[p].fi == b[k].fi) {
   1094                     mx_left = max(mx_left, dp_leftmin[i][j][b[p].se]);
   1095                     mx_right = max(mx_right, dp_rightmin[i][j][b[p].se]);
   1096                     p++;
   1097                 }
   1098                 for (int l = k; l < p; l++) {
   1099                     dp_leftmin[i][j][b[l].se] = mx_left;
   1100                     dp_rightmin[i][j][b[l].se] = mx_right;
   1101                 }
   1102                 k = p - 1;
   1103             }
   1104             mx_left = -INF;
   1105             mx_right = -INF;
   1106             for (int k = n; k >= 0; k--) {
   1107                 int p = k;
   1108                 while (p >= 0 && b[p].fi == b[k].fi) {
   1109                     mx_left = max(mx_left, dp_leftmax[i][j][b[p].se]);
   1110                     mx_right = max(mx_right, dp_rightmax[i][j][b[p].se]);
   1111                     p--;
   1112                 }
   1113                 for (int l = k; l > p; l--) {
   1114                     dp_leftmax[i][j][b[l].se] = mx_left;
   1115                     dp_rightmax[i][j][b[l].se] = mx_right;
   1116                 }
   1117                 k = p + 1;
   1118             }
   1119         }
   1120     }
   1121     int ans = -INF;
   1122     ans = max(ans, dp_leftmin[0][n][n]);
   1123     ans = max(ans, dp_leftmax[0][n][n]);
   1124     for (int x = 0; x <= n; x++) {
   1125         for (int y = x + 1; y <= n; y++) {
   1126             ans = max(ans, dp_rightmin[0][x][y] + dp_leftmax[y][n][x] + 1);
   1127             ans = max(ans, dp_rightmax[0][x][y] + dp_leftmin[y][n][x] + 1);
   1128         }
   1129     }
   1130     cout << ans << "\n";
   1131 }
   1132 
   1133 int main() {
   1134     #ifdef LOCAL
   1135         freopen("input", "r", stdin);
   1136         freopen("output", "w", stdout);
   1137     #else 
   1138         ios_base::sync_with_stdio(0);
   1139         cin.tie(0);
   1140         cout.tie(0);
   1141     #endif
   1142     int t;
   1143     cin >> t;
   1144     while (t--) {
   1145         solve();
   1146     }
   1147     return 0;
   1148 }
   1149 ```
   1150 
   1151 **Rate the problem**
   1152 
   1153 * Amazing problem:
   1154 * Good problem:
   1155 * Average problem:
   1156 * Bad problem:
   1157 * Didn't solve:
   1158 
   1159 [1868F - LIS?](/contest/1868/problem/F "Codeforces Round 896 (Div. 1)")
   1160 
   1161 Author: [Error_Yuan](/profile/Error_Yuan "Candidate Master Error_Yuan")
   1162 
   1163 **Hint 1**
   1164 
   1165 Greedy.
   1166 
   1167 **Hint 2**
   1168 
   1169 This problem is somehow related to geometry.
   1170 
   1171 **Hint 3**
   1172 
   1173 What structure will the intervals you choose each time form?
   1174 
   1175 **Solution**
   1176 
   1177 Tutorial is loading...
   1178 
   1179 **Implementation**
   1180 
   1181 ```
   1182 #include <bits/stdc++.h>
   1183 #define all(s) s.begin(), s.end()
   1184 using namespace std;
   1185 using ll = long long;
   1186 using ull = unsigned long long;
   1187 using point = pair<ll, ll>;
   1188 
   1189 const int _N = 5e5 + 5;
   1190 
   1191 int n;
   1192 ll a[_N], pre[_N], suf[_N], ans;
   1193 struct interval{
   1194 	int l, r; 
   1195 	ll d, dneed;
   1196 	int type, pos; // type0 - l, type1 - r
   1197 };
   1198 struct cmp{
   1199 	bool operator () (const interval &a, const interval &b) {
   1200 		return a.dneed - a.d > b.dneed - b.d;
   1201 	}
   1202 };
   1203 
   1204 ll ceildiv(ll a, ll b) {
   1205 	// return a/b;
   1206 	if (a * b > 0) return a / b;
   1207 	else return a / b - !!(a % b);
   1208 }
   1209 
   1210 namespace sg_left{ // [l, r] -> hull of point l-1 to r-1
   1211 	vector<int> hull[_N << 2];
   1212 	point pt[_N];
   1213 	void get_hull(int p, int l, int r) {
   1214 		int head = 0, tail = -1;
   1215 		for (int i = l; i <= r; i++) {
   1216 			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) <= (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
   1217 				tail--;
   1218 				hull[p].pop_back();
   1219 			}
   1220 			tail++;
   1221 			hull[p].emplace_back(i);
   1222 		}
   1223 	}
   1224 	void build(int p, int l, int r) {
   1225 		get_hull(p, l - 1, r - 1);
   1226 		if (l == r) return;
   1227 		int mid = (l + r) >> 1;
   1228 		build(p * 2, l, mid);
   1229 		build(p * 2 + 1, mid + 1, r);
   1230 	}
   1231 	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
   1232 		if (l >= L && r <= R) { // do ternary search
   1233 			int tl = 1, tr = hull[p].size();
   1234 			while (tl < tr) {
   1235 				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
   1236 				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
   1237 				if ((o.second - p1.second) * (o.first - p2.first) >= (o.second - p2.second) * (o.first - p1.first)) {
   1238 					tl = m1 + 1;
   1239 				} else tr = m2 - 1;
   1240 			}
   1241 			return {ceildiv((o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] + 1};
   1242 		}
   1243 		int mid = (l + r) >> 1;
   1244 		pair<int, int> res = {-1, -1};
   1245 		if (L <= mid) {
   1246 			res = query(p * 2, l, mid, L, R, o);
   1247 		} 
   1248 		if (R > mid) {
   1249 			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
   1250 			if (res == make_pair(-1, -1)) return res2;
   1251 			else {
   1252 				if (res2.first <= res.first) {
   1253 					return res2;
   1254 				} else return res;
   1255 			}
   1256 		}
   1257 		return res;
   1258 	}
   1259 	void test() {
   1260 		auto res = query(1, 1, n, 1, n, pt[n]);
   1261 		cout << res.first << ' ' << res.second << '\n';
   1262 	}
   1263 };
   1264 namespace sg_right{ // [l, r] -> hull of point l+1 to r+1
   1265 	vector<int> hull[_N << 2];
   1266 	point pt[_N];
   1267 	void get_hull(int p, int l, int r) {
   1268 		int head = 0, tail = -1;
   1269 		for (int i = l; i <= r; i++) {
   1270 			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) < (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
   1271 				tail--;
   1272 				hull[p].pop_back();
   1273 			}
   1274 			tail++;
   1275 			hull[p].emplace_back(i);
   1276 		}
   1277 	}
   1278 	void build(int p, int l, int r) {
   1279 		get_hull(p, l + 1, r + 1);
   1280 		if (l == r) return;
   1281 		int mid = (l + r) >> 1;
   1282 		build(p * 2, l, mid);
   1283 		build(p * 2 + 1, mid + 1, r);
   1284 	}
   1285 	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
   1286 		if (l >= L && r <= R) { // do ternary search
   1287 			int tl = 1, tr = hull[p].size();
   1288 			while (tl < tr) {
   1289 				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
   1290 				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
   1291 				if ((o.second - p1.second) * (o.first - p2.first) <= (o.second - p2.second) * (o.first - p1.first)) {
   1292 					tl = m1 + 1;
   1293 				} else tr = m2 - 1;
   1294 			}
   1295 			return {ceildiv(-(o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] - 1};
   1296 		}
   1297 		int mid = (l + r) >> 1;
   1298 		pair<int, int> res = {-1, -1};
   1299 		if (L <= mid) {
   1300 			res = query(p * 2, l, mid, L, R, o);
   1301 		} 
   1302 		if (R > mid) {
   1303 			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
   1304 			if (res == make_pair(-1, -1)) return res2;
   1305 			else {
   1306 				if (res.first <= res2.first) {
   1307 					return res;
   1308 				} else return res2;
   1309 			}
   1310 		}
   1311 		return res;
   1312 	}
   1313 	void test() {
   1314 		auto res = query(1, 1, n, 1, n, pt[1]);
   1315 		cout << res.first << ' ' << res.second << '\n';
   1316 	}
   1317 };
   1318 
   1319 int main() {
   1320 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
   1321 	cin >> n;
   1322 	for (int i = 1; i <= n; i++) cin >> a[i];
   1323 	if (n == 1) {
   1324 		cout << max(a[1] + 1, 0ll) << '\n';
   1325 		return 0;
   1326 	}
   1327 	sg_left::pt[0] = {0, 0}; sg_right::pt[n + 1] = {n + 1, 0};
   1328 	for (int i = 1; i <= n; i++) {
   1329 		pre[i] = pre[i - 1] + a[i];
   1330 		sg_left::pt[i] = {i, pre[i]};
   1331 	}
   1332 	for (int i = n; i >= 1; i--) {
   1333 		suf[i] = suf[i + 1] + a[i];
   1334 		sg_right::pt[i] = {i, suf[i]};
   1335 	}
   1336 	sg_left::build(1, 1, n);
   1337 	sg_right::build(1, 1, n);
   1338 	ll ans = 0;
   1339 	priority_queue<interval, vector<interval>, cmp> q;
   1340 	pair<int, int> resL = sg_left::query(1, 1, n, 1, n, sg_left::pt[n]);
   1341 	pair<int, int> resR = sg_right::query(1, 1, n, 1, n, sg_right::pt[1]);
   1342 	if (resL.second == 1) q.push({1, n, 0, resR.first + 1, 1, resR.second});
   1343 	else if (resR.second == n) q.push({1, n, 0, resL.first + 1, 0, resL.second});
   1344 	else if (resL.first <= resR.first) q.push({1, n, 0, resL.first + 1, 0, resL.second});
   1345 	else q.push({1, n, 0, resR.first + 1, 1, resR.second});
   1346 	while (!q.empty()) {
   1347 		auto x = q.top(); q.pop();
   1348 		if (x.d < x.dneed) {
   1349 			ans += x.dneed - x.d;
   1350 			x.d = x.dneed;
   1351 		}
   1352 		//split
   1353 		if (x.type == 1) x.pos++;
   1354 		int l = x.l, r = x.r;
   1355 		resL = sg_left::query(1, 1, n, l, x.pos - 1, sg_left::pt[x.pos - 1]);
   1356 		resR = sg_right::query(1, 1, n, l, x.pos - 1, sg_right::pt[l]);
   1357 		if (l == x.pos - 1) {
   1358 			ans += max(0ll, a[l] - x.d + 1);
   1359 		} else {
   1360 			if (resL.second == l) q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
   1361 			else if (resR.second == r) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
   1362 			else if (resL.first <= resR.first) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
   1363 			else q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
   1364 		}
   1365 		resL = sg_left::query(1, 1, n, x.pos, r, sg_left::pt[r]);
   1366 		resR = sg_right::query(1, 1, n, x.pos, r, sg_right::pt[x.pos]);
   1367 		if (x.pos == r) {
   1368 			ans += max(0ll, a[r] - x.d + 1);
   1369 		} else {
   1370 			if (resL.second == l) q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
   1371 			else if (resR.second == r)q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
   1372 			else if (resL.first < resR.first) q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
   1373 			else q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
   1374 		}
   1375 	}
   1376 	cout << ans << '\n';
   1377 }
   1378 ```
   1379 
   1380 **Bonus**
   1381 
   1382 Can you solve this problem in $\mathcal{O}(n\log n+n\log V)$ time complexity and $\mathcal{O}(n)$ space complexity?
   1383 
   1384 **Hint for Bonus**
   1385 
   1386 The solution has nothing to do with data structures.
   1387 
   1388 Bonus solution by [duck_pear](/profile/duck_pear "Master duck_pear"):
   1389 
   1390 **Implementation**
   1391 
   1392 ```
   1393 /*  
   1394   hmz is cute!
   1395 --------------------------------------------
   1396   You've got to have faith
   1397   Don't let them cut you down cut you down once more
   1398 */
   1399 //#pragma GCC optimize("Ofast,no-stack-protector")
   1400 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
   1401 #include<bits/stdc++.h>
   1402 using namespace std;
   1403 #define TY long long
   1404 #define IL inline
   1405 #define umap unordered_map
   1406 #define ull unsigned long long
   1407 #define pq priority_queue
   1408 #define mp make_pair
   1409 #define pb push_back
   1410 #define mod (TY)(1e9+7)
   1411 #define MAXN 500005
   1412 #define MAXM 200005
   1413 #define MAXK 27
   1414 #define INF (TY)(1e9)
   1415 #define block 300
   1416 #define For(i,a,b) for(TY i=(a);i<=(b);++i)
   1417 #define FOR(i,a,b) for(TY i=(a);i<(b);++i)
   1418 #define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
   1419 #define ROF(i,a,b) for(TY i=(a);i>(b);--i)
   1420 IL TY qr(){
   1421 	TY x=0,f=1;char op=getchar();
   1422 	for(;op<'0'||op>'9';op=getchar())if(op=='-')f=-1;
   1423 	for(;op>='0'&&op<='9';op=getchar())x=x*10+(op^48);
   1424 	return x*f;
   1425 }IL bool ischar(char op){
   1426 	if(op>='a'&&op<='z')return true;
   1427 	if(op>='A'&&op<='Z')return true;
   1428 	return false;
   1429 }IL char getc(){
   1430 	char op=getchar();
   1431 	while(!ischar(op))op=getchar();
   1432 	return op;
   1433 }IL string qs(){
   1434 	string op="";char u=getchar();
   1435 	while(!ischar(u))u=getchar();
   1436 	while(ischar(u))op+=u,u=getchar();
   1437 	return op;
   1438 }IL void qw(long long x){
   1439 	if(!x){putchar('0');return;}
   1440 	if(x<0)putchar('-'),x=-x;
   1441 	if(x>=10)qw(x/10);putchar(x%10+'0');
   1442 }IL void qw(long long x,char op){qw(x),putchar(op);}
   1443 IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
   1444 IL TY Ceil(TY a,TY b){return a/b+(a%b!=0);}
   1445 IL TY Mod(TY a){return (a>=mod?a-mod:a);}
   1446 IL TY Abs(TY a,TY b){return a>b?a-b:b-a;}
   1447 IL TY Pow(TY a,TY b){
   1448 	TY ans=1,base=a;
   1449 	while(b){
   1450 		if(b&1)ans=ans*base%mod;
   1451 		base=base*base%mod;b>>=1;
   1452 	}return ans;
   1453 }TY n,a[MAXN],b[MAXN],sum[MAXN],lenx[MAXN],leny[MAXN],ans;
   1454 vector<signed> e1[MAXN],e2[MAXN],HH;
   1455 TY Sum[MAXN],SSum[MAXN];
   1456 bool vis[MAXN];
   1457 signed L[MAXN],R[MAXN],LL[MAXN],RR[MAXN],ok[MAXN],nxtx[MAXN],nxty[MAXN];
   1458 struct node{TY l,r,tag,op;};queue<node> q;
   1459 IL void init(TY l,TY r,TY tag){
   1460     For(i,l,r)e1[i].clear(),e2[i].clear();
   1461     vector<pair<TY,TY> > pre,nxt;
   1462     For(i,l,r){
   1463         while(!pre.empty()){
   1464             TY ch=(pre.back().second*-1+tag)*(i-pre.back().first)+sum[i]-sum[pre.back().first];
   1465             if(ch<0){
   1466                 nxtx[pre.back().first]=i;
   1467                 pre.pop_back();continue;
   1468             }else{
   1469                 lenx[i]=pre.back().second+Ceil(ch+1,i-pre.back().first);
   1470                 pre.push_back({i,pre.back().second+Ceil(ch+1,i-pre.back().first)});
   1471                 break;
   1472             }
   1473         }if(pre.empty()){
   1474             lenx[i]=Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1);
   1475             pre.push_back({i,Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1)});
   1476         }
   1477     }while(!pre.empty())nxtx[pre.back().first]=r+1,pre.pop_back();
   1478     Rof(i,r,l){
   1479         while(!nxt.empty()){
   1480             TY ch=(nxt.back().second*-1+tag)*(nxt.back().first-i)-sum[i-1]+sum[nxt.back().first-1];
   1481             if(ch<0){
   1482                 nxty[nxt.back().first]=i;
   1483                 nxt.pop_back();continue;
   1484             }else{
   1485                 leny[i]=nxt.back().second+Ceil(ch+1,nxt.back().first-i);
   1486                 nxt.push_back({i,nxt.back().second+Ceil(ch+1,nxt.back().first-i)});
   1487                 break;
   1488             }
   1489         }if(nxt.empty()){
   1490             leny[i]=Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1);
   1491             nxt.push_back({i,Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1)});
   1492         }
   1493     }while(!nxt.empty())nxty[nxt.back().first]=l-1,nxt.pop_back();
   1494     For(i,l,r)if(nxtx[i]!=r+1)e1[nxtx[i]].pb(i);
   1495     Rof(i,r,l)if(nxty[i]!=l-1)e2[nxty[i]].pb(i);
   1496 }int main(){
   1497     //freopen("data.in","r",stdin);
   1498     /* init */
   1499     n=qr();For(i,1,n)a[i]=qr(),sum[i]=sum[i-1]+a[i];
   1500     q.push({1,n,0,0});
   1501     while(!q.empty()){
   1502         TY l=q.front().l,r=q.front().r,tag=q.front().tag,op=q.front().op;
   1503         if(l>r||l<=0||r>n)continue;
   1504         q.pop();
   1505         if(op==0){
   1506             vector<pair<TY,TY> > tmp;
   1507             TY c=0;TY lst=-1;
   1508             For(i,l,r)b[i]=a[i]+tag;
   1509             For(i,l,r){
   1510                 if((b[i]>=0)!=lst){
   1511                     lst=(b[i]>=0);
   1512                     ++c;L[c]=R[c]=i;
   1513                     Sum[c]=b[i];
   1514                 }else R[c]=i,Sum[c]+=b[i];
   1515             }For(i,1,c)LL[i]=i,RR[i]=i,SSum[i]=Sum[i],ok[i]=0,vis[i]=1;
   1516             Sum[c+1]=0;RR[c+1]=INF;
   1517             For(i,1,c)if(Sum[i]<0){
   1518                 ok[i]=(Sum[i-1]+Sum[i]>=0)+(Sum[i+1]+Sum[i]>=0);
   1519                 if(ok[i]==2)HH.pb(i),ok[i]=INF;
   1520             }else{
   1521                 ok[i]=(Sum[i-1]+Sum[i]<0)+(Sum[i+1]+Sum[i]<0);
   1522                 if(ok[i]==2)HH.pb(i),ok[i]=INF;
   1523             }while(!HH.empty()){
   1524                 TY now=HH.back(),nowL=LL[now],nowR=RR[now];
   1525                 TY k=SSum[nowL]+SSum[nowL-1]+SSum[nowR+1],pre=LL[LL[nowL-1]-1],nxt=RR[nowR+1]+1;
   1526                 HH.pop_back();
   1527                 if(SSum[nowL]>=0){
   1528                     if(pre>=1&&nxt<=c){
   1529                         ok[LL[nowL-1]]=(k+SSum[pre]>=0)+(k+SSum[nxt]>=0);
   1530                         if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
   1531                     }else ok[LL[nowL-1]]=INF;
   1532                     if(pre>=1){
   1533                         ok[pre]+=-(SSum[nowL-1]+SSum[pre]<0)+(SSum[pre]+k<0);
   1534                         if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]>=0)HH.pb(pre),ok[pre]=INF;
   1535                     }if(nxt<=c){
   1536                         ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]<0)+(SSum[nxt]+k<0);
   1537                         if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]>=0)HH.pb(nxt),ok[nxt]=INF;
   1538                     }
   1539                 }else{
   1540                     if(pre>=1&&nxt<=c){
   1541                         ok[LL[nowL-1]]=(k+SSum[pre]<0)+(k+SSum[nxt]<0);
   1542                         if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
   1543                     }else ok[LL[nowL-1]]=INF;
   1544                     if(pre>=1){
   1545                         ok[pre]+=-(SSum[nowL-1]+SSum[pre]>=0)+(SSum[pre]+k>=0);
   1546                         if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]<0)HH.pb(pre),ok[pre]=INF;
   1547                     }if(nxt<=c){
   1548                         ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]>=0)+(SSum[nxt]+k>=0);
   1549                         if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]<0)HH.pb(nxt),ok[nxt]=INF;
   1550                     }
   1551                 }SSum[LL[nowL-1]]=SSum[RR[nowR+1]]=k;
   1552                 RR[LL[nowL-1]]=RR[nowR+1];
   1553                 LL[RR[nowR+1]]=LL[nowL-1];
   1554             }Rof(i,c,1)if(Sum[i]>=0&&vis[i]){
   1555                 Rof(j,i,LL[i])vis[j]=0;
   1556                 tmp.pb({L[LL[i]],R[RR[i]]});
   1557             }Rof(i,tmp.size()-1,0)q.push({tmp[i].first,tmp[i].second,tag,1});
   1558         }else{
   1559             if(l==r){
   1560                 ans+=a[l]+tag+1;
   1561                 continue;
   1562             }queue<TY> fir,sec;
   1563             init(l,r,tag);
   1564             For(i,l,r)if(nxtx[i]==r+1)fir.push(i);
   1565             Rof(i,r,l)if(nxty[i]==l-1)sec.push(i);
   1566             TY lstl=l,lstr=r,lstcnt=0;
   1567             while(lstl<lstr){
   1568                 while(!fir.empty()&&(lstl>fir.front()||fir.front()>lstr))fir.pop();
   1569                 while(!sec.empty()&&(lstl>sec.front()||sec.front()>lstr))sec.pop();
   1570                 TY id1=(fir.empty()?INF:fir.front()),id2=(sec.empty()?INF:sec.front());
   1571                 TY cnt1=(id1==INF?INF:lenx[id1]-lstcnt);
   1572                 TY cnt2=(id2==INF?INF:leny[id2]-lstcnt);
   1573                 if(cnt1<=cnt2){
   1574                     fir.pop();
   1575                     lstcnt=lenx[id1];
   1576                     For(j,lstl,id1){FOR(i,0,e2[j].size())sec.push(e2[j][i]);e2[j].clear();}
   1577                     q.push({lstl,id1,-lstcnt+tag,0});
   1578                     lstl=id1+1;
   1579                 }else{
   1580                     sec.pop();
   1581                     lstcnt=leny[id2];
   1582                     Rof(j,lstr,id2){FOR(i,0,e1[j].size())fir.push(e1[j][i]);e1[j].clear();}
   1583                     q.push({id2,lstr,-lstcnt+tag,0});
   1584                     lstr=id2-1;
   1585                 }
   1586             }if(lstl==lstr)q.push({lstl,lstl,-lstcnt+tag,1});
   1587             ans+=lstcnt;
   1588         }
   1589     }qw(ans);
   1590     return 0;
   1591 }
   1592 ```
   1593 
   1594 **Rate the problem**
   1595 
   1596 * Amazing problem:
   1597 * Good problem:
   1598 * Average problem:
   1599 * Bad problem:
   1600 * Didn't solve: