[A](https://codeforces.me/gym/105672/problem/A)↵
↵
Idea:[user:FP7317,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
### Problem Description↵
↵
Since the constraints are small, you only need to simulate this process.↵
↵
You are tasked with finding the minimum number of bandages required to defeat a dragon using a sword. The sword deals:↵
↵
- **1 damage** if the i-th attack is **not divisible by 3**.↵
- **2 damage** if the i-th attack is **divisible by 3**.↵
↵
If your health will becomes less than $0$ when the dragon attack you (in other words, your hp is less than $k$) , you must use a bandage.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
```cpp↵
void solve(){↵
int h,k,n;cin>>h>>k>>n;↵
int ans = 0, l = k, r = 1;↵
while(h > 1){↵
r++;↵
k -= n;↵
if(k <= 0){↵
k = l - n;↵
ans++;↵
}↵
if(r % 3 == 0){↵
h-=2;↵
}else{↵
h--;↵
}↵
}↵
cout<<ans<<endl;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039A,option1]↵
↵
Good problem: [likes:2039A,option2]↵
↵
Average problem: [likes:2039A,option3]↵
↵
Bad problem: [likes:2039A,option4]↵
↵
Didn't solve: [likes:2039A,option5]↵
</spoiler>↵
↵
↵
[B](https://codeforces.me/gym/105672/problem/B)↵
↵
Idea:[user:reyleigh,2025-01-23]↵
↵
<spoiler summary="solution">↵
## Problem Statement↵
↵
OwlBear is attacking a village. The village has *n* cannons, each dealing *a<sub>i</sub>* damage. At the *k*-th second, the OwlBear is protected from the cannon at index (*k*-1) mod *n*. Given *q* queries, each with a damage threshold *h*, find the minimum number of seconds required to deal at least *h* damage.↵
↵
## Analysis↵
↵
The key idea is to precompute the prefix sums of the damage dealt in each second, excluding the blocked cannon. Let `sum` be the total damage all cannons can deal in one second. Then, the damage dealt in the *i*-th second is `sum - a[i % n]`. We can create a prefix sum array `p` where `p[i]` stores the total damage dealt from second 1 to second *i*.↵
↵
To answer a query with damage *h*, we can first calculate how many full cycles of *n* seconds are needed. This can be done by `ans = h / p[n-1]`. The remaining damage is `h -= (ans * p[n-1])`. Then, we multiply `ans` by *n* to get the number of seconds in full cycles. If there is still remaining damage (`h > 0`), we use binary search (specifically `lower_bound`) on the prefix sum array `p` to find the minimum number of additional seconds needed.↵
↵
## Solution↵
↵
1. Read *n* and the damage array *a*.↵
2. Calculate the total damage `sum` and create the prefix sum array `p` where `p[i] = sum - a[i]` and accumulate the prefix sums.↵
3. For each query *h*:↵
* Calculate the number of full cycles: `ans = h / p[n-1]`.↵
* Update the remaining damage: `h -= (ans * p[n-1])`.↵
* Multiply `ans` by *n*.↵
* If `h > 0`, use `lower_bound` on `p` to find the index of the first value greater than or equal to *h*. Add this index + 1 to `ans` to get the final answer.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
```C++↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
int main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int tc;↵
cin >> tc;↵
while (tc--) {↵
int n;↵
cin >> n;↵
vector<ll> a(n), p(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
ll sum = 0;↵
for (int i = 0; i < n; i++) sum += a[i];↵
for (int i = 0; i < n; i++) p[i] = sum - a[i];↵
for (int i = 1; i < n; i++) p[i] += p[i - 1];↵
int q;↵
cin >> q;↵
while (q--) {↵
ll h;↵
cin >> h;↵
ll ans = h / p[n - 1];↵
h -= (ans * p[n - 1]);↵
ans *= n;↵
if (h) ans += lower_bound(p.begin(), p.end(), h) - p.begin()+1;↵
cout << ans << '\n';↵
}↵
}↵
}↵
```↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039b,option1]↵
↵
Good problem: [likes:2039b,option2]↵
↵
Average problem: [likes:2039b,option3]↵
↵
Bad problem: [likes:2039b,option4]↵
↵
Didn't solve: [likes:2039b,option5]↵
</spoiler>↵
↵
[C1](https://codeforces.me/gym/105672/problem/C1)+[C2](https://codeforces.me/gym/105672/problem/C2)↵
↵
Idea:[user:pramod_17,2025-01-23]↵
↵
↵
↵
<spoiler summary="solution(easy version)">↵
↵
We can set $a_{i,j} = a_{j,i} = i + j$ for $i \neq j$, and set $a_{i,i} = 2$ for all $1 \le i \le n$.↵
↵
Now, if $n$ is even, all conditions are met.↵
↵
If $n$ is odd, the XOR of all elements is $2$. To balance out that $2$, we can add $2$ to $a_{3,1}$. ↵
↵
↵
</spoiler>↵
↵
<spoiler summary="solution(hard version)">↵
↵
We set $a_{i,j}$ as the minimum prime factor of (i+j).↵
↵
Now, if $n$ is even, all conditions are met.↵
↵
If $n$ is odd, the XOR of all elements is $2$. There are $2$ cases:↵
↵
- $n \le 17$. In this case we change $a_{1,1}$ to $4$ and $a_{2,2}$ to $6$.↵
↵
- $n > 17$. In this case we change $a_{17,18}$ from $5$ to $7$.↵
↵
<spoiler summary="Analysis">↵
↵
Note $a[i][j] = \min \text{ prime divisor of } (i+j)$, and $d[i][j] = \text{ans}[i][j] - a[i][j]$, where ans is the answer matrix. And $sumd = \text{the sum of all numbers in } d$.↵
↵
### Claim 1:↵
$sumd$ is even. If not, the XOR value is odd.↵
↵
### Claim 2:↵
$sumd = 6$ is an upper bound (put $2 \dots 2 4 6$ in the odd diagonal). So we only need to consider $sumd = 2$ or $4$.↵
↵
### Claim 3:↵
$d[i][j] = 1$ is useless. For odd $a[i][j]$, $\gcd(a[i][j]+1, i+j)$ must be 1 because $a[i][j]$ is the minimum prime divisor of $(i+j)$. For even $a[i][j]$, adding 1 only changes the last bit.↵
↵
### Claim 4:↵
Combine Claim 2 and Claim 3. When $sumd = 2$, it must be $d[x][y] = 2$ and $d[i][j] = 0$ for all $(i, j)$ other than $(x, y)$. We can find the minimum $(i+j)$ is 35 ($5 \times 7$).↵
↵
### Claim 5:↵
When $sumd = 4$, there are only 2 cases: $d[x1][y1] = d[x2][y2] = 2$ and $d[x][y] = 4$. We can find they are all impossible.↵
↵
↵
</spoiler>↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
↵
int t;↵
cin>>t;↵
↵
while(t--){↵
↵
int n;↵
cin>>n;↵
↵
vector<vector<int>> a(n+1,vector<int>(n+1,0));↵
↵
for(int i=1;i<=n;i++){↵
for(int j=1;j<=n;j++){↵
if(i==j) a[i][j] = 2;↵
else a[i][j] = i+j;↵
}↵
}↵
↵
if(n&1){↵
a[3][1] = 6;↵
}↵
↵
for(int i=1;i<=n;i++){↵
for(int j=1;j<=n;j++) cout << a[i][j] << ' ';↵
cout << endl;↵
}↵
↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(C++)(hard version)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace __gnu_pbds;↵
using namespace std;↵
template <typename T>↵
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
template <typename T>↵
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
#define mod 1000000007↵
#define mod2 998244353↵
#define ll long long↵
#define bl __int128_t↵
#define pb push_back↵
#define all(v) v.begin(),v.end()↵
#define bs binary_search↵
#define rall(v) v.rbegin(),v.rend()↵
#define lb lower_bound↵
#define ub upper_bound↵
#define pl pair<ll,ll>↵
#define f(i,n) for(ll i=0;i<n;i++)↵
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]↵
#define pyes cout<<"YES\n"↵
#define pno cout<<"NO\n"↵
using Mat = array<array<ll,2>,2>;↵
↵
#pragma GCC optimize("unroll-loops")↵
#pragma gcc optimize("Ofast")↵
#pragma GCC optimization("Ofast")↵
#pragma optimize(Ofast)↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("popcnt")↵
↵
ll power(ll x,ll y,ll z=LLONG_MAX){↵
ll res=1;↵
while(y>0){↵
if(y%2) res=(res*x)%z;↵
y/=2;↵
if(y) x=(x*x)%z;↵
}return res%z;↵
}↵
↵
ll gcd(ll a,ll b,ll& x,ll& y){↵
x=1,y=0;↵
ll x1=0,y1=1,a1=a,b1=b;↵
while(b1){↵
ll q=a1/b1;↵
tie(x,x1)=make_tuple(x1,x-q*x1);↵
tie(y,y1)=make_tuple(y1,y-q*y1);↵
tie(a1,b1)=make_tuple(b1,a1-q*b1);↵
}return a1;↵
}↵
↵
#define MX 1e4↵
vector<ll> spf(MX+2,1);↵
vector<ll> gpf(MX+2,0);↵
void sieve(){↵
spf[0]=0;↵
for(ll i=2;i<3;i++){↵
if(spf[i]==1){↵
for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;↵
}↵
}for(ll i=3;i<MX+1;i+=2){↵
if(spf[i]==1){↵
for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;↵
}↵
}for(ll i=2;i<=MX;i++) if(gpf[i]==0) for(ll j=i;j<=MX;j+=i) gpf[j]=i;↵
return; ↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;↵
sieve(); // for SPF↵
cin>>t;↵
ll tt=t;↵
string s,s2;↵
while(tt--){↵
cin>>n;↵
assert(n!=1ll);↵
vector<vector<ll>> a(n+1ll,vector<ll>(n+1ll,0ll));↵
f(i,n) f(j,n) a[i+1][j+1] = spf[i+j+2ll];↵
if(n%2ll == 1ll){↵
if(n>18){↵
a[17][18] = 7;↵
}↵
else{↵
a[2][2] = 4ll;↵
a[3][3] = 6ll;↵
}↵
}↵
f(i,n){↵
f(j,n) cout<<a[i+1][j+1]<<' ';↵
cout<<'\n';↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039c,option1]↵
↵
Good problem: [likes:2039c,option2]↵
↵
Average problem: [likes:2039c,option3]↵
↵
Bad problem: [likes:2039c,option4]↵
↵
Didn't solve: [likes:2039c,option5]↵
</spoiler>↵
↵
[D1](https://codeforces.me/gym/105672/problem/D1)+[D2](https://codeforces.me/gym/105672/problem/D2)↵
↵
D1 Idea:[user:sanju77,2025-01-23] ↵
↵
D2 Idea:[user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution(easy version)">↵
↵
There are only $n$ possible different shifts.Let's calculate cost for each of them in O(1).↵
↵
Assume one-based indexing for array. ↵
Let `cost[i]` represent the cost of the array after `i` shifts. ↵
↵
Initial cost: ↵
`cost[0] = 1*a1 + 2*a2 + ... + n*an`↵
↵
cost after first shift: ↵
↵
<spoiler>↵
`cost[1] = 1*a2 + 2*a3 + ... + (n-1)*an + n*a1` </spoiler>↵
↵
Rewriting cost[1] in terms of cost[0] ↵
↵
<spoiler>↵
`cost[1] = cost[0] - sum + n*a1` ↵
</spoiler>↵
↵
cost after second shift: ↵
↵
<spoiler> ↵
`cost[2] = 1*a3 + 2*a4 + ... + (n-1)*a1 + n*a2` ↵
</spoiler>↵
↵
Rewriting cost[2] in terms of cost[1]↵
↵
<spoiler> ↵
`cost[2] = cost[1] - sum + n*a2` ↵
</spoiler>↵
↵
↵
↵
The generalized formula cost[i] from cost[i-1] terms : ↵
↵
<spoiler> ↵
`cost[i] = cost[i-1] - sum + n*a[i]` ↵
</spoiler>↵
↵
### Why the generalized formula is correct? ↵
↵
<spoiler>↵
The generalized formula adjusts the cost for each shift by: ↵
1. Subtracting the total sum (`sum`) of the array (since every element moves one step back in weight). ↵
2. Adding `n*a[i]` to account for the element `a[i]`, which moves to the last position in the array.↵
</spoiler>↵
↵
Using this formula, we can compute the cost for all shifts in **O(1)** per shift and take **minimum** among all, resulting in an overall complexity of **O(n)**.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="solution(hard version)">↵
Let's take↵
↵
$ cost_0 = 1 * a_1 + 2 * a_2 + ... + n * a_n $↵
↵
$ sum = a_1 + a_2 + ... + a_n $↵
↵
for now let's assume no updates on array ( i.e NO query 1 ( static array ) ). In easy version, we know for i>=1↵
↵
$ cost_i = cost_{i-1} - sum + n * a_i $↵
↵
↵
$cost_i$ in terms of $cost_{i-2}$ :↵
↵
<spoiler>↵
$ cost_i = cost_{i-2} - 2 * sum + n * (a_{i-1} + a_i) $↵
</spoiler>↵
↵
If we continue this, we can express the cost at the i-th shift in terms of the 0-th shift:↵
↵
<spoiler>↵
$ cost_i = cost_0 - i * sum + n * (a_1 + a_2 + ... + a_i) $↵
</spoiler>↵
↵
Now, if there are updates in the array, the formula for the cost is modified. When an update occurs at inddex $ind$ , we modify the initial cost as follows:↵
↵
let's say,↵
↵
prev = $a_{ind}$ before update↵
↵
↵
curr = $a_{ind}$ after update↵
↵
we modify the initial cost as follows:↵
↵
<spoiler>↵
$ cost_0 = cost_0 + (curr - prev) * ind $↵
</spoiler>↵
↵
The sum also changes:↵
↵
<spoiler>↵
$ sum = sum + (curr - prev) $↵
</spoiler>↵
↵
To efficiently manage the updates and calculate the prefix sum, we can use Fenwick tree or segment tree (You can learn more about it https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/ ).↵
↵
Thus, the final formula after k shifts, considering updates, is:↵
↵
<spoiler>↵
$ cost_k = cost_0 - k * sum + n * (a_1 + a_2 + ... + a_k) $↵
</spoiler>↵
↵
Time Complexity: $ O((n+q)*logn) $↵
↵
Space Complexity:$ O(n+q) $↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(easy version)">↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
↵
long long t;↵
cin>>t;↵
↵
while(t--)↵
{↵
long long n;↵
cin>>n;↵
long long a[n];↵
long long sum=0;↵
long long ans=0;↵
for(long long i=0;i<n;i++)↵
{↵
cin>>a[i];↵
sum+=a[i];↵
ans+=((i+1)*a[i]);↵
}↵
↵
long long cost=ans;↵
for(long long i=0;i<n;i++) ↵
{↵
cost=cost-sum+n*a[i];↵
ans=min(ans,cost);↵
}↵
cout<<ans<<"\n";↵
}↵
↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="code by sanju77 (hard version)">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
long long BIT[200000]={0}, a[200000]={0}, n;↵
void update(long long x, long long delta)↵
{↵
for(; x <= n; x += x&-x)↵
BIT[x] += delta;↵
}↵
long long query(long long x)↵
{↵
long long sum = 0;↵
for(; x > 0; x -= x&-x)↵
sum += BIT[x];↵
return sum;↵
}↵
↵
int main() {↵
↵
long long t;↵
cin>>t;↵
while(t--) ↵
{↵
cin>>n;↵
long long cost=0;↵
long long sum=0;↵
for(long long i=0;i<n;i++)↵
{↵
cin>>a[i];↵
update(i+1,a[i]);↵
cost+=((i+1)*a[i]);↵
sum+=a[i];↵
}↵
↵
long long q;↵
cin>>q;↵
↵
while(q--)↵
{↵
long long ty;↵
cin>>ty;↵
if(ty==1)↵
{↵
long long ind,x;↵
cin>>ind>>x;↵
cost-=((ind)*(a[ind-1]));↵
sum+=(x-a[ind-1]);↵
update(ind,x-a[ind-1]);↵
a[ind-1]=x;↵
cost+=((ind)*(a[ind-1]));↵
}↵
else↵
{↵
long long k;↵
cin>>k;↵
k%=n;↵
cout<<cost-(k)*(sum)+n*(query(k))<<"\n";↵
}↵
}↵
↵
for(int i = 0; i < n; i++) update(i + 1, -a[i]);↵
}↵
↵
return 0;↵
}↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code by pramod_17 (hard version)">↵
```cpp↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace __gnu_pbds;↵
using namespace std;↵
template <typename T>↵
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
template <typename T>↵
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
#define mod 1000000007↵
#define mod2 998244353↵
#define ll long long↵
#define bl __int128_t↵
#define pb push_back↵
#define all(v) v.begin(),v.end()↵
#define bs binary_search↵
#define rall(v) v.rbegin(),v.rend()↵
#define lb lower_bound↵
#define ub upper_bound↵
#define pl pair<ll,ll>↵
#define f(i,n) for(ll i=0;i<n;i++)↵
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]↵
#define pyes cout<<"YES\n"↵
#define pno cout<<"NO\n"↵
using Mat = array<array<ll,2>,2>;↵
↵
#pragma GCC optimize("unroll-loops")↵
#pragma gcc optimize("Ofast")↵
#pragma GCC optimization("Ofast")↵
#pragma optimize(Ofast)↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("popcnt")↵
↵
ll power(ll x,ll y,ll z=LLONG_MAX){↵
ll res=1;↵
while(y>0){↵
if(y%2) res=(res*x)%z;↵
y/=2;↵
if(y) x=(x*x)%z;↵
}return res%z;↵
}↵
↵
ll gcd(ll a,ll b,ll& x,ll& y){↵
x=1,y=0;↵
ll x1=0,y1=1,a1=a,b1=b;↵
while(b1){↵
ll q=a1/b1;↵
tie(x,x1)=make_tuple(x1,x-q*x1);↵
tie(y,y1)=make_tuple(y1,y-q*y1);↵
tie(a1,b1)=make_tuple(b1,a1-q*b1);↵
}return a1;↵
}↵
↵
template<class T, class U>↵
// T -> node, U->update.↵
struct Lsegtree{↵
vector<T>st;↵
vector<U>lazy;↵
ll n;↵
T identity_element; // related to query↵
U identity_update; // related to update↵
Lsegtree(ll n, T identity_element, U identity_update)↵
{↵
this->n = n;↵
this->identity_element = identity_element;↵
this->identity_update = identity_update;↵
st.assign(4*n,identity_element);↵
lazy.assign(4*n, identity_update);↵
}↵
T combine(T l, T r)↵
{↵
// change this function as required.↵
// related to query↵
T ans = l + r;↵
return ans;↵
}↵
void buildUtil(ll v, ll tl, ll tr, vector<T>&a)↵
{↵
if(tl == tr)↵
{↵
st[v]=a[tl];↵
return;↵
}↵
ll tm = (tl + tr)/2;↵
buildUtil(2*v + 1, tl, tm,a);↵
buildUtil(2*v + 2,tm+1,tr,a);↵
st[v] = combine(st[2*v + 1], st[2*v + 2]);↵
}↵
// change the following 2 functions, and you're more or less done.↵
T apply(T curr, U upd, ll tl, ll tr)↵
{ ↵
// related to update and query↵
T ans = (upd)*(tr-tl+1);↵
return ans;↵
}↵
U combineUpdate(U old_upd, U new_upd, ll tl, ll tr)↵
{ ↵
// related to update↵
U ans = old_upd;↵
ans=(new_upd);↵
return ans;↵
} ↵
void push_down(ll v, ll tl, ll tr)↵
{↵
if(lazy[v] == identity_update)return;↵
st[v] = apply(st[v], lazy[v], tl, tr);↵
if(2*v + 2 < 4*n)↵
{↵
ll tm = (tl + tr)>>1;↵
lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm);↵
lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr); ↵
}↵
lazy[v] = identity_update;↵
}↵
T queryUtil(ll v, ll tl, ll tr, ll l, ll r)↵
{↵
push_down(v,tl,tr);↵
if(l > r)return identity_element;↵
if(tr < l or tl > r)↵
{↵
return identity_element;↵
}↵
if(l <= tl and r >= tr)↵
{↵
return st[v];↵
}↵
ll tm = (tl + tr)>>1;↵
return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r));↵
}↵
void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd)↵
{↵
push_down(v,tl,tr); ↵
if(tr < l or tl > r)return;↵
if(tl >=l and tr <=r)↵
{↵
lazy[v] = combineUpdate(lazy[v],upd,tl,tr);↵
push_down(v,tl,tr);↵
}↵
else↵
{↵
ll tm = (tl + tr)/2;↵
updateUtil(2*v+1,tl,tm,l,r,upd);↵
updateUtil(2*v+2,tm+1,tr,l,r,upd);↵
st[v] = combine(st[2*v + 1], st[2*v+2]);↵
}↵
}↵
void build(vector<T>a)↵
{↵
assert(a.size() == n);↵
buildUtil(0,0,n-1,a);↵
}↵
T query(ll l, ll r)↵
{↵
return queryUtil(0,0,n-1,l,r);↵
}↵
void update(ll l,ll r, U upd)↵
{↵
updateUtil(0,0,n-1,l,r,upd);↵
}↵
ll find_ind(ll v,ll tl,ll tr,ll x){↵
// have to store maximums for this to work↵
if(st[v]>x) return 0;↵
if(tl==tr) return tl;↵
ll tm=(tl+tr)/2;↵
if(st[v+v+1]<=x) return find_ind(v+v+1,tl,tm,x);↵
else return find_ind(v+v+2,tm+1,tr,x-st[v+v+1]);↵
}↵
};↵
↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;↵
// sieve(); // for SPF↵
cin>>t;↵
ll tt=t;↵
string s,s2;↵
while(tt--){↵
ll n;↵
cin>>n;↵
inp(a,n);↵
ll sum = accumulate(all(a),0ll);↵
ll val = 0ll;↵
f(i,n) val += ((i+1)*a[i]);↵
Lsegtree<ll,ll> sega(n,0ll,LLONG_MIN);↵
sega.build(a);↵
↵
ll q;↵
cin>>q; ↵
while(q--){↵
ll x;↵
cin>>x;↵
if(x==1ll){↵
ll ind,p;↵
cin>>ind>>p;↵
ind--;↵
sega.update(ind,ind,p);↵
sum += (p-a[ind]);↵
val += ((ind+1)*(p-a[ind]));↵
a[ind] = p;↵
}↵
else{↵
ll k;↵
cin>>k;↵
k %= n;↵
ll ans = val;↵
if(k>0ll){↵
ans += (n*sega.query(0ll,k-1ll));↵
ans -= (k*sum);↵
}↵
cout<<ans<<'\n';↵
}↵
}↵
}↵
return 0;↵
}↵
↵
↵
```↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039d,option1]↵
↵
Good problem: [likes:2039d,option2]↵
↵
Average problem: [likes:2039d,option3]↵
↵
Bad problem: [likes:2039d,option4]↵
↵
Didn't solve: [likes:2039d,option5]↵
</spoiler>↵
↵
[E](https://codeforces.me/gym/105672/problem/E)↵
↵
Idea:[user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution">↵
↵
### Solution 1:↵
↵
This algorithm is a **randomized algorithm**.↵
↵
We randomly select two fixed points $x$ and $y$, then for all $z \neq x, y$, query "? $x$ $y$ $z$". If the result is 0, it means $z$ and $x$ are on the same side of $y$; otherwise, $z$ and $x$ are on different sides of $y$.↵
↵
Thus, we use $y$ as the pivot and partition the elements into the left and right halves. To determine which side is the actual left half, we need to perform type $1$ operation once, (this is only required in the first partitioning step. After determining the correct position of $y$, no more operations of this type are needed).↵
↵
Once we know the correct position of $y$, we can recursively solve the left and right halves.↵
↵
You might have already noticed that this is essentially the process of **quick sort**. Therefore, the complexity proof is identical to that of quicksort.↵
↵
---↵
↵
### Solution 2:↵
↵
This algorithm is a **deterministic algorithm**.↵
↵
If we can determine the value of $p[1]$, then we can perform a comparison "? $p[1]$ $x$ $y$", where we compare two numbers.↵
↵
The method to determine $p[1]$ is given by the following code:↵
↵
```cpp↵
int u = 1, v = 2;↵
for (int i = 3; i <= n; i++) {↵
int res = ask(u, i, v);↵
if (!res) {↵
res = ask(u, v, i);↵
if (res) v = i;↵
else u = i;↵
}↵
}↵
cout << "1 " << u << ' ' << v << endl;↵
int res;↵
cin >> res;↵
if (!res) swap(u, v);↵
```↵
↵
After determining $p[1]$, you can solve the problem using any $O(n \log n)$ sorting algorithm.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(solution 1)">↵
↵
~~~~~↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
#include <unordered_map>↵
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
using namespace std;↵
typedef double db;↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=0;↵
const ll INF=2147483647;↵
int T,n,keypos;↵
int p[N];↵
/*↵
// 创建随机数生成器↵
std::random_device rd; // 获得随机种子↵
std::mt19937 g(rd()); // 使用Mersenne Twister引擎↵
*/↵
↵
void init()↵
{↵
srand(time(0));↵
cin>>n;↵
keypos=0;↵
}↵
↵
int ask1(int x,int y)↵
{↵
int t;↵
cout<<"1 "<<x<<" "<<y<<"\n";↵
cout.flush();↵
cin>>t;↵
return t;↵
}↵
↵
int ask2(int x,int y,int z)↵
{↵
int t;↵
cout<<"2 "<<x<<" "<<y<<" "<<z<<"\n";↵
cout.flush();↵
cin>>t;↵
return t;↵
}↵
↵
void work(int L,int R,vector<int> &v)↵
{↵
if(L>R) return ;↵
if(L==R)↵
{↵
p[L]=v[0];↵
return ;↵
}↵
if(L==R-1)↵
{↵
if(R<keypos)↵
{↵
if(!ask2(v[0],v[1],p[keypos])) swap(v[0],v[1]);↵
}↵
else↵
{↵
if(!ask2(v[1],v[0],p[keypos])) swap(v[0],v[1]);↵
}↵
p[L]=v[0];↵
p[R]=v[1];↵
return ;↵
}↵
// 使用std::shuffle打乱vector↵
int midpos;↵
vector<int> lhalf,rhalf;↵
↵
//shuffle(v.begin(), v.end(), g);↵
random_shuffle(v.begin(), v.end());↵
lhalf.push_back(v[0]);↵
/*↵
cout<<"L="<<L<<" R="<<R<<"\n shuffled v[]=";↵
for(int i=0;i<v.size();i++) cout<<v[i]<<' ';↵
cout<<"\n";↵
//↵
//↵
cout<<"lhalf[]=";↵
for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';↵
cout<<"\n";↵
*/↵
for(int i=2;i<v.size();i++)↵
{↵
if(ask2(v[0],v[1],v[i])) rhalf.push_back(v[i]);↵
else lhalf.push_back(v[i]);↵
↵
/*↵
cout<<"lhalf[]=";↵
for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';↵
cout<<"\n";↵
*/↵
}↵
if(!keypos)↵
{↵
if(!ask1(v[0],v[1])) swap(lhalf,rhalf);↵
midpos=lhalf.size()+1;↵
p[midpos]=v[1];↵
keypos=midpos;↵
//↵
//printf("keypos=%d\n",keypos);↵
//↵
}↵
else↵
{↵
if(R<keypos)↵
{↵
if(!ask2(v[0],v[1],p[keypos])) swap(lhalf,rhalf);↵
}↵
else↵
{↵
if(!ask2(v[1],v[0],p[keypos])) swap(lhalf,rhalf);↵
}↵
midpos=lhalf.size()+L;↵
p[midpos]=v[1];↵
}↵
/*↵
cout<<"lhalf[]=";↵
for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';↵
cout<<"\n";↵
cout<<"rhalf[]=";↵
for(int i=0;i<rhalf.size();i++) cout<<rhalf[i]<<' ';↵
cout<<"\n";↵
*/↵
work(L,midpos-1,lhalf);↵
work(midpos+1,R,rhalf);↵
}↵
↵
void solve()↵
{↵
vector<int> v;↵
for(int i=1;i<=n;i++) v.push_back(i);↵
work(1,n,v);↵
cout<<"! ";↵
for(int i=1;i<=n;i++) cout<<p[i]<<(i==n?'\n':' ');↵
cout.flush();↵
}↵
↵
//-------------------------------------------------------↵
↵
void gen_data()↵
{↵
srand(time(NULL));↵
}↵
↵
int bruteforce()↵
{↵
return 0;↵
}↵
↵
//-------------------------------------------------------↵
↵
int main()↵
{↵
//fastio;↵
↵
cin>>T;↵
while(T--)↵
{↵
init();↵
solve();↵
↵
/*↵
↵
//Stress Test↵
↵
gen_data();↵
auto ans1=solve(),ans2=bruteforce();↵
if(ans1==ans2) printf("OK!\n");↵
else↵
{↵
//Output Data↵
}↵
↵
*/↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(solution2)">↵
↵
~~~~~↵
// Problem: G. Interactive is Fun↵
// Contest: Codeforces - TheForces Round #39 (DIV4-Forces)↵
// URL: https://codeforces.me/gym/105651/problem/G↵
// Memory Limit: 256 MB↵
// Time Limit: 3000 ms↵
// ↵
// Powered by CP Editor (https://cpeditor.org)↵
↵
#include <bits/stdc++.h>↵
#define all(s) s.begin(), s.end()↵
using namespace std;↵
using ll = long long;↵
using ull = unsigned long long;↵
↵
const int _N = 1e5 + 5;↵
↵
int T;↵
↵
void solve() {↵
int n; cin >> n;↵
vector<int> p(n + 1);↵
for (int i = 1; i <= n; i++) p[i] = i;↵
auto ask = [&](int x, int y, int z) -> bool {↵
cout << "2 " << x << ' ' << y << ' ' << z << endl;↵
int res; cin >> res;↵
return res;↵
};↵
int u = 1, v = 2;↵
for (int i = 3; i <= n; i++) {↵
int res = ask(u, i, v);↵
if (!res) {↵
res = ask(u, v, i);↵
if (res) v = i;↵
else u = i;↵
}↵
}↵
cout << "1 " << u << ' ' << v << endl;↵
int res; cin >> res;↵
if (!res) swap(u, v);↵
stable_sort(p.begin() + 1, p.end(), [&](int i, int j) {↵
return ask(u, i, j);↵
});↵
cout << "! ";↵
for (int i = 1; i <= n; i++) cout << p[i] << " ";↵
cout << endl;↵
return;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039e,option1]↵
Good problem: [likes:2039e,option2]↵
Average problem: [likes:2039e,option3]↵
Bad problem: [likes:2039e,option4]↵
Didn't solve: [likes:2039e,option5]↵
</spoiler>↵
↵
↵
[F](https://codeforces.me/gym/105672/problem/F)↵
↵
Idea:[user:pramod_17,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
↵
Note that performing an operation is always optimal as it won't decrease the answer.↵
↵
At first, lets find the number of good subarrays before applying the operation. For this, the condition is $a_l + a_{l+1} ... + a_r >= k*(r-l+1)$ which is $pre[r] - k*r >= pre[l-1] - k*(l-1)$. So we can make a new array $b$ where $b_i = pre[i] - k*i$ and the initial number of good subarrays is equal to the number of **inversions** in the array $b$.↵
↵
Now, lets say we increment $a_i$ by $1$ for some $i$, then the additional good subarrays formed should have their left boundary to the left of $i$ or equal to $i$ and their right boundary to the right of $i$ or equal to $i$ $(i.e., l \le i \le r)$ and $b_r = b_{l-1} - 1$. If we have the number of additional good subarrays when the operation is performed at $i^{th}$ position, we can easily find the number of additional good subarrays when the operation is performed at $(i+1)^{th}$ position using a `map`.↵
↵
Finally we take maximum over all positions and add it to the initial answer.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
template <typename T>↵
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
template <typename T>↵
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
#define ll long long↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
ll n, k;↵
cin >> n >> k;↵
↵
vector<ll> a(n);↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
↵
vector<ll> b(n + 1, 0ll);↵
for (int i = 0; i < n; i++) {↵
b[i + 1] = b[i] + (a[i] - k);↵
}↵
↵
ll ans = 0;↵
↵
oms<ll> inv;↵
inv.insert(0);↵
↵
for (int i = 0; i < n; i++) {↵
ans += inv.order_of_key(b[i + 1] + 1);↵
inv.insert(b[i + 1]);↵
}↵
↵
ll mx = 0;↵
map<ll, ll> left, right;↵
↵
for (int i = 0; i < n; i++) {↵
right[b[i + 1]]++;↵
}↵
↵
left[0]++;↵
ll val = 0;↵
↵
for (int i = 0; i < n; i++) {↵
if (b[i + 1] == -1) {↵
val++;↵
}↵
}↵
↵
mx = val;↵
↵
for (int i = 2; i <= n; i++) {↵
val += right[b[i - 1] - 1];↵
val -= left[b[i - 1] + 1];↵
↵
left[b[i - 1]]++;↵
right[b[i - 1]]--;↵
↵
mx = max(mx, val);↵
}↵
↵
ans += mx;↵
cout << ans << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039f,option1]↵
↵
Good problem: [likes:2039f,option2]↵
↵
Average problem: [likes:2039f,option3]↵
↵
Bad problem: [likes:2039f,option4]↵
↵
Didn't solve: [likes:2039f,option5]↵
</spoiler>↵
↵
↵
Idea:[user:FP7317,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
### Problem Description↵
↵
Since the constraints are small, you only need to simulate this process.↵
↵
You are tasked with finding the minimum number of bandages required to defeat a dragon using a sword. The sword deals:↵
↵
- **1 damage** if the i-th attack is **not divisible by 3**.↵
- **2 damage** if the i-th attack is **divisible by 3**.↵
↵
If your health will becomes less than $0$ when the dragon attack you (in other words, your hp is less than $k$) , you must use a bandage.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
```cpp↵
void solve(){↵
int h,k,n;cin>>h>>k>>n;↵
int ans = 0, l = k, r = 1;↵
while(h > 1){↵
r++;↵
k -= n;↵
if(k <= 0){↵
k = l - n;↵
ans++;↵
}↵
if(r % 3 == 0){↵
h-=2;↵
}else{↵
h--;↵
}↵
}↵
cout<<ans<<endl;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039A,option1]↵
↵
Good problem: [likes:2039A,option2]↵
↵
Average problem: [likes:2039A,option3]↵
↵
Bad problem: [likes:2039A,option4]↵
↵
Didn't solve: [likes:2039A,option5]↵
</spoiler>↵
↵
↵
[B](https://codeforces.me/gym/105672/problem/B)↵
↵
Idea:[user:reyleigh,2025-01-23]↵
↵
<spoiler summary="solution">↵
## Problem Statement↵
↵
OwlBear is attacking a village. The village has *n* cannons, each dealing *a<sub>i</sub>* damage. At the *k*-th second, the OwlBear is protected from the cannon at index (*k*-1) mod *n*. Given *q* queries, each with a damage threshold *h*, find the minimum number of seconds required to deal at least *h* damage.↵
↵
## Analysis↵
↵
The key idea is to precompute the prefix sums of the damage dealt in each second, excluding the blocked cannon. Let `sum` be the total damage all cannons can deal in one second. Then, the damage dealt in the *i*-th second is `sum - a[i % n]`. We can create a prefix sum array `p` where `p[i]` stores the total damage dealt from second 1 to second *i*.↵
↵
To answer a query with damage *h*, we can first calculate how many full cycles of *n* seconds are needed. This can be done by `ans = h / p[n-1]`. The remaining damage is `h -= (ans * p[n-1])`. Then, we multiply `ans` by *n* to get the number of seconds in full cycles. If there is still remaining damage (`h > 0`), we use binary search (specifically `lower_bound`) on the prefix sum array `p` to find the minimum number of additional seconds needed.↵
↵
## Solution↵
↵
1. Read *n* and the damage array *a*.↵
2. Calculate the total damage `sum` and create the prefix sum array `p` where `p[i] = sum - a[i]` and accumulate the prefix sums.↵
3. For each query *h*:↵
* Calculate the number of full cycles: `ans = h / p[n-1]`.↵
* Update the remaining damage: `h -= (ans * p[n-1])`.↵
* Multiply `ans` by *n*.↵
* If `h > 0`, use `lower_bound` on `p` to find the index of the first value greater than or equal to *h*. Add this index + 1 to `ans` to get the final answer.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
```C++↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
int main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int tc;↵
cin >> tc;↵
while (tc--) {↵
int n;↵
cin >> n;↵
vector<ll> a(n), p(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
ll sum = 0;↵
for (int i = 0; i < n; i++) sum += a[i];↵
for (int i = 0; i < n; i++) p[i] = sum - a[i];↵
for (int i = 1; i < n; i++) p[i] += p[i - 1];↵
int q;↵
cin >> q;↵
while (q--) {↵
ll h;↵
cin >> h;↵
ll ans = h / p[n - 1];↵
h -= (ans * p[n - 1]);↵
ans *= n;↵
if (h) ans += lower_bound(p.begin(), p.end(), h) - p.begin()+1;↵
cout << ans << '\n';↵
}↵
}↵
}↵
```↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039b,option1]↵
↵
Good problem: [likes:2039b,option2]↵
↵
Average problem: [likes:2039b,option3]↵
↵
Bad problem: [likes:2039b,option4]↵
↵
Didn't solve: [likes:2039b,option5]↵
</spoiler>↵
↵
[C1](https://codeforces.me/gym/105672/problem/C1)+[C2](https://codeforces.me/gym/105672/problem/C2)↵
↵
Idea:[user:pramod_17,2025-01-23]↵
↵
↵
↵
<spoiler summary="solution(easy version)">↵
↵
We can set $a_{i,j} = a_{j,i} = i + j$ for $i \neq j$, and set $a_{i,i} = 2$ for all $1 \le i \le n$.↵
↵
Now, if $n$ is even, all conditions are met.↵
↵
If $n$ is odd, the XOR of all elements is $2$. To balance out that $2$, we can add $2$ to $a_{3,1}$. ↵
↵
↵
</spoiler>↵
↵
<spoiler summary="solution(hard version)">↵
↵
We set $a_{i,j}$ as the minimum prime factor of (i+j).↵
↵
Now, if $n$ is even, all conditions are met.↵
↵
If $n$ is odd, the XOR of all elements is $2$. There are $2$ cases:↵
↵
- $n \le 17$. In this case we change $a_{1,1}$ to $4$ and $a_{2,2}$ to $6$.↵
↵
- $n > 17$. In this case we change $a_{17,18}$ from $5$ to $7$.↵
↵
<spoiler summary="Analysis">↵
↵
Note $a[i][j] = \min \text{ prime divisor of } (i+j)$, and $d[i][j] = \text{ans}[i][j] - a[i][j]$, where ans is the answer matrix. And $sumd = \text{the sum of all numbers in } d$.↵
↵
### Claim 1:↵
$sumd$ is even. If not, the XOR value is odd.↵
↵
### Claim 2:↵
$sumd = 6$ is an upper bound (put $2 \dots 2 4 6$ in the odd diagonal). So we only need to consider $sumd = 2$ or $4$.↵
↵
### Claim 3:↵
$d[i][j] = 1$ is useless. For odd $a[i][j]$, $\gcd(a[i][j]+1, i+j)$ must be 1 because $a[i][j]$ is the minimum prime divisor of $(i+j)$. For even $a[i][j]$, adding 1 only changes the last bit.↵
↵
### Claim 4:↵
Combine Claim 2 and Claim 3. When $sumd = 2$, it must be $d[x][y] = 2$ and $d[i][j] = 0$ for all $(i, j)$ other than $(x, y)$. We can find the minimum $(i+j)$ is 35 ($5 \times 7$).↵
↵
### Claim 5:↵
When $sumd = 4$, there are only 2 cases: $d[x1][y1] = d[x2][y2] = 2$ and $d[x][y] = 4$. We can find they are all impossible.↵
↵
↵
</spoiler>↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
↵
int t;↵
cin>>t;↵
↵
while(t--){↵
↵
int n;↵
cin>>n;↵
↵
vector<vector<int>> a(n+1,vector<int>(n+1,0));↵
↵
for(int i=1;i<=n;i++){↵
for(int j=1;j<=n;j++){↵
if(i==j) a[i][j] = 2;↵
else a[i][j] = i+j;↵
}↵
}↵
↵
if(n&1){↵
a[3][1] = 6;↵
}↵
↵
for(int i=1;i<=n;i++){↵
for(int j=1;j<=n;j++) cout << a[i][j] << ' ';↵
cout << endl;↵
}↵
↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(C++)(hard version)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace __gnu_pbds;↵
using namespace std;↵
template <typename T>↵
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
template <typename T>↵
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
#define mod 1000000007↵
#define mod2 998244353↵
#define ll long long↵
#define bl __int128_t↵
#define pb push_back↵
#define all(v) v.begin(),v.end()↵
#define bs binary_search↵
#define rall(v) v.rbegin(),v.rend()↵
#define lb lower_bound↵
#define ub upper_bound↵
#define pl pair<ll,ll>↵
#define f(i,n) for(ll i=0;i<n;i++)↵
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]↵
#define pyes cout<<"YES\n"↵
#define pno cout<<"NO\n"↵
using Mat = array<array<ll,2>,2>;↵
↵
#pragma GCC optimize("unroll-loops")↵
#pragma gcc optimize("Ofast")↵
#pragma GCC optimization("Ofast")↵
#pragma optimize(Ofast)↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("popcnt")↵
↵
ll power(ll x,ll y,ll z=LLONG_MAX){↵
ll res=1;↵
while(y>0){↵
if(y%2) res=(res*x)%z;↵
y/=2;↵
if(y) x=(x*x)%z;↵
}return res%z;↵
}↵
↵
ll gcd(ll a,ll b,ll& x,ll& y){↵
x=1,y=0;↵
ll x1=0,y1=1,a1=a,b1=b;↵
while(b1){↵
ll q=a1/b1;↵
tie(x,x1)=make_tuple(x1,x-q*x1);↵
tie(y,y1)=make_tuple(y1,y-q*y1);↵
tie(a1,b1)=make_tuple(b1,a1-q*b1);↵
}return a1;↵
}↵
↵
#define MX 1e4↵
vector<ll> spf(MX+2,1);↵
vector<ll> gpf(MX+2,0);↵
void sieve(){↵
spf[0]=0;↵
for(ll i=2;i<3;i++){↵
if(spf[i]==1){↵
for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;↵
}↵
}for(ll i=3;i<MX+1;i+=2){↵
if(spf[i]==1){↵
for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;↵
}↵
}for(ll i=2;i<=MX;i++) if(gpf[i]==0) for(ll j=i;j<=MX;j+=i) gpf[j]=i;↵
return; ↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;↵
sieve(); // for SPF↵
cin>>t;↵
ll tt=t;↵
string s,s2;↵
while(tt--){↵
cin>>n;↵
assert(n!=1ll);↵
vector<vector<ll>> a(n+1ll,vector<ll>(n+1ll,0ll));↵
f(i,n) f(j,n) a[i+1][j+1] = spf[i+j+2ll];↵
if(n%2ll == 1ll){↵
if(n>18){↵
a[17][18] = 7;↵
}↵
else{↵
a[2][2] = 4ll;↵
a[3][3] = 6ll;↵
}↵
}↵
f(i,n){↵
f(j,n) cout<<a[i+1][j+1]<<' ';↵
cout<<'\n';↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039c,option1]↵
↵
Good problem: [likes:2039c,option2]↵
↵
Average problem: [likes:2039c,option3]↵
↵
Bad problem: [likes:2039c,option4]↵
↵
Didn't solve: [likes:2039c,option5]↵
</spoiler>↵
↵
[D1](https://codeforces.me/gym/105672/problem/D1)+[D2](https://codeforces.me/gym/105672/problem/D2)↵
↵
D1 Idea:[user:sanju77,2025-01-23] ↵
↵
D2 Idea:[user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution(easy version)">↵
↵
There are only $n$ possible different shifts.Let's calculate cost for each of them in O(1).↵
↵
Assume one-based indexing for array. ↵
Let `cost[i]` represent the cost of the array after `i` shifts. ↵
↵
Initial cost: ↵
`cost[0] = 1*a1 + 2*a2 + ... + n*an`↵
↵
cost after first shift: ↵
↵
<spoiler>↵
`cost[1] = 1*a2 + 2*a3 + ... + (n-1)*an + n*a1` </spoiler>↵
↵
Rewriting cost[1] in terms of cost[0] ↵
↵
<spoiler>↵
`cost[1] = cost[0] - sum + n*a1` ↵
</spoiler>↵
↵
cost after second shift: ↵
↵
<spoiler> ↵
`cost[2] = 1*a3 + 2*a4 + ... + (n-1)*a1 + n*a2` ↵
</spoiler>↵
↵
Rewriting cost[2] in terms of cost[1]↵
↵
<spoiler> ↵
`cost[2] = cost[1] - sum + n*a2` ↵
</spoiler>↵
↵
↵
↵
The generalized formula cost[i] from cost[i-1] terms : ↵
↵
<spoiler> ↵
`cost[i] = cost[i-1] - sum + n*a[i]` ↵
</spoiler>↵
↵
### Why the generalized formula is correct? ↵
↵
<spoiler>↵
The generalized formula adjusts the cost for each shift by: ↵
1. Subtracting the total sum (`sum`) of the array (since every element moves one step back in weight). ↵
2. Adding `n*a[i]` to account for the element `a[i]`, which moves to the last position in the array.↵
</spoiler>↵
↵
Using this formula, we can compute the cost for all shifts in **O(1)** per shift and take **minimum** among all, resulting in an overall complexity of **O(n)**.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="solution(hard version)">↵
Let's take↵
↵
$ cost_0 = 1 * a_1 + 2 * a_2 + ... + n * a_n $↵
↵
$ sum = a_1 + a_2 + ... + a_n $↵
↵
for now let's assume no updates on array ( i.e NO query 1 ( static array ) ). In easy version, we know for i>=1↵
↵
$ cost_i = cost_{i-1} - sum + n * a_i $↵
↵
↵
$cost_i$ in terms of $cost_{i-2}$ :↵
↵
<spoiler>↵
$ cost_i = cost_{i-2} - 2 * sum + n * (a_{i-1} + a_i) $↵
</spoiler>↵
↵
If we continue this, we can express the cost at the i-th shift in terms of the 0-th shift:↵
↵
<spoiler>↵
$ cost_i = cost_0 - i * sum + n * (a_1 + a_2 + ... + a_i) $↵
</spoiler>↵
↵
Now, if there are updates in the array, the formula for the cost is modified. When an update occurs at inddex $ind$ , we modify the initial cost as follows:↵
↵
let's say,↵
↵
prev = $a_{ind}$ before update↵
↵
↵
curr = $a_{ind}$ after update↵
↵
we modify the initial cost as follows:↵
↵
<spoiler>↵
$ cost_0 = cost_0 + (curr - prev) * ind $↵
</spoiler>↵
↵
The sum also changes:↵
↵
<spoiler>↵
$ sum = sum + (curr - prev) $↵
</spoiler>↵
↵
To efficiently manage the updates and calculate the prefix sum, we can use Fenwick tree or segment tree (You can learn more about it https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/ ).↵
↵
Thus, the final formula after k shifts, considering updates, is:↵
↵
<spoiler>↵
$ cost_k = cost_0 - k * sum + n * (a_1 + a_2 + ... + a_k) $↵
</spoiler>↵
↵
Time Complexity: $ O((n+q)*logn) $↵
↵
Space Complexity:$ O(n+q) $↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(easy version)">↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
↵
long long t;↵
cin>>t;↵
↵
while(t--)↵
{↵
long long n;↵
cin>>n;↵
long long a[n];↵
long long sum=0;↵
long long ans=0;↵
for(long long i=0;i<n;i++)↵
{↵
cin>>a[i];↵
sum+=a[i];↵
ans+=((i+1)*a[i]);↵
}↵
↵
long long cost=ans;↵
for(long long i=0;i<n;i++) ↵
{↵
cost=cost-sum+n*a[i];↵
ans=min(ans,cost);↵
}↵
cout<<ans<<"\n";↵
}↵
↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="code by sanju77 (hard version)">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
long long BIT[200000]={0}, a[200000]={0}, n;↵
void update(long long x, long long delta)↵
{↵
for(; x <= n; x += x&-x)↵
BIT[x] += delta;↵
}↵
long long query(long long x)↵
{↵
long long sum = 0;↵
for(; x > 0; x -= x&-x)↵
sum += BIT[x];↵
return sum;↵
}↵
↵
int main() {↵
↵
long long t;↵
cin>>t;↵
while(t--) ↵
{↵
cin>>n;↵
long long cost=0;↵
long long sum=0;↵
for(long long i=0;i<n;i++)↵
{↵
cin>>a[i];↵
update(i+1,a[i]);↵
cost+=((i+1)*a[i]);↵
sum+=a[i];↵
}↵
↵
long long q;↵
cin>>q;↵
↵
while(q--)↵
{↵
long long ty;↵
cin>>ty;↵
if(ty==1)↵
{↵
long long ind,x;↵
cin>>ind>>x;↵
cost-=((ind)*(a[ind-1]));↵
sum+=(x-a[ind-1]);↵
update(ind,x-a[ind-1]);↵
a[ind-1]=x;↵
cost+=((ind)*(a[ind-1]));↵
}↵
else↵
{↵
long long k;↵
cin>>k;↵
k%=n;↵
cout<<cost-(k)*(sum)+n*(query(k))<<"\n";↵
}↵
}↵
↵
for(int i = 0; i < n; i++) update(i + 1, -a[i]);↵
}↵
↵
return 0;↵
}↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code by pramod_17 (hard version)">↵
```cpp↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace __gnu_pbds;↵
using namespace std;↵
template <typename T>↵
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
template <typename T>↵
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
#define mod 1000000007↵
#define mod2 998244353↵
#define ll long long↵
#define bl __int128_t↵
#define pb push_back↵
#define all(v) v.begin(),v.end()↵
#define bs binary_search↵
#define rall(v) v.rbegin(),v.rend()↵
#define lb lower_bound↵
#define ub upper_bound↵
#define pl pair<ll,ll>↵
#define f(i,n) for(ll i=0;i<n;i++)↵
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]↵
#define pyes cout<<"YES\n"↵
#define pno cout<<"NO\n"↵
using Mat = array<array<ll,2>,2>;↵
↵
#pragma GCC optimize("unroll-loops")↵
#pragma gcc optimize("Ofast")↵
#pragma GCC optimization("Ofast")↵
#pragma optimize(Ofast)↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("popcnt")↵
↵
ll power(ll x,ll y,ll z=LLONG_MAX){↵
ll res=1;↵
while(y>0){↵
if(y%2) res=(res*x)%z;↵
y/=2;↵
if(y) x=(x*x)%z;↵
}return res%z;↵
}↵
↵
ll gcd(ll a,ll b,ll& x,ll& y){↵
x=1,y=0;↵
ll x1=0,y1=1,a1=a,b1=b;↵
while(b1){↵
ll q=a1/b1;↵
tie(x,x1)=make_tuple(x1,x-q*x1);↵
tie(y,y1)=make_tuple(y1,y-q*y1);↵
tie(a1,b1)=make_tuple(b1,a1-q*b1);↵
}return a1;↵
}↵
↵
template<class T, class U>↵
// T -> node, U->update.↵
struct Lsegtree{↵
vector<T>st;↵
vector<U>lazy;↵
ll n;↵
T identity_element; // related to query↵
U identity_update; // related to update↵
Lsegtree(ll n, T identity_element, U identity_update)↵
{↵
this->n = n;↵
this->identity_element = identity_element;↵
this->identity_update = identity_update;↵
st.assign(4*n,identity_element);↵
lazy.assign(4*n, identity_update);↵
}↵
T combine(T l, T r)↵
{↵
// change this function as required.↵
// related to query↵
T ans = l + r;↵
return ans;↵
}↵
void buildUtil(ll v, ll tl, ll tr, vector<T>&a)↵
{↵
if(tl == tr)↵
{↵
st[v]=a[tl];↵
return;↵
}↵
ll tm = (tl + tr)/2;↵
buildUtil(2*v + 1, tl, tm,a);↵
buildUtil(2*v + 2,tm+1,tr,a);↵
st[v] = combine(st[2*v + 1], st[2*v + 2]);↵
}↵
// change the following 2 functions, and you're more or less done.↵
T apply(T curr, U upd, ll tl, ll tr)↵
{ ↵
// related to update and query↵
T ans = (upd)*(tr-tl+1);↵
return ans;↵
}↵
U combineUpdate(U old_upd, U new_upd, ll tl, ll tr)↵
{ ↵
// related to update↵
U ans = old_upd;↵
ans=(new_upd);↵
return ans;↵
} ↵
void push_down(ll v, ll tl, ll tr)↵
{↵
if(lazy[v] == identity_update)return;↵
st[v] = apply(st[v], lazy[v], tl, tr);↵
if(2*v + 2 < 4*n)↵
{↵
ll tm = (tl + tr)>>1;↵
lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm);↵
lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr); ↵
}↵
lazy[v] = identity_update;↵
}↵
T queryUtil(ll v, ll tl, ll tr, ll l, ll r)↵
{↵
push_down(v,tl,tr);↵
if(l > r)return identity_element;↵
if(tr < l or tl > r)↵
{↵
return identity_element;↵
}↵
if(l <= tl and r >= tr)↵
{↵
return st[v];↵
}↵
ll tm = (tl + tr)>>1;↵
return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r));↵
}↵
void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd)↵
{↵
push_down(v,tl,tr); ↵
if(tr < l or tl > r)return;↵
if(tl >=l and tr <=r)↵
{↵
lazy[v] = combineUpdate(lazy[v],upd,tl,tr);↵
push_down(v,tl,tr);↵
}↵
else↵
{↵
ll tm = (tl + tr)/2;↵
updateUtil(2*v+1,tl,tm,l,r,upd);↵
updateUtil(2*v+2,tm+1,tr,l,r,upd);↵
st[v] = combine(st[2*v + 1], st[2*v+2]);↵
}↵
}↵
void build(vector<T>a)↵
{↵
assert(a.size() == n);↵
buildUtil(0,0,n-1,a);↵
}↵
T query(ll l, ll r)↵
{↵
return queryUtil(0,0,n-1,l,r);↵
}↵
void update(ll l,ll r, U upd)↵
{↵
updateUtil(0,0,n-1,l,r,upd);↵
}↵
ll find_ind(ll v,ll tl,ll tr,ll x){↵
// have to store maximums for this to work↵
if(st[v]>x) return 0;↵
if(tl==tr) return tl;↵
ll tm=(tl+tr)/2;↵
if(st[v+v+1]<=x) return find_ind(v+v+1,tl,tm,x);↵
else return find_ind(v+v+2,tm+1,tr,x-st[v+v+1]);↵
}↵
};↵
↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;↵
// sieve(); // for SPF↵
cin>>t;↵
ll tt=t;↵
string s,s2;↵
while(tt--){↵
ll n;↵
cin>>n;↵
inp(a,n);↵
ll sum = accumulate(all(a),0ll);↵
ll val = 0ll;↵
f(i,n) val += ((i+1)*a[i]);↵
Lsegtree<ll,ll> sega(n,0ll,LLONG_MIN);↵
sega.build(a);↵
↵
ll q;↵
cin>>q; ↵
while(q--){↵
ll x;↵
cin>>x;↵
if(x==1ll){↵
ll ind,p;↵
cin>>ind>>p;↵
ind--;↵
sega.update(ind,ind,p);↵
sum += (p-a[ind]);↵
val += ((ind+1)*(p-a[ind]));↵
a[ind] = p;↵
}↵
else{↵
ll k;↵
cin>>k;↵
k %= n;↵
ll ans = val;↵
if(k>0ll){↵
ans += (n*sega.query(0ll,k-1ll));↵
ans -= (k*sum);↵
}↵
cout<<ans<<'\n';↵
}↵
}↵
}↵
return 0;↵
}↵
↵
↵
```↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039d,option1]↵
↵
Good problem: [likes:2039d,option2]↵
↵
Average problem: [likes:2039d,option3]↵
↵
Bad problem: [likes:2039d,option4]↵
↵
Didn't solve: [likes:2039d,option5]↵
</spoiler>↵
↵
[E](https://codeforces.me/gym/105672/problem/E)↵
↵
Idea:[user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution">↵
↵
### Solution 1:↵
↵
This algorithm is a **randomized algorithm**.↵
↵
We randomly select two fixed points $x$ and $y$, then for all $z \neq x, y$, query "? $x$ $y$ $z$". If the result is 0, it means $z$ and $x$ are on the same side of $y$; otherwise, $z$ and $x$ are on different sides of $y$.↵
↵
Thus, we use $y$ as the pivot and partition the elements into the left and right halves. To determine which side is the actual left half, we need to perform type $1$ operation once, (this is only required in the first partitioning step. After determining the correct position of $y$, no more operations of this type are needed).↵
↵
Once we know the correct position of $y$, we can recursively solve the left and right halves.↵
↵
You might have already noticed that this is essentially the process of **quick sort**. Therefore, the complexity proof is identical to that of quicksort.↵
↵
---↵
↵
### Solution 2:↵
↵
This algorithm is a **deterministic algorithm**.↵
↵
If we can determine the value of $p[1]$, then we can perform a comparison "? $p[1]$ $x$ $y$", where we compare two numbers.↵
↵
The method to determine $p[1]$ is given by the following code:↵
↵
```cpp↵
int u = 1, v = 2;↵
for (int i = 3; i <= n; i++) {↵
int res = ask(u, i, v);↵
if (!res) {↵
res = ask(u, v, i);↵
if (res) v = i;↵
else u = i;↵
}↵
}↵
cout << "1 " << u << ' ' << v << endl;↵
int res;↵
cin >> res;↵
if (!res) swap(u, v);↵
```↵
↵
After determining $p[1]$, you can solve the problem using any $O(n \log n)$ sorting algorithm.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(solution 1)">↵
↵
~~~~~↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
#include <unordered_map>↵
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
using namespace std;↵
typedef double db;↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=0;↵
const ll INF=2147483647;↵
int T,n,keypos;↵
int p[N];↵
/*↵
// 创建随机数生成器↵
std::random_device rd; // 获得随机种子↵
std::mt19937 g(rd()); // 使用Mersenne Twister引擎↵
*/↵
↵
void init()↵
{↵
srand(time(0));↵
cin>>n;↵
keypos=0;↵
}↵
↵
int ask1(int x,int y)↵
{↵
int t;↵
cout<<"1 "<<x<<" "<<y<<"\n";↵
cout.flush();↵
cin>>t;↵
return t;↵
}↵
↵
int ask2(int x,int y,int z)↵
{↵
int t;↵
cout<<"2 "<<x<<" "<<y<<" "<<z<<"\n";↵
cout.flush();↵
cin>>t;↵
return t;↵
}↵
↵
void work(int L,int R,vector<int> &v)↵
{↵
if(L>R) return ;↵
if(L==R)↵
{↵
p[L]=v[0];↵
return ;↵
}↵
if(L==R-1)↵
{↵
if(R<keypos)↵
{↵
if(!ask2(v[0],v[1],p[keypos])) swap(v[0],v[1]);↵
}↵
else↵
{↵
if(!ask2(v[1],v[0],p[keypos])) swap(v[0],v[1]);↵
}↵
p[L]=v[0];↵
p[R]=v[1];↵
return ;↵
}↵
// 使用std::shuffle打乱vector↵
int midpos;↵
vector<int> lhalf,rhalf;↵
↵
//shuffle(v.begin(), v.end(), g);↵
random_shuffle(v.begin(), v.end());↵
lhalf.push_back(v[0]);↵
/*↵
cout<<"L="<<L<<" R="<<R<<"\n shuffled v[]=";↵
for(int i=0;i<v.size();i++) cout<<v[i]<<' ';↵
cout<<"\n";↵
//↵
//↵
cout<<"lhalf[]=";↵
for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';↵
cout<<"\n";↵
*/↵
for(int i=2;i<v.size();i++)↵
{↵
if(ask2(v[0],v[1],v[i])) rhalf.push_back(v[i]);↵
else lhalf.push_back(v[i]);↵
↵
/*↵
cout<<"lhalf[]=";↵
for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';↵
cout<<"\n";↵
*/↵
}↵
if(!keypos)↵
{↵
if(!ask1(v[0],v[1])) swap(lhalf,rhalf);↵
midpos=lhalf.size()+1;↵
p[midpos]=v[1];↵
keypos=midpos;↵
//↵
//printf("keypos=%d\n",keypos);↵
//↵
}↵
else↵
{↵
if(R<keypos)↵
{↵
if(!ask2(v[0],v[1],p[keypos])) swap(lhalf,rhalf);↵
}↵
else↵
{↵
if(!ask2(v[1],v[0],p[keypos])) swap(lhalf,rhalf);↵
}↵
midpos=lhalf.size()+L;↵
p[midpos]=v[1];↵
}↵
/*↵
cout<<"lhalf[]=";↵
for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';↵
cout<<"\n";↵
cout<<"rhalf[]=";↵
for(int i=0;i<rhalf.size();i++) cout<<rhalf[i]<<' ';↵
cout<<"\n";↵
*/↵
work(L,midpos-1,lhalf);↵
work(midpos+1,R,rhalf);↵
}↵
↵
void solve()↵
{↵
vector<int> v;↵
for(int i=1;i<=n;i++) v.push_back(i);↵
work(1,n,v);↵
cout<<"! ";↵
for(int i=1;i<=n;i++) cout<<p[i]<<(i==n?'\n':' ');↵
cout.flush();↵
}↵
↵
//-------------------------------------------------------↵
↵
void gen_data()↵
{↵
srand(time(NULL));↵
}↵
↵
int bruteforce()↵
{↵
return 0;↵
}↵
↵
//-------------------------------------------------------↵
↵
int main()↵
{↵
//fastio;↵
↵
cin>>T;↵
while(T--)↵
{↵
init();↵
solve();↵
↵
/*↵
↵
//Stress Test↵
↵
gen_data();↵
auto ans1=solve(),ans2=bruteforce();↵
if(ans1==ans2) printf("OK!\n");↵
else↵
{↵
//Output Data↵
}↵
↵
*/↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(solution2)">↵
↵
~~~~~↵
// Problem: G. Interactive is Fun↵
// Contest: Codeforces - TheForces Round #39 (DIV4-Forces)↵
// URL: https://codeforces.me/gym/105651/problem/G↵
// Memory Limit: 256 MB↵
// Time Limit: 3000 ms↵
// ↵
// Powered by CP Editor (https://cpeditor.org)↵
↵
#include <bits/stdc++.h>↵
#define all(s) s.begin(), s.end()↵
using namespace std;↵
using ll = long long;↵
using ull = unsigned long long;↵
↵
const int _N = 1e5 + 5;↵
↵
int T;↵
↵
void solve() {↵
int n; cin >> n;↵
vector<int> p(n + 1);↵
for (int i = 1; i <= n; i++) p[i] = i;↵
auto ask = [&](int x, int y, int z) -> bool {↵
cout << "2 " << x << ' ' << y << ' ' << z << endl;↵
int res; cin >> res;↵
return res;↵
};↵
int u = 1, v = 2;↵
for (int i = 3; i <= n; i++) {↵
int res = ask(u, i, v);↵
if (!res) {↵
res = ask(u, v, i);↵
if (res) v = i;↵
else u = i;↵
}↵
}↵
cout << "1 " << u << ' ' << v << endl;↵
int res; cin >> res;↵
if (!res) swap(u, v);↵
stable_sort(p.begin() + 1, p.end(), [&](int i, int j) {↵
return ask(u, i, j);↵
});↵
cout << "! ";↵
for (int i = 1; i <= n; i++) cout << p[i] << " ";↵
cout << endl;↵
return;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039e,option1]↵
Good problem: [likes:2039e,option2]↵
Average problem: [likes:2039e,option3]↵
Bad problem: [likes:2039e,option4]↵
Didn't solve: [likes:2039e,option5]↵
</spoiler>↵
↵
↵
[F](https://codeforces.me/gym/105672/problem/F)↵
↵
Idea:[user:pramod_17,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
↵
Note that performing an operation is always optimal as it won't decrease the answer.↵
↵
At first, lets find the number of good subarrays before applying the operation. For this, the condition is $a_l + a_{l+1} ... + a_r >= k*(r-l+1)$ which is $pre[r] - k*r >= pre[l-1] - k*(l-1)$. So we can make a new array $b$ where $b_i = pre[i] - k*i$ and the initial number of good subarrays is equal to the number of **inversions** in the array $b$.↵
↵
Now, lets say we increment $a_i$ by $1$ for some $i$, then the additional good subarrays formed should have their left boundary to the left of $i$ or equal to $i$ and their right boundary to the right of $i$ or equal to $i$ $(i.e., l \le i \le r)$ and $b_r = b_{l-1} - 1$. If we have the number of additional good subarrays when the operation is performed at $i^{th}$ position, we can easily find the number of additional good subarrays when the operation is performed at $(i+1)^{th}$ position using a `map`.↵
↵
Finally we take maximum over all positions and add it to the initial answer.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
template <typename T>↵
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
template <typename T>↵
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
#define ll long long↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
ll n, k;↵
cin >> n >> k;↵
↵
vector<ll> a(n);↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
↵
vector<ll> b(n + 1, 0ll);↵
for (int i = 0; i < n; i++) {↵
b[i + 1] = b[i] + (a[i] - k);↵
}↵
↵
ll ans = 0;↵
↵
oms<ll> inv;↵
inv.insert(0);↵
↵
for (int i = 0; i < n; i++) {↵
ans += inv.order_of_key(b[i + 1] + 1);↵
inv.insert(b[i + 1]);↵
}↵
↵
ll mx = 0;↵
map<ll, ll> left, right;↵
↵
for (int i = 0; i < n; i++) {↵
right[b[i + 1]]++;↵
}↵
↵
left[0]++;↵
ll val = 0;↵
↵
for (int i = 0; i < n; i++) {↵
if (b[i + 1] == -1) {↵
val++;↵
}↵
}↵
↵
mx = val;↵
↵
for (int i = 2; i <= n; i++) {↵
val += right[b[i - 1] - 1];↵
val -= left[b[i - 1] + 1];↵
↵
left[b[i - 1]]++;↵
right[b[i - 1]]--;↵
↵
mx = max(mx, val);↵
}↵
↵
ans += mx;↵
cout << ans << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039f,option1]↵
↵
Good problem: [likes:2039f,option2]↵
↵
Average problem: [likes:2039f,option3]↵
↵
Bad problem: [likes:2039f,option4]↵
↵
Didn't solve: [likes:2039f,option5]↵
</spoiler>↵
↵
