• Excellent contest
• Good contest
• Average contest
• Bad contest
• Horrible contest

• Trivial contest
• Easy contest
• Average contest
• Hard contest
• Impossible contest

Alice can't lose unless there are no numbers remaining on her turn (in particular, this can only occur if $$$n$$$ is even). So Bob's job is to pair all numbers into disjoint pairs $$$(a, b)$$$ with $$$a+b\equiv 3\pmod 4$$$. If he can do so, he wins by choosing the paired number to each of Alice's choices. Otherwise, Alice wins.

It doesn't really matter if Bob chooses, say, $$$0$$$ or $$$4$$$, because it won't affect the value of $$$a+b\pmod 4$$$. That is, two values are essentially identical in this game if they are equivalent $$$\bmod 4$$$. So now, the numbers on the blackboard are essentially $$$0, 1, 2, 3, 0, 1, 2, 3, \dots (n-1)\pmod 4$$$.

Now, all of the numbers on the blackboard are either $$$0$$$, $$$1$$$, $$$2$$$, or $$$3$$$. It is clear that Bob must pair $$$0$$$ with $$$3$$$, and $$$1$$$ with $$$2$$$. So Bob wins if the number of $$$0$$$'s is the same as the number of $$$3$$$'s, and the number of $$$1$$$'s is the same as the number of $$$2$$$'s.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> cnt(4);
    for(int i=0; i<n; i++)
        cnt[i % 4]++;
    cout << (cnt[0] == cnt[3] && cnt[1] == cnt[2] ? "Bob" : "Alice") << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

For an $$$O(1)$$$ solution, observe that as $$$n$$$ increases, a $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ are introduced, in that order. So the number of $$$0$$$'s can only match the number of $$$3$$$'s, and the number of $$$1$$$'s can only match the number of $$$2$$$'s, if $$$n$$$ is a multiple of $$$4$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    cout << (n % 4 ? "Alice" : "Bob") << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

If $$$k \gt 1$$$, then the answer is always $$$\texttt{YES}$$$. This is because player $$$j$$$ might never get picked.

If $$$k=1$$$, then we claim that the answer is only $$$\texttt{YES}$$$ if player $$$j$$$ has the maximum strength across all players. Indeed, consider the set of players with maximum strength. It is impossible for all of them to get eliminated, because the last one of them can't possibly lose a match. So at least one of these players will be remaining at the end of the game. If player $$$j$$$ is not one of these players, they cannot be the last player remaining.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, j, k, mx = 0;
    cin >> n >> j >> k;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    cout << (k > 1 || a[j] == mx ? "YES" : "NO") << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

If $$$a$$$ has size $$$2$$$, we can make either of its elements the last one. We can transform $$$a$$$ into $$$\min(a_1, a_2)$$$ by choosing the prefix of size $$$2$$$, and we can transform $$$a$$$ into $$$\max(a_1, a_2)$$$ by choosing the suffix of size $$$2$$$.

If $$$a_i$$$ is a prefix min, now we can transform $$$a$$$ into $$$[a_i]$$$. We do so by first choosing the prefix of length $$$i$$$. Now, $$$a_i$$$ is the first element of $$$a$$$. If $$$a$$$ is of size $$$1$$$, we are done. Otherwise, we can choose the suffix consisting of all of the elements after it. Now, our array is of size $$$2$$$, so we can transform $$$a$$$ into $$$[a_i]$$$ as desired. By identical reasoning, if $$$a_i$$$ is a suffix max, we can transform $$$a$$$ into $$$[a_i]$$$.

Now, suppose that $$$a_i$$$ is not a prefix min or a suffix max. Then let $$$a_p$$$ be the min of the prefix $$$[a_1, \dots, a_i]$$$, and let $$$a_s$$$ be the max of the suffix $$$[a_i, \dots, a_n]$$$. Note that $$$p \lt i \lt s$$$ and $$$a_p \lt a_i \lt a_s$$$.

We claim that it is impossible to remove $$$a_p$$$ or $$$a_s$$$ without removing $$$a_i$$$. Consider the first operation which removes (at least) one of $$$a_p$$$, $$$a_i$$$, or $$$a_s$$$.

• Suppose you remove $$$a_p$$$ by choosing a prefix which includes an element smaller than $$$a_p$$$. Since $$$a_p$$$ is the smallest element in $$$[a_1, \dots, a_i]$$$, this means that you must have chosen at least one element after $$$a_i$$$. But then this prefix also includes $$$a_i$$$. Since $$$a_i$$$ is not the min of this prefix, it will also be removed. By identical reasoning, if you remove $$$a_s$$$ by choosing a suffix which includes an element larger than $$$a_s$$$, then $$$a_i$$$ will also be removed.
• Conversely, suppose you remove $$$a_p$$$ by choosing a suffix which includes $$$a_p$$$. But then this suffix will include $$$a_i$$$ and $$$a_s$$$. Since $$$a_i$$$ is not the max of this suffix, it will also be removed. By identical reasoning, if you remove $$$a_s$$$ by choosing a prefix which includes $$$a_s$$$, then $$$a_i$$$ will also be removed.

So the first operation that removes one of $$$a_p$$$, $$$a_i$$$, or $$$a_s$$$ will necessarily remove $$$a_i$$$, so it is impossible to transform $$$a$$$ into $$$[a_i]$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n+1), pre(n+1, INT_MAX), suf(n+2);
    for(int i=1; i<=n; i++){
        cin >> a[i];
        pre[i] = min(pre[i-1], a[i]);
    }
    for(int i=n; i>=1; i--)
        suf[i] = max(suf[i+1], a[i]);
    for(int i=1; i<=n; i++)
        cout << (a[i] == pre[i] || a[i] == suf[i] ? 1 : 0);
    cout << '\n';
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$\mathrm{cnt}$$$ be the number of ones in $$$s$$$. Then clearly if $$$\mathrm{cnt} \leq k$$$, Alice can win immediately.

Now, let's reframe Bob's win condition. Bob can win if and only if he can ensure that, before each of Alice's turns, there are at least $$$k+1$$$ ones in $$$s$$$. In other words, he has to ensure that after each of his turns, $$$\mathrm{cnt} \gt k$$$. Clearly, after each of Bob's turns, $$$\mathrm{cnt} \geq k$$$, since the entire substring he chose is all ones. So he only has to ensure that there is at least one other extra one in $$$s$$$.

If $$$\mathrm{cnt} \gt k$$$ and $$$n\geq 2\cdot k$$$, then Bob can always win. Indeed, on each of Bob's turns, he can pick any existing one in $$$s$$$ to be the extra one. Now, he simply has to choose a substring which doesn't contain this extra one. Then there will be at least $$$k+1$$$ ones; the $$$k$$$ from the substring he chose, and the extra one. If $$$n\geq 2\cdot k$$$, then there must be at least $$$k$$$ elements to either the left or the right of this one, so Bob can choose such a substring.

For example, consider $$$n=8$$$ and $$$k=4$$$. Suppose, before Bob's turn, $$$s=00100010$$$. Then Bob chooses any arbitrary existing one in $$$s$$$, say, the one in the third position. Now, he would like to choose a substring of length $$$k$$$ which does not include the third position. In this case, he can choose the substring $$$s[5, 8]$$$. Now, after his turn, $$$s=00101111$$$. As desired, there are at least five ones, in particular, the four in $$$s[5, 8]$$$ and the extra one in the third position.

This motivates Alice's strategy as well. Suppose that $$$n \lt 2\cdot k$$$. Alice would like to make sure that Bob is losing value from his moves. Notice that every substring of length $$$k$$$ includes the element $$$s_k$$$. So, after Bob's first turn, we have that $$$s_k=1$$$. Now, a winning strategy for Alice is to leave $$$s_k=1$$$ until her last turn, and otherwise choose any $$$k$$$ arbitrary ones to flip. This guarantees that after every round, $$$\mathrm{cnt}$$$ decreases, because Alice flips $$$k$$$ ones, whereas Bob flips at most $$$k-1$$$ zeros, since $$$a_k$$$ is already one. Since $$$\mathrm{cnt}$$$ is nonnegative, finite, and decreasing, it must eventually reach zero.

For example, consider $$$n=8$$$ and $$$k=5$$$. Suppose that before Alice's turn, $$$s=01111101$$$. Then we have that $$$\mathrm{cnt}=6$$$. Alice wants to choose any $$$5$$$ ones to flip, except for $$$s_5$$$. So she chooses to flip $$$s_2$$$, $$$s_3$$$, $$$s_4$$$, $$$s_6$$$, and $$$s_8$$$. Now, before Bob's turn, $$$s=00001000$$$. But any substring of length $$$5$$$ includes $$$s_5$$$, so Bob can only flip at most $$$4$$$ zeros. Suppose he chooses $$$s[2, 6]$$$. Then after his turn, we have that $$$s=01111100$$$. During this round, the value of $$$\mathrm{cnt}$$$ decreased from $$$6$$$ to $$$5$$$, as desired.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, k, cnt = 0;
    string s;
    cin >> n >> k >> s;
    for(char c : s)
        if(c == '1')
            cnt++;
    cout << (cnt <= k || n < 2*k ? "Alice" : "Bob") << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$\mathrm{mex}$$$ be the original $$$\mathrm{MEX}$$$ of $$$a$$$. Clearly we cannot increase $$$\mathrm{MEX}(a)$$$ by removing elements. So, for every $$$0\leq i\leq \mathrm{mex}$$$, let's try to determine, for which $$$k$$$ can we make $$$\mathrm{MEX}(a) = i$$$?

We must have $$$i\leq n-k$$$, since the $$$\mathrm{MEX}$$$ of an array cannot be greater than its size. Furthermore, we must have $$$\mathrm{freq}(i) \leq k$$$, since we have to remove all instances of $$$i$$$ in order to make it the $$$\mathrm{MEX}$$$ of $$$a$$$.

Now, we claim that these are the only constraints. Indeed, suppose that $$$0\leq i\leq \mathrm{mex}$$$, $$$i\leq n-k$$$, and $$$\mathrm{freq}(i) \leq k$$$. We want to choose $$$n-k$$$ elements to keep. Since $$$i\leq \mathrm{mex}$$$, every element smaller than $$$i$$$ is in $$$a$$$, and since $$$i\leq n-k$$$, we can first choose one instance of every element less than $$$i$$$. Now, the $$$\mathrm{MEX}$$$ of our chosen elements is $$$i$$$, so we just need to choose the rest of the elements without affecting the $$$\mathrm{MEX}$$$. We can just choose elements arbitrarily, as long as we don't choose $$$i$$$. Since $$$\mathrm{freq}(i) \leq k$$$, we have enough spare elements to reach our $$$n-k$$$ quota without needing to choose $$$i$$$.

Let's maintain a set of elements which can be $$$\mathrm{MEX}(a)$$$ after removing $$$k$$$ elements. As $$$k$$$ increases, how does this set change? If we compare the set from $$$k-1$$$ to $$$k$$$, we now have that the value $$$n-(k-1)$$$ is no longer legal, since $$$n-(k-1) \gt n-k$$$, so let's erase this element from our set. Furthermore, any elements with frequency $$$k$$$ might now be legal, so let's add them to our set as long as they are $$$\leq \min(\mathrm{mex}, n-k)$$$. Then we output the size of our set.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> freq;
    set<int> excl;
    for(int i=0; i<=n; i++)
        excl.insert(i);
    for(int i=0; i<n; i++){
        cin >> a[i];
        freq[a[i]]++;
        excl.erase(a[i]);
    }
    map<int, vector<int>> invfreq;
    for(pair<int, int> p : freq)
        invfreq[p.second].push_back(p.first);
    int mex = *excl.begin();
    set<int> vals;
    vals.insert(mex);
    for(int k=0; k<=n; k++){
        vals.erase(n-k+1);
        for(int i : invfreq[k])
            if(i <= min(mex, n-k))
                vals.insert(i);
        cout << vals.size() << (k != n ? ' ' : '\n');
    }
}
 
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

Let $$$\mathrm{ans}_k$$$ be the number of possible values of $$$\mathrm{MEX}(a)$$$ after removing $$$k$$$ elements from $$$a$$$. Now, let $$$\mathrm{diff}$$$ be the difference array of $$$\mathrm{ans}$$$; that is, $$$\mathrm{diff}_k = \mathrm{ans}_k - \mathrm{ans}_{k-1}$$$. Then for all $$$0\leq i\leq \mathrm{mex}$$$, we have that $$$\mathrm{MEX}(a)$$$ can be $$$i$$$ if and only if $$$\mathrm{freq}(i) \leq k \leq n-i$$$. So we increment $$$\mathrm{diff}_{\mathrm{freq}(i)}$$$ and decrement $$$\mathrm{diff}_{n-i+1}$$$. Finally, we can reconstruct $$$\mathrm{ans}$$$ by taking the prefix sums of $$$\mathrm{diff}$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n), ans(n+1), diff(n+2);
    map<int, int> freq;
    for(int i=0; i<n; i++){
        cin >> a[i];
        freq[a[i]]++;
    }
    for(int i=0; i<=n; i++){
        diff[freq[i]]++;
        diff[n-i+1]--;
        if(!freq[i])
            break;
    }
    for(int k=0; k<=n; k++){
        ans[k] = (k ? ans[k-1] : 0) + diff[k];
        cout << ans[k] << (k != n ? ' ' : '\n');
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's first find out which values must be fixed points. Clearly if $$$i$$$ is relatively prime to every $$$1\leq j\leq n$$$ with $$$j\neq i$$$, then $$$i$$$ must be a fixed point. This occurs when $$$i=1$$$, or when $$$i$$$ is prime and $$$2\cdot i \gt n$$$, because the smallest number that is not relatively prime to prime $$$i$$$ is $$$2\cdot i$$$.

Now, let's try to construct $$$p$$$ such that these are the only fixed points. Consider the cycle decomposition of $$$p$$$. If we can ensure that all elements in a cycle, excluding the cycle $$$(1)$$$, share a common divisor greater than $$$1$$$, then $$$p$$$ is good.

Notice that a fixed point corresponds to a cycle of length $$$1$$$. So we want as few cycles of length $$$1$$$ as possible. The prime $$$i$$$ are the most restrictive. Let's pair all prime $$$i$$$ with $$$2\cdot i$$$, if possible. Now, none of the primes $$$\leq \frac{n}{2}$$$ are fixed points. For the remaining composites, we have a lot more freedom. We can insert them into the cycle with any one of their prime factors; now, the composites are also not fixed points. Then all cycles share a common divisor, namely, the prime in that cycle, so $$$p$$$ is good.

One systematic way to do this is to partition the elements from $$$1$$$ to $$$n$$$ based on their largest prime divisor. Then, indeed, all of the elements in the cycle containing prime $$$i$$$ are divisible by $$$i$$$, and $$$2\cdot i$$$ has largest prime factor $$$i$$$, so if $$$2\cdot i \leq n$$$, it will be in the cycle containing $$$i$$$.

#include <bits/stdc++.h>
using namespace std;
 
vector<bool> comp(1e5+1);
vector<int> primes;
 
void sieve(){
    for(int i=2; i*i<=1e5; i++)
        if(!comp[i])
            for(int j=i*i; j<=1e5; j+=i)
                comp[j] = true;
    for(int i=2; i<=1e5; i++)
        if(!comp[i])
            primes.push_back(i);
}
 
void solve(){
    int n;
    cin >> n;
    vector<int> p(n+1);
    for(auto it = primes.rbegin(); it != primes.rend(); ++it){
        vector<int> cycle;
        for(int i=*it; i<=n; i+=*it)
            if(!p[i])
                cycle.push_back(i);
        for(int i=0; i<cycle.size(); i++)
            p[cycle[i]] = cycle[(i+1) % cycle.size()];
    }
    for(int i=1; i<=n; i++)
        if(!p[i])
            p[i] = i;
    for(int i=1; i<=n; i++)
        cout << p[i] << (i != n ? ' ' : '\n');
}
 
int main(){
    sieve();
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's first try to answer a query of type 2 in $$$O(n)$$$. We want to set $$$a_1$$$ as small as possible. Then we want to set $$$a_2$$$ to the smallest value which is $$$\geq a_1$$$. We continue to choose elements greedily, selecting the smallest legal value $$$a_i$$$ which is $$$\geq a_{i-1}$$$. If at any point there are no legal values, the answer is $$$\texttt{NO}$$$. Otherwise, the answer is $$$\texttt{YES}$$$.

Now, let's try to characterize what values we can change $$$a_i$$$ into. Clearly $$$a_i\pmod{\gcd(k, m)}$$$ is invariant across operations.

Next, we claim that all values less than $$$m$$$ which are congruent to $$$a_i\pmod{\gcd(k, m)}$$$ are reachable.

First, let's consider the case where $$$\gcd(k, m) = 1$$$. Then we can set $$$a_i := a_i + 1\pmod m$$$ by applying the operation onto $$$a_i$$$, $$$x$$$ times, where $$$x$$$ is the modular multiplicative inverse of $$$k\pmod m$$$. By repeatedly adding $$$1$$$, we can set $$$a_i$$$ to any value.

Next, let's consider the case where $$$\gcd(k, m) \gt 1$$$. Then, if we imagine dividing $$$k$$$ and $$$m$$$ by $$$\gcd(k, m)$$$, we fall into the previous case; that is, we can set $$$a_i := a_i + \gcd(k, m)\pmod m$$$ by applying the operation onto $$$a_i$$$, $$$x$$$ times, where $$$x$$$ is the modular multiplicative inverse of $$$\frac{k}{\gcd(k, m)}\pmod{\frac{m}{\gcd(k, m)}}$$$. By repeatedly adding $$$\gcd(k, m)$$$, we can set $$$a_i$$$ to any value which falls into the same congruence class $$$\bmod{\gcd(k, m)}$$$.

Let's try simulating the greedy process, where we repeatedly choose the smallest value which lies in the same congruence class $$$\bmod \gcd(k, m)$$$. Then if we have $$$a_n \lt m$$$, we can sort the array.

However, we want to represent the array in a way such that we can update $$$a_i$$$ quickly, and check the end-result of $$$a_n$$$ after our greedy process quickly. Let $$$\mathrm{diff}$$$ be the difference array of $$$a$$$; that is, $$$\mathrm{diff}_i = a_i - a_{i-1}$$$ (for convenience, we will define $$$a_0 = 0$$$). Then, by telescoping sum, we have that $$$a_n$$$ is the sum of the elements of the difference array; that is, $$$a_n = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \dots + (a_2 - a_1) + (a_1 - a_0)$$$.

Now, notice that $$$\mathrm{diff}_i$$$ is invariant $$$\bmod{\gcd(k, m)}$$$, and we also must have that $$$\mathrm{diff}_i$$$ is nonnegative for $$$a$$$ to be nondecreasing. So let's maintain the sum of the elements of the difference array, where each element is taken $$$\bmod{\gcd(k, m)}$$$, for each $$$k$$$. Then this is the final value of $$$a_n$$$ after simulating the greedy process. This is quick to update, since only two elements of the difference array are changed with each update.

Finally, we observe that $$$\gcd(k, m)$$$ is always a divisor of $$$m$$$, so we only have to maintain and update $$$d(m)$$$ different values. This allows us to answer queries in $$$O(d(m))$$$ time.

#include <bits/stdc++.h>
using namespace std;
 
int mod(int a, int m){
    return (a % m + m) % m;
}
 
void solve(){
    int n, m, q, op, i, x, k;
    cin >> n >> m >> q;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    map<int, long long> ans;
    for(int i=1; i*i<=m; i++)
        if(!(m % i)){
            ans[i] = 0;
            ans[m/i] = 0;
        }
    for(pair<int, int> p : ans)
        for(int i=1; i<=n; i++)
            ans[p.first] += mod(a[i] - a[i-1], p.first);
    while(q--){
        cin >> op;
        if(op == 1){
            cin >> i >> x;
            for(pair<int, int> p : ans){
                ans[p.first] += mod(x - a[i-1], p.first) - mod(a[i] - a[i-1], p.first);
                if(i != n)
                    ans[p.first] += mod(a[i+1] - x, p.first) - mod(a[i+1] - a[i], p.first);
            }
            a[i] = x;
        }
        else{
            cin >> k;
            cout << (ans[__gcd(k, m)] < m ? "YES" : "NO") << '\n';
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

Imagine putting all of the numbers from $$$0$$$ to $$$m-1$$$ in a grid, where each row is of size $$$\gcd(k, m)$$$. For example, if $$$k=8$$$ and $$$m=12$$$, our grid would look as follows:

Then observe that by applying operations, we can reach any element in the same column. Consider simulating the greedy process. Then we want to choose the lowest row possible; that is, we want to move up in the grid as infrequently as possible.

Notice that we only have to move up in the grid if $$$a_i \pmod{\gcd(k, m)} \lt a_{i-1} \pmod{\gcd(k, m)}$$$, because then we cannot stay in the same row. We want to move up in the grid $$$ \lt \frac{m}{\gcd(k, m)}$$$ times. So let's maintain the number of times we are forced to move up in the grid, for each $$$k$$$. This is quick to update, since when we update $$$a_i$$$, we only have to compare it to the two adjacent values.

Finally, we observe that $$$\gcd(k, m)$$$ is always a divisor of $$$m$$$, so we only have to maintain and update $$$d(m)$$$ different values. This allows us to answer queries in $$$O(d(m))$$$ time.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, m, q, op, i, x, k;
    cin >> n >> m >> q;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    map<int, int> ans;
    for(int i=1; i*i<=m; i++)
        if(!(m % i)){
            ans[i] = 0;
            ans[m/i] = 0;
        }
    for(pair<int, int> p : ans)
        for(int i=1; i<=n; i++)
            ans[p.first] += (a[i] % p.first < a[i-1] % p.first);
    while(q--){
        cin >> op;
        if(op == 1){
            cin >> i >> x;
            for(pair<int, int> p : ans){
                ans[p.first] += (x % p.first < a[i-1] % p.first) - (a[i] % p.first < a[i-1] % p.first);
                if(i != n)
                    ans[p.first] += (a[i+1] % p.first < x % p.first) - (a[i+1] % p.first < a[i] % p.first);
            }
            a[i] = x;
        }
        else{
            cin >> k;
            cout << (ans[__gcd(k, m)] < m / __gcd(k, m) ? "YES" : "NO") << '\n';
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem