Modular Sorting

For query 2 k, one operation adds $k$ modulo $m$ to one element. Applying it many times to the same element gives

$$a_i,\ a_i+k,\ a_i+2k,\dots \pmod m.$$

The set of values reachable from $a_i$ is exactly all values with the same remainder modulo

$$g=\gcd(k,m).$$

So the query is equivalent to this cleaner problem:

Can we choose values $b_i$ such that

$$b_i\equiv a_i \pmod g,$$

and

$$b_1\le b_2\le\dots\le b_n?$$

That is the main simplification. The operation itself is just noise after you notice the gcd.

Residues and levels

Fix some divisor $g$ of $m$. Define

$$r_i=a_i\bmod g.$$

Every possible final value for position $i$ has the form

$$r_i+c_i g,$$

where

$$0\le c_i< m/g.$$

Call $c_i$ the level. There are exactly $m/g$ levels.

Now compare two adjacent positions. We need

$$r_i+c_i g\le r_{i+1}+c_{i+1}g.$$

There are only two cases:

• If $r_i\le r_{i+1}$, then $c_{i+1}=c_i$ already works.
• If $r_i>r_{i+1}$, then the residue wrapped backward, so we must have $c_{i+1}\ge c_i+1$.

So every adjacent drop in the residue sequence forces the level to increase by one.

Let

$$bad_g = \#\{i : a_i\bmod g > a_{i+1}\bmod g\}.$$

Starting from level $0$, after all forced jumps we need final level at least $bad_g$. Since the maximum allowed level is $m/g-1$, sorting is possible exactly when

$$bad_g\le m/g-1.$$

Equivalently:

$$bad_g < m/g.$$

Why this is sufficient

Use the greedy construction:

• Set $c_1=0$.
• Moving left to right, keep the same level if $r_i\le r_{i+1}$.
• Increase the level by $1$ if $r_i>r_{i+1}$.

This creates a nondecreasing sequence, because it does the minimum level increase needed at every adjacent pair. If the total number of drops is less than $m/g$, every chosen value stays below $m$. Done.

No DP. No sorting simulation. Just count the wraps. Very rude of the problem statement to hide that, honestly.

Updates

For every divisor $g$ of $m$, maintain

$$bad_g=\#\{i:a_i\bmod g>a_{i+1}\bmod g\}.$$

For an update 1 i x, only two adjacent comparisons can change:

$$(i-1,i)\quad\text{and}\quad(i,i+1).$$

So for every divisor $g$:

1. remove the old contribution of those pairs,
2. assign $a_i=x$,
3. add the new contribution of those pairs.

For query 2 k:

1. compute $g=\gcd(k,m)$,
2. answer YES iff bad[g] < m / g.

Since $g$ is always a divisor of $m$, we only store counters for divisors of $m$.

Complexity

Let $\tau(m)$ be the number of divisors of $m$.

For each test case:

• building all counters costs $O(n\tau(m))$,
• each update costs $O(\tau(m))$,
• each type 2 query costs $O(\log m+\log \tau(m))$, basically tiny.

The total $n$ and $q$ are at most $10^5$, and $m\le 5\cdot 10^5$, so this easily fits.