codeforces-scrape

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

1967.md (22638B)


      1 Source: https://codeforces.com/blog/entry/129027
      2 
      3 [1972A - Contest Proposal](/contest/1972/problem/A "Codeforces Round 942 (Div. 2)")
      4 
      5 **Hint 1**
      6 
      7 Only add problems when they are needed.
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 //By: OIer rui_er
     17 #include <bits/stdc++.h>
     18 #define rep(x, y, z) for(int x = (y); x <= (z); ++x)
     19 #define per(x, y, z) for(int x = (y); x >= (z); --x)
     20 #define endl '\n'
     21 using namespace std;
     22 typedef long long ll;
     23  
     24 const int N = 105;
     25  
     26 int T, n, a[N], b[N];
     27  
     28 int main() {
     29     ios::sync_with_stdio(false);
     30     cin.tie(0); cout.tie(0);
     31     for(cin >> T; T; --T) {
     32         cin >> n;
     33         rep(i, 1, n) cin >> a[i];
     34         rep(i, 1, n) cin >> b[i];
     35         int diff = 0, ans = 0;
     36         rep(i, 1, n) {
     37             if(a[i - diff] > b[i]) {
     38                 ++ans;
     39                 ++diff;
     40             }
     41         }
     42         cout << ans << endl;
     43     }
     44     return 0;
     45 }
     46 ```
     47 
     48 [1972B - Coin Games](/contest/1972/problem/B "Codeforces Round 942 (Div. 2)")
     49 
     50 **Hint 1**
     51 
     52 Is there anything that *never* / *always* changes after each operation?
     53 
     54 **Hint 2**
     55 
     56 The parity.
     57 
     58 **Tutorial**
     59 
     60 Tutorial is loading...
     61 
     62 **Solution**
     63 
     64 ```
     65 //By: OIer rui_er
     66 #include <bits/stdc++.h>
     67 #define rep(x, y, z) for(int x = (y); x <= (z); ++x)
     68 #define per(x, y, z) for(int x = (y); x >= (z); --x)
     69 #define endl '\n'
     70 using namespace std;
     71 typedef long long ll;
     72  
     73 int T, n;
     74 string s;
     75  
     76 int main() {
     77     ios::sync_with_stdio(false);
     78     cin.tie(0); cout.tie(0);
     79     for(cin >> T; T; --T) {
     80         cin >> n >> s;
     81         int cntU = 0;
     82         for(char c : s) if(c == 'U') ++cntU;
     83         if(cntU & 1) cout << "YES" << endl;
     84         else cout << "NO" << endl;
     85     }
     86     return 0;
     87 }
     88 ```
     89 
     90 [1967A - Permutation Counting](/contest/1967/problem/A "Codeforces Round 942 (Div. 1)")
     91 
     92 **Hint 1**
     93 
     94 What's the answer if $a_1=a_2=\cdots=a_n$ and $k=0$?
     95 
     96 **Hint 2**
     97 
     98 What's the answer if $k=0$?
     99 
    100 **Hint 3**
    101 
    102 You've already known the $\mathcal O(k)$ solution. How to improve it?
    103 
    104 **Tutorial**
    105 
    106 Tutorial is loading...
    107 
    108 **Solution**
    109 
    110 ```
    111 #include<bits/stdc++.h>
    112 using namespace std;
    113 void solve()
    114 {
    115     int n;long long k;
    116     cin>>n>>k;
    117     vector<long long>a(n);
    118     for(int x=0;x<n;x++)
    119     cin>>a[x];
    120     sort(a.begin(),a.end());
    121     reverse(a.begin(),a.end());
    122     long long lst=a.back(),cnt=1;
    123     a.pop_back();
    124     while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;
    125     while(!a.empty())
    126     {
    127         long long delta=a.back()-lst;
    128         if(k<delta*cnt)break;
    129         k-=delta*cnt;
    130         lst=a.back();
    131         while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;
    132     }
    133     lst+=k/cnt;
    134     k%=cnt;
    135     cnt-=k;
    136     cout<<lst*n-cnt+1<<endl;
    137 }
    138 main()
    139 {
    140     ios::sync_with_stdio(false),cin.tie(0);
    141     int t;
    142     cin>>t;
    143     while(t--)solve();
    144 }
    145 ```
    146 
    147 [1967B1 - Reverse Card (Easy Version)](/contest/1967/problem/B1 "Codeforces Round 942 (Div. 1)")
    148 
    149 **Hint 1**
    150 
    151 Denote $\gcd(a,b)$ as $d$.
    152 
    153 **Hint 2**
    154 
    155 Did you notice that $b\mid a$? How to prove that?
    156 
    157 **Tutorial**
    158 
    159 Tutorial is loading...
    160 
    161 **Solution**
    162 
    163 ```
    164 #include<bits/stdc++.h>
    165 using namespace std;
    166 typedef long long ll;
    167 const int N=2000005;
    168 int tc,n,m; ll ans;
    169 inline void solve(){
    170 	cin>>n>>m; ans=0;
    171 	for(int i=1;i<=m;i++)
    172 		ans+=(n+i)/(1ll*i*i);
    173 	cout<<ans-1<<'\n';
    174 }
    175 int main(){
    176 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    177 	cin>>tc; while(tc--) solve();
    178 	return 0;
    179 }
    180 ```
    181 
    182 [1967B2 - Reverse Card (Hard Version)](/contest/1967/problem/B2 "Codeforces Round 942 (Div. 1)")
    183 
    184 **Hint 1**
    185 
    186 Denote $\gcd(a,b)$ as $d$. Assume that $a=pd$ and $b=qd$.
    187 
    188 **Hint 2**
    189 
    190 $\gcd(p,q)=1$.
    191 
    192 **Hint 3**
    193 
    194 How large could $p$ and $q$ be?
    195 
    196 **Tutorial**
    197 
    198 Tutorial is loading...
    199 
    200 **Solution**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 using namespace std;
    205  
    206 #define nl "\n"
    207 #define nf endl
    208 #define ll long long
    209 #define pb push_back
    210 #define _ << ' ' <<
    211  
    212 #define INF (ll)1e18
    213 #define mod 998244353
    214 #define maxn 110
    215  
    216 int main() {
    217     ios::sync_with_stdio(0);
    218     cin.tie(0);
    219  
    220     #if !ONLINE_JUDGE && !EVAL
    221         ifstream cin("input.txt");
    222         ofstream cout("output.txt");
    223     #endif
    224     int t;
    225     cin>>t;
    226     while(t--)
    227     {
    228         ll n,m; cin >> n>>m;
    229         ll sq = sqrt(n) + 2,sqm=sqrt(m)+2;
    230     
    231         vector bad(sq + 1, vector<bool>(sqm+1, 0));
    232         for (ll i = 2; i <= min(sq,sqm); i++) {
    233             for (ll a = i; a <= sq; a += i) {
    234                 for (ll b = i; b <= sqm; b += i) {
    235                     bad[a][b] = true;
    236                 }
    237             }
    238         }
    239     
    240         ll ans = 0;
    241         for (ll a = 1; a * a <= n; a++) {
    242             for (ll b = 1; b * b <= m; b++) {
    243                 if (bad[a][b]) continue;
    244                 ans += min(n/(a+b)/a,m/(a+b)/b);
    245             }
    246         }
    247         cout << ans << nl;
    248     }
    249  
    250     return 0;
    251 }
    252 ```
    253 
    254 [1967C - Fenwick Tree](/contest/1967/problem/C "Codeforces Round 942 (Div. 1)")
    255 
    256 **Hint 1**
    257 
    258 The height of a Fenwick Tree is $\mathcal O(\log n)$, so operations like enumerating ancestors of each vertex will be acceptable.
    259 
    260 **Hint 2**
    261 
    262 What's the coefficient of $a_u$ in each $b$ value of its ancestors?
    263 
    264 **Tutorial**
    265 
    266 Tutorial is loading...
    267 
    268 **Solution**
    269 
    270 ```
    271 //By: OIer rui_er
    272 #include <bits/stdc++.h>
    273 #define rep(x, y, z) for(int x = (y); x <= (z); ++x)
    274 #define per(x, y, z) for(int x = (y); x >= (z); --x)
    275 #define debug(format...) fprintf(stderr, format)
    276 #define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
    277 #define endl '\n'
    278 using namespace std;
    279 typedef long long ll;
    280  
    281 mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
    282 int randint(int L, int R) {
    283     uniform_int_distribution<int> dist(L, R);
    284     return dist(rnd);
    285 }
    286  
    287 template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
    288 template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
    289  
    290 template<int mod>
    291 inline unsigned int down(unsigned int x) {
    292 	return x >= mod ? x - mod : x;
    293 }
    294  
    295 template<int mod>
    296 struct Modint {
    297 	unsigned int x;
    298 	Modint() = default;
    299 	Modint(unsigned int x) : x(x) {}
    300 	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
    301 	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
    302 	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
    303 	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
    304 	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
    305 	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
    306 	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
    307 	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
    308 	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
    309 	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
    310 	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
    311 	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
    312 	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
    313 	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
    314 	friend Modint& operator++(Modint& a) {return a += 1;}
    315 	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
    316 	friend Modint& operator--(Modint& a) {return a -= 1;}
    317 	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
    318 	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
    319 	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
    320 };
    321  
    322 const int N = 1e6 + 100, mod = 998244353;
    323 typedef Modint<mod> mint;
    324  
    325 int T, n, k;
    326 mint a[N], inv[N];
    327  
    328 inline int lowbit(int x) {return x & -x;}
    329  
    330 int main() {
    331     ios::sync_with_stdio(false);
    332     cin.tie(0); cout.tie(0);
    333     inv[0] = inv[1] = 1;
    334     rep(i, 2, N - 1) inv[i] = (mod - mod / i) * inv[mod % i];
    335     for(cin >> T; T; --T) {
    336         cin >> n >> k;
    337         rep(i, 1, n) cin >> a[i];
    338         rep(i, 1, n) {
    339             mint mul = 1;
    340             for(int u = i + lowbit(i), d = 1; u <= n; u += lowbit(u), ++d) {
    341                 mul *= (d + k - 1) * inv[d];
    342                 a[u] -= mul * a[i];
    343             }
    344         }
    345         rep(i, 1, n) cout << a[i] << " \n"[i == n];
    346     }
    347     return 0;
    348 }
    349 ```
    350 
    351 [1967D - Long Way to be Non-decreasing](/contest/1967/problem/D "Codeforces Round 942 (Div. 1)")
    352 
    353 **Hint 1**
    354 
    355 Binary search on the answer of magics.
    356 
    357 **Hint 2**
    358 
    359 You may come up with many $\mathcal O(m\log m + n\log^2 m)$ solutions with heavy data structures. Unfortunately, none of them is helpful.
    360 
    361 **Hint 3**
    362 
    363 The key is to judge $\mathcal O(m\log n)$ times whether vertex $u$ is reachable from vertex $v$ in $k$ steps, instead of querying the minimal value or something else.
    364 
    365 **Tutorial**
    366 
    367 Tutorial is loading...
    368 
    369 **Solution**
    370 
    371 ```
    372 #include <bits/stdc++.h>
    373  
    374 namespace FastIO {
    375 	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
    376 	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }
    377 	template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }
    378 	template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }
    379 }; using namespace FastIO;
    380  
    381 #define MAXM 1000001
    382 int dep[MAXM], id[MAXM], dfn[MAXM], to[MAXM], sz[MAXM], tot = 0;
    383 std::vector<int> ch[MAXM];
    384 void dfs(int u) {
    385 	sz[u] = 1, dfn[u] = ++tot;
    386 	for (int v : ch[u]) {
    387 		dep[v] = dep[u] + 1, id[v] = id[u];
    388 		dfs(v), sz[u] += sz[v];
    389 	}
    390 }
    391 inline bool inSub(int u, int v) /* v \in u ? */ { return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + sz[u]; }
    392 constexpr int INF = 0x3f3f3f3f;
    393 inline int query(int u, int v) /* u -> v */ {
    394 	if (u == v) return 0;
    395 	if (id[u] != id[v]) return INF;
    396 	int res = INF;
    397 	if (inSub(v, u)) res = dep[u] - dep[v];
    398 	if (inSub(v, to[id[u]])) res = std::min(dep[u] - dep[v] + dep[to[id[u]]] + 1, res);
    399 	// printf("query(%d, %d) = %d\n", u, v, res);
    400 	return res;
    401 }
    402  
    403 #define MAXN 1000001
    404 int a[MAXN], N, M;
    405 bool check(int val) {
    406 	// printf("check %d\n", val);
    407 	int lst = 1;
    408 	for (int i = 1; i <= N; ++i) {
    409 		while (lst <= M && query(a[i], lst) > val) ++lst;
    410 		if (lst > M) return false;
    411 		// printf("a[%d] = %d\n", i, lst);	
    412 	}
    413 	return true;
    414 }
    415  
    416 namespace DSU {
    417 	int fa[MAXM];
    418 	void inis(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
    419 	inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    420 	inline bool merge(int x, int y) { if (find(x) == find(y)) return false; fa[fa[x]] = fa[y]; return true; }
    421 }; using namespace DSU;
    422  
    423 int main() {
    424 	int T = read<int>();
    425 	while (T--) {
    426 		N = read<int>(), M = read<int>(), inis(M);
    427 		for (int i = 1; i <= N; ++i) a[i] = read<int>();
    428 		for (int x = 1; x <= M; ++x) dep[x] = id[x] = dfn[x] = to[x] = sz[x] = 0, ch[x].clear();
    429 		tot = 0;
    430 		for (int i = 1, p; i <= M; ++i) {
    431 			p = read<int>();
    432 			if (merge(i, p)) ch[p].push_back(i); else to[i] = p;
    433 		}
    434 		for (int i = 1; i <= M; ++i) if (to[i] > 0) id[i] = i, dfs(i);
    435 		if (!check(M)) { puts("-1"); continue; }
    436 		int L = 0, R = M;
    437 		while (L < R) {
    438 			int mid = L + R >> 1;
    439 			if (check(mid)) R = mid; else L = mid + 1;
    440 		}
    441 		print<int>(R, '\n');
    442 	}
    443 }
    444 ```
    445 
    446 [1967E1 - Again Counting Arrays (Easy Version)](/contest/1967/problem/E1 "Codeforces Round 942 (Div. 1)")
    447 
    448 **Hint 1**
    449 
    450 Use the simplest way to judge if an $a$ is valid.
    451 
    452 **Hint 2**
    453 
    454 We've got a $\mathcal O(nm)$ solution. Our target time complexity is $\mathcal O(n\sqrt{n})$.
    455 
    456 **Hint 3**
    457 
    458 It can be boiled down to a grid path counting problem.
    459 
    460 **Tutorial**
    461 
    462 Tutorial is loading...
    463 
    464 **Solution**
    465 
    466 ```
    467 #include <bits/stdc++.h>
    468  
    469 namespace FastIO {
    470 	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
    471 	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }
    472 	template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }
    473 	template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }
    474 }; using namespace FastIO;
    475  
    476 #define MAXN 2000001
    477 namespace Maths {
    478 	constexpr int MOD = 998244353;
    479 	long long qpow(long long a, long long x) { long long ans = 1; while (x) (x & 1) && (ans = ans * a % MOD), a = a * a % MOD, x >>= 1; return ans; }
    480 	long long frac[MAXN << 1 | 1], prac[MAXN << 1 | 1];
    481 	inline void inis(int V = MAXN * 2) { frac[0] = prac[0] = 1; for (int i = 1; i <= V; ++i) frac[i] = frac[i - 1] * i % MOD; prac[V] = qpow(frac[V], MOD - 2); for (int i = V - 1; i; --i) prac[i] = prac[i + 1] * (i + 1) % MOD; }
    482 	inline long long C(int N, int M) { if (N < 0 || M < 0 || N < M) return 0; return frac[N] * prac[M] % MOD * prac[N - M] % MOD; }
    483 }; using namespace Maths;
    484  
    485 struct Point {
    486 	int x, y;
    487 	Point () {}
    488 	Point (int X, int Y) : x(X), y(Y) {}
    489 	inline void flip(int b) { x += b, y -= b, std::swap(x, y); }
    490 	inline int calc() { return C(x + y, y); }
    491 } pA, pB;
    492  
    493 inline void add(int& x, int y) { (x += y) >= MOD && (x -= MOD); }
    494 inline void del(int& x, int y) { (x -= y) < 0 && (x += MOD); }
    495  
    496 int calc(int p, int q, int b1, int b2) {
    497 	pA = pB = Point(p, q);
    498 	int ans = pA.calc();
    499 	while (pA.x >= 0 && pA.y >= 0) 
    500 		pA.flip(b1), del(ans, pA.calc()), pA.flip(b2), add(ans, pA.calc());
    501 	while (pB.x >= 0 && pB.y >= 0) 
    502 		pB.flip(b2), del(ans, pB.calc()), pB.flip(b1), add(ans, pB.calc());
    503 	return ans;
    504 }
    505  
    506 int dp[2][3001], powm[MAXN];
    507 void solve() {
    508 	int N = read<int>(), M = read<int>(), b0 = read<int>();
    509 	if (b0 >= M) return (void)print<int>(qpow(M, N), '\n');
    510 	powm[0] = 1; for (int i = 1; i <= N; ++i) powm[i] = 1ll * M * powm[i - 1] % MOD;
    511 	if (1ll * M * M <= N) { // dp
    512 		for (int k = 0; k < M; ++k) dp[0][k] = (int)(k == b0), dp[1][k] = 0;
    513 		int ans = 1ll * dp[0][M - 1] * (M - 1) % MOD * powm[N - 1] % MOD;
    514 		for (int i = 1; i <= N; ++i) {
    515 			auto now = dp[i & 1], lst = dp[(i & 1) ^ 1];
    516 			now[0] = 0; for (int k = 0; k + 1 < M; ++k) now[k + 1] = 1ll * lst[k] * (M - 1) % MOD;
    517 			for (int k = 1; k < M; ++k) add(now[k - 1], lst[k]);
    518 			if (i < N) add(ans, 1ll * now[M - 1] * (M - 1) % MOD * powm[N - i - 1] % MOD);
    519 		}
    520 		for (int k = 0; k < M; ++k) add(ans, dp[N & 1][k]);
    521 		print<int>(ans, '\n');
    522 	} else { // reflective inclusion-exclusion
    523 		const int B1 = M - b0, B2 = -1 - b0; int ans = qpow(M, N);
    524 		for (int x = b0, y = 0, k = 1, p = b0; p < N; p += 2, ++x, ++y, k = 1ll * k * (M - 1) % MOD) 
    525 			del(ans, 1ll * calc(x, y, B1, B2) * k % MOD * powm[N - p - 1] % MOD);
    526 		print<int>(ans, '\n');
    527 	}
    528 }
    529  
    530 int main() { int T = read<int>(); inis(); while (T--) solve(); return 0; }
    531 ```
    532 
    533 [1967E2 - Again Counting Arrays (Hard Version)](/contest/1967/problem/E2 "Codeforces Round 942 (Div. 1)")
    534 
    535 Thanks [A_G](/profile/A_G "Legendary Grandmaster A_G") for discovering that E2 is possible!
    536 
    537 **Hint 1**
    538 
    539 Solve E1 with $\mathcal O(n\sqrt{n})$ solution first (The $\mathcal O(n\log^2n)$ solution doesn't help much in E2).
    540 
    541 **Hint 2**
    542 
    543 For a single round of inclusion-exclusion, write down the form of the answer as simple as possible.
    544 
    545 **Tutorial**
    546 
    547 Tutorial is loading...
    548 
    549 **Solution**
    550 
    551 ```
    552 #include <bits/stdc++.h>
    553 using namespace std;
    554  
    555 const int MOD = 998244353;
    556 const int N = 2e6+5;
    557 int inv[N];
    558  
    559 int inversemod(int p, int q) {
    560   // assumes p > 0
    561   // https://codeforces.com/blog/entry/23365
    562   return (p > 1 ? q-1LL*inversemod(q%p, p)*q/p : 1);
    563 }
    564  
    565 void add(int& x, int y) {
    566   x += y;
    567   if (x >= MOD) x -= MOD;
    568 }
    569  
    570 void sub(int& x, int y) {
    571   x -= y;
    572   if (x < 0) x += MOD;
    573 }
    574  
    575 int solve(int n, int m, int b0) {
    576   // let X = hit -1, Y = hit m
    577   // f(S) = count of sequences that end up in [0, infty] while containing the pattern S
    578   // g(S) = count of sequences that end up in [-infty, -1] while containing the pattern S
    579   // we want f() - f(X) + f(YX) - f(XYX) + f(YXYX) - f(XYXYX) + ...
    580   //             + g(Y) - g(XY) + g(YXY) - g(XYXY) + g(YXYXY) - ...
    581   vector<int> pw(n+1);
    582   pw[0] = 1;
    583   for (int i = 1; i <= n; i++) pw[i] = 1LL*pw[i-1]*(m-1) % MOD;
    584  
    585   // final ans will be sum from i = 0 to n of (n choose i) a_i
    586   vector<int> a(n+2);
    587   auto work = [&] (int c, int pw_coeff, int sgn_x) -> bool {
    588     // let RANGE = [-infty, -1] if sgn_x == -1 and [0, infty] if sgn_x == 1
    589     // for all x in RANGE such that (n+x+c)/2 is between 0 and n inclusive,
    590     // add pw_coeff*pw[(n+x-b0)/2] to a[(n+x+c)/2]
    591  
    592     // return 0 to signal that we are out of bounds and should exit, otherwise 1
    593     int l = 0;
    594     if (sgn_x == 1) l = max(l, (n+c+1)>>1);
    595     int r = n;
    596     if (sgn_x == -1) r = min(r, (n+c-1)>>1);
    597     if (l > r) return 0;
    598     add(a[l], 1LL*pw_coeff*pw[l-(b0+c)/2] % MOD);
    599     sub(a[r+1], 1LL*pw_coeff*pw[r+1-(b0+c)/2] % MOD);
    600     return 1;
    601   };
    602  
    603   int ans = 0;
    604   // f(k*YX)
    605   // after reflection trick, end up in x + 2*(m+1)*k
    606   for (int k = 0; work(2*(m+1)*k - b0, 1, 1); k++);
    607  
    608   // f(X + k*YX)
    609   // after reflection trick, end up in -2-x - 2*(m+1)*k
    610   for (int k = 0; work(2*(m+1)*k+2+b0, MOD-1, 1); k++);
    611  
    612   // g(Y + k*XY)
    613   // after reflection trick, end up in 2*m-x + 2*(m+1)*k
    614   for (int k = 0; work(-2*m -2*(m+1)*k + b0, 1, -1); k++);
    615  
    616   // g(k*XY)
    617   // after reflection trick, end up in x - 2*(m+1)*k
    618   for (int k = 1; work(-2*(m+1)*k - b0, MOD-1, -1); k++);
    619  
    620   for (int i = 1; i <= n; i++) {
    621     add(a[i], 1LL*a[i-1]*(m-1) % MOD);
    622   }
    623  
    624   // do the binomial stuff without precalculated factorials because why not
    625   int coeff = 1;
    626   for (int i = 0; i <= n; i++) {
    627     add(ans, 1LL * coeff * a[i] % MOD);
    628     coeff = 1LL * coeff * (n-i) % MOD * inv[i+1] % MOD;
    629   }
    630  
    631   return ans;
    632 }
    633  
    634 int main () {
    635   ios_base::sync_with_stdio(0); cin.tie(0);
    636   inv[1] = 1;
    637   for (int i = 2; i < N; i++) inv[i] = 1LL*(MOD-MOD/i)*inv[MOD % i] % MOD;
    638  
    639   int T;
    640   cin >> T;
    641   while (T--) {
    642     int n, m, b0;
    643     cin >> n >> m >> b0;
    644     if (b0 >= m) {
    645       int ans = 1;
    646       for (int i = 0; i < n; i++) ans = 1LL*ans*m % MOD;
    647       cout << ans << '\n';
    648       continue;
    649     }
    650     cout << solve(n, m, b0) << '\n';
    651   }
    652 }
    653 ```
    654 
    655 [1967F - Next and Prev](/contest/1967/problem/F "Codeforces Round 942 (Div. 1)")
    656 
    657 **Hint 1**
    658 
    659 How to maintain $\sum\min(nxt_i-pre_i,x)$? Try $\sum\min(nxt_i-i,x)+\min(i-pre_i,x)$.
    660 
    661 **Hint 2**
    662 
    663 To maintain $\sum\min(nxt_i-i,x)$, we can use chunking. Just +1 and $\operatorname{chkmin}$.
    664 
    665 **Hint 3**
    666 
    667 To finish it, consider what we do in segment-beats.
    668 
    669 **Tutorial**
    670 
    671 Tutorial is loading...
    672 
    673 **Solution**
    674 
    675 ```
    676 #include<bits/stdc++.h>
    677 using namespace std;
    678  
    679 constexpr int maxn=300010,maxq=100010,B=400;
    680  
    681 int n,bn,a[maxn],b[maxn],idx[maxn],nxt[maxn],add[maxn/B+5],mxadd[maxn/B+5],mx[maxn/B+5],se[maxn/B+5],t[maxn];
    682 long long ans[maxq];
    683 vector<int>val[maxn/B+5],mxval[maxn/B+5],pre[maxn/B+5],mxpre[maxn/B+5],pos[maxn/B+5],ks[maxn];
    684  
    685 void vAdd(int i)
    686 {
    687 	for(;i<=n;i+=(i&-i)) t[i]++;
    688 }
    689  
    690 int nQuery(int i)
    691 {
    692 	int s=0;
    693 	for(;i;i-=(i&-i)) s+=t[i];
    694 	return s;
    695 }
    696  
    697 void vWork()
    698 {
    699 	int i,j,tot=0;
    700 	for(i=1;i<=n;i++) b[a[i]]=i;
    701 	for(i=1;i<=n;i++)
    702 	{
    703 		int p=b[i],bp=(p-1)/B+1;
    704 		val[bp].clear();
    705 		mxval[bp].clear();
    706 		auto radixsort=[](vector<int>&v)
    707 		{
    708 			if(v.empty()) return;
    709 			static int buc[1024],res[B+5];
    710 			auto tmp=minmax_element(v.begin(),v.end());
    711 			int mn=*tmp.first,rg=*tmp.second-mn;
    712 			if(!rg) return;
    713 			int lv=__lg(rg)/2+1,len=1<<lv,i;
    714 			memset(buc,0,len*4);
    715 			for(int &it:v) it-=mn,buc[it&(len-1)]++;
    716 			for(i=1;i<len;i++) buc[i]+=buc[i-1];
    717 			for(int it:v) res[--buc[it&(len-1)]]=it;
    718 			memset(buc,0,len*4);
    719 			for(int it:v) buc[it>>lv]++;
    720 			for(i=1;i<len;i++) buc[i]+=buc[i-1];
    721 			for(i=v.size()-1;i>=0;i--) v[--buc[res[i]>>lv]]=res[i]+mn;
    722 		};
    723 		auto getpre=[&](vector<int>&pre,const vector<int>&ori)
    724 		{
    725 			pre.resize(ori.size());
    726 			if(ori.empty()) return;
    727 			pre[0]=ori[0];
    728 			for(int i=1;i<(int)ori.size();i++) pre[i]=pre[i-1]+ori[i];
    729 		};
    730 		int lstmx=mx[bp];
    731 		vAdd(p);
    732 		idx[p]=nQuery(p);
    733 		mx[bp]=nxt[p]=n*2;
    734 		se[bp]=0;
    735 		auto it=pos[bp].begin();
    736 		for(;it<pos[bp].end();it++)
    737 		{
    738 			j=*it;
    739 			if(j>p) break;
    740 			nxt[j]+=add[bp];
    741 			if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];
    742 			nxt[j]=min(nxt[j],idx[p]);
    743 			idx[j]+=add[bp];
    744 			if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];
    745 			else if(nxt[j]>se[bp]) se[bp]=nxt[j];
    746 		}
    747 		it=pos[bp].insert(it,p);
    748 		for(it++;it!=pos[bp].end();it++)
    749 		{
    750 			j=*it;
    751 			nxt[j]+=add[bp];
    752 			if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];
    753 			nxt[j]++;
    754 			idx[j]+=add[bp]+1;
    755 			if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];
    756 			else if(nxt[j]>se[bp]) se[bp]=nxt[j];
    757 		}
    758 		for(int j:pos[bp])
    759 		{
    760 			if(nxt[j]==mx[bp]) mxval[bp].push_back(nxt[j]-idx[j]);
    761 			else val[bp].push_back(nxt[j]-idx[j]);
    762 		}
    763 		add[bp]=mxadd[bp]=0;
    764 		radixsort(val[bp]);
    765 		getpre(pre[bp],val[bp]);
    766 		radixsort(mxval[bp]);
    767 		getpre(mxpre[bp],mxval[bp]);
    768 		for(j=bp+1;j<=bn;j++) add[j]++,mx[j]++,se[j]++;
    769 		for(j=1;j<bp;j++)
    770 		{
    771 			if(mx[j]<=idx[p]) continue;
    772 			if(se[j]<idx[p])
    773 			{
    774 				mxadd[j]+=idx[p]-mx[j],mx[j]=idx[p];
    775 				continue;
    776 			}
    777 			val[j].clear();
    778 			mxval[j].clear();
    779 			lstmx=mx[j];
    780 			mx[j]=idx[p],se[j]=0;
    781 			for(int x:pos[j])
    782 			{
    783 				nxt[x]+=add[j];
    784 				idx[x]+=add[j];
    785 				if(nxt[x]>lstmx) nxt[x]+=mxadd[j];
    786 				if(nxt[x]>=idx[p])
    787 				{
    788 					nxt[x]=idx[p];
    789 					mxval[j].push_back(nxt[x]-idx[x]);
    790 				}
    791 				else
    792 				{
    793 					if(nxt[x]>se[j]) se[j]=nxt[x];
    794 					val[j].push_back(nxt[x]-idx[x]);
    795 				}
    796 			}
    797 			add[j]=mxadd[j]=0;
    798 			radixsort(val[j]);
    799 			getpre(pre[j],val[j]);
    800 			radixsort(mxval[j]);
    801 			getpre(mxpre[j],mxval[j]);
    802 		}
    803 		for(int ki:ks[i])
    804 		{
    805 			tot++;
    806 			for(j=1;j<=bn;j++)
    807 			{
    808 				auto it=lower_bound(val[j].begin(),val[j].end(),ki);
    809 				ans[tot]+=(val[j].end()-it)*ki;
    810 				if(it!=val[j].begin()) ans[tot]+=pre[j][it-val[j].begin()-1];
    811 				it=lower_bound(mxval[j].begin(),mxval[j].end(),ki-mxadd[j]);
    812 				ans[tot]+=(mxval[j].end()-it)*ki;
    813 				if(it!=mxval[j].begin()) ans[tot]+=(it-mxval[j].begin())*mxadd[j]+mxpre[j][it-mxval[j].begin()-1];
    814 			}
    815 		}
    816 	}
    817 }
    818  
    819 int main()
    820 {
    821 	ios::sync_with_stdio(false),cin.tie(0);
    822 	int T;
    823 	cin>>T;
    824 	while(T--)
    825 	{
    826     	int i,ki,tot=0;
    827     	cin>>n;
    828     	bn=(n-1)/B+1;
    829     	for(i=1;i<=n;i++) cin>>a[i];
    830     	for(i=1;i<=n;i++)
    831     	{
    832     		cin>>ki;
    833     		ks[i].resize(ki);
    834     		for(int &it:ks[i])
    835     		{
    836     			cin>>it;
    837     			ans[++tot]=-(i+it-1);
    838     		}
    839     	}
    840     	vWork();
    841     	reverse(a+1,a+n+1);
    842     	for(int x=1;x<=n;x++)
    843     	t[x]=0;
    844     	for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();
    845     	vWork();
    846     	for(int x=1;x<=n;x++)
    847     	t[x]=0;
    848     	for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();
    849     	for(i=1;i<=tot;i++) cout<<ans[i]<<'\n';
    850     	tot=0;
    851 	}
    852 	return 0;
    853 }
    854 ```