Thanks a lot for participating!↵
↵
[problem:2267A]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
signed main() {↵
int T;↵
cin >> T;↵
while (T--) {↵
int n;↵
cin >> n;↵
char c; cin >> c;↵
string s; cin >> s;↵
int ans = 0;↵
for (int i = 0; i < n / 2; ++i) {↵
if (s[i] == s[n - i - 1]) continue;↵
if (s[i] == c || s[n - i - 1] == c) ans++;↵
else ans+=2;↵
}↵
cout << ans << '\n';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:A,option1] Great problem↵
- [likes:A,option2] Good problem↵
- [likes:A,option3] Bad problem↵
- [likes:A,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267B]↵
↵
- Idea: [user:YF_YUSUF,2026-09-25]↵
- Solution + Editorial: [user:YF_YUSUF,2026-09-25], [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267B]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int n, a[101], cnt[101];↵
↵
void solve()↵
{↵
cin >> n;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
cnt[a[i]] ++;↵
}↵
for(int i = 1; i <= n; i ++)↵
{↵
for(int j = 100; j >= 1; j --)↵
{↵
if(cnt[j] >= i) cout << j << ' ';↵
}↵
}↵
for(int i = 1; i <= n; i ++) cnt[a[i]] = 0;↵
↵
cout << '\n';↵
}↵
int main()↵
{↵
int t;↵
cin >> t;↵
while(t --) solve();↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:B,option1] Great problem↵
- [likes:B,option2] Good problem↵
- [likes:B,option3] Bad problem↵
- [likes:B,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267C]↵
↵
- Idea: [user:dibamboo,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267C]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
#define ll long long↵
↵
const int N = 3e5 + 12;↵
using namespace std;↵
↵
int n, x, a[N], p[N];↵
ll cnt[N];↵
↵
vector <int> vc[N];↵
↵
void solve()↵
{↵
cin >> n >> x;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
int r = a[i];↵
a[i] = __gcd(a[i], x);↵
↵
for(auto j : vc[a[i]])↵
{↵
cnt[j] += r;↵
}↵
}↵
ll ans = 0;↵
↵
for(auto j : vc[x])↵
{↵
ans = max(ans, cnt[j]);↵
}↵
for(int i = 1; i <= n; i ++)↵
{↵
for(auto j : vc[a[i]]) cnt[j] = 0;↵
}↵
cout << ans << '\n';↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
for(int i = 2; i <= N - 12; i ++)↵
{↵
if(!p[i])↵
{↵
for(int j = i; j <= N - 12; j += i)↵
{↵
p[j] = 1;↵
vc[j].push_back(i);↵
}↵
}↵
}↵
int test = 0;↵
if(!test) cin >> test;↵
while(test --) solve();↵
}↵
// solved by KluydQ↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:C,option1] Great problem↵
- [likes:C,option2] Good problem↵
- [likes:C,option3] Bad problem↵
- [likes:C,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267D]↵
↵
- Idea: [user:Aldk,2026-09-25]↵
- Solution + Editorial: [user:Aldk,2026-09-25], [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267D]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve()↵
{↵
int n;↵
cin >> n;↵
↵
int a[n + 5];↵
int pos[n + 5];↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
pos[a[i]] = i % 2;↵
}↵
int balance = 0;↵
↵
for(int x = n; x > 0; x --)↵
{↵
if(pos[x] % 2 == 0) balance ++;↵
if(pos[x] % 2 == 1) balance --;↵
↵
if(abs(balance) > 1)↵
{↵
cout << "NO\n";↵
return;↵
}↵
}↵
cout << "YES\n";↵
}↵
int main()↵
{↵
int t;↵
cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:D,option1] Great problem↵
- [likes:D,option2] Good problem↵
- [likes:D,option3] Bad problem↵
- [likes:D,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267E]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267E]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
#define int long long↵
#define sz(x) (int)(x.size())↵
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )↵
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )↵
↵
using namespace std;↵
↵
const int N = 2e5 + 12;↵
const int mod = 1e9 + 7;↵
↵
int n, q, ans, cnt0, cnt1, pr[N];↵
string s;↵
↵
void solve()↵
{↵
cin >> n >> q >> s;↵
ans = cnt0 = cnt1 = 0;↵
↵
FOR(i, 1, n - 1, 1)↵
{↵
pr[i] = 0;↵
↵
if(s[i - 1] != s[i])↵
{↵
pr[i] = 1;↵
ans += i * (n - i);↵
}↵
}↵
FOR(i, 0, n - 1, 1)↵
{↵
if(s[i] == '0') cnt0 ++;↵
if(s[i] == '1') cnt1 ++;↵
}↵
cout << (ans + cnt0 * cnt1) / 2 << ' ';↵
↵
FOR(i, 1, q, 1)↵
{↵
int pos;↵
cin >> pos;↵
↵
if(pos != 1)↵
{↵
if(pr[pos - 1] == 0) pr[pos - 1] = 1, ans += (pos - 1) * (n - pos + 1);↵
else pr[pos - 1] = 0, ans -= (pos - 1) * (n - pos + 1);↵
}↵
if(pos != n)↵
{↵
if(pr[pos] == 0) pr[pos] = 1, ans += pos * (n - pos);↵
else pr[pos] = 0, ans -= pos * (n - pos);↵
}↵
if(s[pos - 1] == '0') cnt0 --, cnt1 ++, s[pos - 1] = '1';↵
else cnt1 --, cnt0 ++, s[pos - 1] = '0';↵
↵
cout << (ans + cnt0 * cnt1) / 2 << ' ';↵
}↵
cout << '\n';↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int t = 0;↵
if(!t) cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:E,option1] Great problem↵
- [likes:E,option2] Good problem↵
- [likes:E,option3] Bad problem↵
- [likes:E,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267F1]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267F1]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 2048;↵
int n, m, tim, a[N], cnt[N], ans[N];↵
↵
void transform()↵
{↵
vector <int> v;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
for(int j = i + 1; j <= n; j ++)↵
{↵
v.push_back(a[i] ^ a[j]);↵
}↵
}↵
sort(v.begin(), v.end());↵
for(int i = 1; i <= n; i ++) a[i] = v[i - 1];↵
}↵
void solve()↵
{↵
cin >> n >> m;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
}↵
sort(a + 1, a + n + 1);↵
int lim = 0;↵
↵
ans[lim] = a[n] - a[1];↵
↵
while(a[n] != 0)↵
{↵
lim ++, transform();↵
ans[lim] = a[n] - a[1];↵
}↵
for(int i = 1; i <= m; i ++)↵
{↵
int x;↵
cin >> x;↵
↵
if(x >= lim) cout << ans[lim] << '\n';↵
else cout << ans[x] << '\n';↵
}↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int test = 0;↵
if(!test) cin >> test;↵
while(test --) solve();↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:F1,option1] Great problem↵
- [likes:F1,option2] Good problem↵
- [likes:F1,option3] Bad problem↵
- [likes:F1,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267F2]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267F2]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 3e5 + 12;↵
↵
int n, m, tim, a[N], cnt[N], ans[N];↵
int t[N * 30], son[N * 30][2];↵
↵
void update(int x, int v = 1)↵
{↵
t[v] ++;↵
↵
for(int i = 29; i >= 0; i --)↵
{↵
if((x >> i) & 1)↵
{↵
if(!son[v][1]) son[v][1] = ++ tim;↵
v = son[v][1];↵
}↵
else↵
{↵
if(!son[v][0]) son[v][0] = ++ tim;↵
v = son[v][0];↵
}↵
t[v] ++;↵
}↵
}↵
int get(int x, int k, int v = 1)↵
{↵
int res = 0;↵
↵
for(int i = 29; i >= 0; i --)↵
{↵
int b = (x >> i) & 1;↵
↵
if(t[son[v][b]] >= k) v = son[v][b], res += (1 << i) * b;↵
else k -= t[son[v][b]], v = son[v][b ^ 1], res += (1 << i) * (b ^ 1);↵
}↵
return res ^ x;↵
}↵
void transform()↵
{↵
for(int v = 1; v <= tim; v ++) t[v] = son[v][0] = son[v][1] = 0;↵
set <pair <int, int>> st; tim = 1;↵
↵
for(int i = 1; i <= n; i ++) update(a[i]), cnt[i] = 2;↵
for(int i = 1; i <= n; i ++) st.insert({get(a[i], 2), i});↵
↵
vector <int> upd;↵
↵
for(int _ = 1; _ <= 2 * n; _ ++)↵
{↵
auto it = st.begin();↵
int i = (*it).second;↵
↵
upd.push_back((*it).first);↵
st.erase(it), cnt[i] ++;↵
↵
if(cnt[i] > n) continue;↵
st.insert({get(a[i], cnt[i]), i});↵
}↵
for(int i = 1; i <= n; i ++) a[i] = upd[(i - 1) * 2];↵
}↵
void solve()↵
{↵
cin >> n >> m;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
}↵
sort(a + 1, a + n + 1);↵
int lim = 0;↵
↵
ans[lim] = a[n] - a[1];↵
↵
while(a[n] != 0)↵
{↵
lim ++, transform();↵
ans[lim] = a[n] - a[1];↵
}↵
for(int i = 1; i <= m; i ++)↵
{↵
int x;↵
cin >> x;↵
↵
if(x >= lim) cout << ans[lim] << '\n';↵
else cout << ans[x] << '\n';↵
}↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int test = 0;↵
if(!test) cin >> test;↵
while(test --) solve();↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:F2,option1] Great problem↵
- [likes:F2,option2] Good problem↵
- [likes:F2,option3] Bad problem↵
- [likes:F2,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267G]↵
↵
- Idea: [user:Aldk,2026-09-25]↵
- Solution + Editorial: [user:Aldk,2026-09-25], [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267G]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
#define sz(x) (int)(x.size())↵
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )↵
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )↵
↵
using namespace std;↵
↵
const int N = (1 << 20) + 5;↵
const int mod = 1e9 + 7;↵
↵
int n, m, c[N], dp[N], cnt[N], st[N][21];↵
↵
void add(int &x, int y)↵
{↵
x += y;↵
if(x >= mod) x -= mod;↵
}↵
void solve()↵
{↵
cin >> n >> m;↵
↵
FOR( i, 1, m, 1 )↵
{↵
cin >> c[i];↵
}↵
dp[0] = cnt[0] = 1;↵
↵
FOR( i, 1, n, 1 )↵
{↵
st[i][0] = 0;↵
↵
FOR( j, 0, 19, 1 )↵
{↵
st[i][j + 1] = st[i][j];↵
if(!((m >> j) & 1) || i < (1 << j)) continue;↵
↵
else↵
{↵
add(st[i][j + 1], st[i - (1 << j)][j]);↵
add(st[i][j + 1], dp[i - (1 << j)]);↵
}↵
}↵
dp[i] = st[i][20];↵
}↵
FOR( i, 1, n, 1 )↵
{↵
st[i][0] = 0;↵
↵
FOR( j, 0, 19, 1 )↵
{↵
st[i][j + 1] = st[i][j];↵
if(!((m >> j) & 1) || i < (1 << j)) continue;↵
↵
else↵
{↵
add(st[i][j + 1], st[i - (1 << j)][j]);↵
add(st[i][j + 1], cnt[i - (1 << j)]);↵
}↵
}↵
cnt[i] = st[i][20];↵
add(cnt[i], dp[i]);↵
}↵
int ans = 0;↵
↵
FOR( i, 1, m, 1 )↵
{↵
if((m & i) == i) add(ans, c[i] * 1ll * cnt[n - i] % mod);↵
}↵
cout << ans << '\n';↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int t = 0;↵
if(!t) cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:G,option1] Great problem↵
- [likes:G,option2] Good problem↵
- [likes:G,option3] Bad problem↵
- [likes:G,option4] Didn't solve↵
↵
</spoiler>↵
↵
↵
[problem:2267A]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
signed main() {↵
int T;↵
cin >> T;↵
while (T--) {↵
int n;↵
cin >> n;↵
char c; cin >> c;↵
string s; cin >> s;↵
int ans = 0;↵
for (int i = 0; i < n / 2; ++i) {↵
if (s[i] == s[n - i - 1]) continue;↵
if (s[i] == c || s[n - i - 1] == c) ans++;↵
else ans+=2;↵
}↵
cout << ans << '\n';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:A,option1] Great problem↵
- [likes:A,option2] Good problem↵
- [likes:A,option3] Bad problem↵
- [likes:A,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267B]↵
↵
- Idea: [user:YF_YUSUF,2026-09-25]↵
- Solution + Editorial: [user:YF_YUSUF,2026-09-25], [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267B]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int n, a[101], cnt[101];↵
↵
void solve()↵
{↵
cin >> n;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
cnt[a[i]] ++;↵
}↵
for(int i = 1; i <= n; i ++)↵
{↵
for(int j = 100; j >= 1; j --)↵
{↵
if(cnt[j] >= i) cout << j << ' ';↵
}↵
}↵
for(int i = 1; i <= n; i ++) cnt[a[i]] = 0;↵
↵
cout << '\n';↵
}↵
int main()↵
{↵
int t;↵
cin >> t;↵
while(t --) solve();↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:B,option1] Great problem↵
- [likes:B,option2] Good problem↵
- [likes:B,option3] Bad problem↵
- [likes:B,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267C]↵
↵
- Idea: [user:dibamboo,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267C]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
#define ll long long↵
↵
const int N = 3e5 + 12;↵
using namespace std;↵
↵
int n, x, a[N], p[N];↵
ll cnt[N];↵
↵
vector <int> vc[N];↵
↵
void solve()↵
{↵
cin >> n >> x;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
int r = a[i];↵
a[i] = __gcd(a[i], x);↵
↵
for(auto j : vc[a[i]])↵
{↵
cnt[j] += r;↵
}↵
}↵
ll ans = 0;↵
↵
for(auto j : vc[x])↵
{↵
ans = max(ans, cnt[j]);↵
}↵
for(int i = 1; i <= n; i ++)↵
{↵
for(auto j : vc[a[i]]) cnt[j] = 0;↵
}↵
cout << ans << '\n';↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
for(int i = 2; i <= N - 12; i ++)↵
{↵
if(!p[i])↵
{↵
for(int j = i; j <= N - 12; j += i)↵
{↵
p[j] = 1;↵
vc[j].push_back(i);↵
}↵
}↵
}↵
int test = 0;↵
if(!test) cin >> test;↵
while(test --) solve();↵
}↵
// solved by KluydQ↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:C,option1] Great problem↵
- [likes:C,option2] Good problem↵
- [likes:C,option3] Bad problem↵
- [likes:C,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267D]↵
↵
- Idea: [user:Aldk,2026-09-25]↵
- Solution + Editorial: [user:Aldk,2026-09-25], [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267D]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve()↵
{↵
int n;↵
cin >> n;↵
↵
int a[n + 5];↵
int pos[n + 5];↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
pos[a[i]] = i % 2;↵
}↵
int balance = 0;↵
↵
for(int x = n; x > 0; x --)↵
{↵
if(pos[x] % 2 == 0) balance ++;↵
if(pos[x] % 2 == 1) balance --;↵
↵
if(abs(balance) > 1)↵
{↵
cout << "NO\n";↵
return;↵
}↵
}↵
cout << "YES\n";↵
}↵
int main()↵
{↵
int t;↵
cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:D,option1] Great problem↵
- [likes:D,option2] Good problem↵
- [likes:D,option3] Bad problem↵
- [likes:D,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267E]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267E]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
#define int long long↵
#define sz(x) (int)(x.size())↵
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )↵
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )↵
↵
using namespace std;↵
↵
const int N = 2e5 + 12;↵
const int mod = 1e9 + 7;↵
↵
int n, q, ans, cnt0, cnt1, pr[N];↵
string s;↵
↵
void solve()↵
{↵
cin >> n >> q >> s;↵
ans = cnt0 = cnt1 = 0;↵
↵
FOR(i, 1, n - 1, 1)↵
{↵
pr[i] = 0;↵
↵
if(s[i - 1] != s[i])↵
{↵
pr[i] = 1;↵
ans += i * (n - i);↵
}↵
}↵
FOR(i, 0, n - 1, 1)↵
{↵
if(s[i] == '0') cnt0 ++;↵
if(s[i] == '1') cnt1 ++;↵
}↵
cout << (ans + cnt0 * cnt1) / 2 << ' ';↵
↵
FOR(i, 1, q, 1)↵
{↵
int pos;↵
cin >> pos;↵
↵
if(pos != 1)↵
{↵
if(pr[pos - 1] == 0) pr[pos - 1] = 1, ans += (pos - 1) * (n - pos + 1);↵
else pr[pos - 1] = 0, ans -= (pos - 1) * (n - pos + 1);↵
}↵
if(pos != n)↵
{↵
if(pr[pos] == 0) pr[pos] = 1, ans += pos * (n - pos);↵
else pr[pos] = 0, ans -= pos * (n - pos);↵
}↵
if(s[pos - 1] == '0') cnt0 --, cnt1 ++, s[pos - 1] = '1';↵
else cnt1 --, cnt0 ++, s[pos - 1] = '0';↵
↵
cout << (ans + cnt0 * cnt1) / 2 << ' ';↵
}↵
cout << '\n';↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int t = 0;↵
if(!t) cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:E,option1] Great problem↵
- [likes:E,option2] Good problem↵
- [likes:E,option3] Bad problem↵
- [likes:E,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267F1]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267F1]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 2048;↵
int n, m, tim, a[N], cnt[N], ans[N];↵
↵
void transform()↵
{↵
vector <int> v;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
for(int j = i + 1; j <= n; j ++)↵
{↵
v.push_back(a[i] ^ a[j]);↵
}↵
}↵
sort(v.begin(), v.end());↵
for(int i = 1; i <= n; i ++) a[i] = v[i - 1];↵
}↵
void solve()↵
{↵
cin >> n >> m;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
}↵
sort(a + 1, a + n + 1);↵
int lim = 0;↵
↵
ans[lim] = a[n] - a[1];↵
↵
while(a[n] != 0)↵
{↵
lim ++, transform();↵
ans[lim] = a[n] - a[1];↵
}↵
for(int i = 1; i <= m; i ++)↵
{↵
int x;↵
cin >> x;↵
↵
if(x >= lim) cout << ans[lim] << '\n';↵
else cout << ans[x] << '\n';↵
}↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int test = 0;↵
if(!test) cin >> test;↵
while(test --) solve();↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:F1,option1] Great problem↵
- [likes:F1,option2] Good problem↵
- [likes:F1,option3] Bad problem↵
- [likes:F1,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267F2]↵
↵
- Idea: [user:KluydQ,2026-09-25]↵
- Solution + Editorial: [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267F2]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 3e5 + 12;↵
↵
int n, m, tim, a[N], cnt[N], ans[N];↵
int t[N * 30], son[N * 30][2];↵
↵
void update(int x, int v = 1)↵
{↵
t[v] ++;↵
↵
for(int i = 29; i >= 0; i --)↵
{↵
if((x >> i) & 1)↵
{↵
if(!son[v][1]) son[v][1] = ++ tim;↵
v = son[v][1];↵
}↵
else↵
{↵
if(!son[v][0]) son[v][0] = ++ tim;↵
v = son[v][0];↵
}↵
t[v] ++;↵
}↵
}↵
int get(int x, int k, int v = 1)↵
{↵
int res = 0;↵
↵
for(int i = 29; i >= 0; i --)↵
{↵
int b = (x >> i) & 1;↵
↵
if(t[son[v][b]] >= k) v = son[v][b], res += (1 << i) * b;↵
else k -= t[son[v][b]], v = son[v][b ^ 1], res += (1 << i) * (b ^ 1);↵
}↵
return res ^ x;↵
}↵
void transform()↵
{↵
for(int v = 1; v <= tim; v ++) t[v] = son[v][0] = son[v][1] = 0;↵
set <pair <int, int>> st; tim = 1;↵
↵
for(int i = 1; i <= n; i ++) update(a[i]), cnt[i] = 2;↵
for(int i = 1; i <= n; i ++) st.insert({get(a[i], 2), i});↵
↵
vector <int> upd;↵
↵
for(int _ = 1; _ <= 2 * n; _ ++)↵
{↵
auto it = st.begin();↵
int i = (*it).second;↵
↵
upd.push_back((*it).first);↵
st.erase(it), cnt[i] ++;↵
↵
if(cnt[i] > n) continue;↵
st.insert({get(a[i], cnt[i]), i});↵
}↵
for(int i = 1; i <= n; i ++) a[i] = upd[(i - 1) * 2];↵
}↵
void solve()↵
{↵
cin >> n >> m;↵
↵
for(int i = 1; i <= n; i ++)↵
{↵
cin >> a[i];↵
}↵
sort(a + 1, a + n + 1);↵
int lim = 0;↵
↵
ans[lim] = a[n] - a[1];↵
↵
while(a[n] != 0)↵
{↵
lim ++, transform();↵
ans[lim] = a[n] - a[1];↵
}↵
for(int i = 1; i <= m; i ++)↵
{↵
int x;↵
cin >> x;↵
↵
if(x >= lim) cout << ans[lim] << '\n';↵
else cout << ans[x] << '\n';↵
}↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int test = 0;↵
if(!test) cin >> test;↵
while(test --) solve();↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:F2,option1] Great problem↵
- [likes:F2,option2] Good problem↵
- [likes:F2,option3] Bad problem↵
- [likes:F2,option4] Didn't solve↵
↵
</spoiler>↵
↵
[problem:2267G]↵
↵
- Idea: [user:Aldk,2026-09-25]↵
- Solution + Editorial: [user:Aldk,2026-09-25], [user:KluydQ,2026-09-25]↵
↵
<spoiler summary="Solution">↵
[tutorial:2267G]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
#define sz(x) (int)(x.size())↵
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )↵
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )↵
↵
using namespace std;↵
↵
const int N = (1 << 20) + 5;↵
const int mod = 1e9 + 7;↵
↵
int n, m, c[N], dp[N], cnt[N], st[N][21];↵
↵
void add(int &x, int y)↵
{↵
x += y;↵
if(x >= mod) x -= mod;↵
}↵
void solve()↵
{↵
cin >> n >> m;↵
↵
FOR( i, 1, m, 1 )↵
{↵
cin >> c[i];↵
}↵
dp[0] = cnt[0] = 1;↵
↵
FOR( i, 1, n, 1 )↵
{↵
st[i][0] = 0;↵
↵
FOR( j, 0, 19, 1 )↵
{↵
st[i][j + 1] = st[i][j];↵
if(!((m >> j) & 1) || i < (1 << j)) continue;↵
↵
else↵
{↵
add(st[i][j + 1], st[i - (1 << j)][j]);↵
add(st[i][j + 1], dp[i - (1 << j)]);↵
}↵
}↵
dp[i] = st[i][20];↵
}↵
FOR( i, 1, n, 1 )↵
{↵
st[i][0] = 0;↵
↵
FOR( j, 0, 19, 1 )↵
{↵
st[i][j + 1] = st[i][j];↵
if(!((m >> j) & 1) || i < (1 << j)) continue;↵
↵
else↵
{↵
add(st[i][j + 1], st[i - (1 << j)][j]);↵
add(st[i][j + 1], cnt[i - (1 << j)]);↵
}↵
}↵
cnt[i] = st[i][20];↵
add(cnt[i], dp[i]);↵
}↵
int ans = 0;↵
↵
FOR( i, 1, m, 1 )↵
{↵
if((m & i) == i) add(ans, c[i] * 1ll * cnt[n - i] % mod);↵
}↵
cout << ans << '\n';↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
int t = 0;↵
if(!t) cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Did you like the problem?">↵
↵
- [likes:G,option1] Great problem↵
- [likes:G,option2] Good problem↵
- [likes:G,option3] Bad problem↵
- [likes:G,option4] Didn't solve↵
↵
</spoiler>↵
↵
