NOADJK2 - Editorial

iceknight1093 · February 11, 2026, 4:30pm

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Medium

PREREQUISITES:

Binary search

PROBLEM:

You’re given an array A and a parameter K.
A valid subsequence (i_1, \ldots, i_r) is one such that no two adjacent indices belong to it, and any segment of length K contains at least one chosen index.

Across all valid subsequences, find the maximum possible value of

\max(A_{i_1}, A_{i_2}, \ldots, A_{i_r}) - \min(A_{i_1}, A_{i_2}, \ldots, A_{i_r})

You must also process Q updates to the array.
Each update gives you a value X, and you must update A_i \gets (A_i + X) \bmod M for every index i.
M is constant across updates.

EXPLANATION:

From the solution to the base version of the problem, we know that the answer for a single array is as follows:

If K = 2, consider the even and odd indices separately, take the best \max - \min difference of both.
If K \ge 3, the answer is the maximum difference between two non-adjacent elements.

We now need to maintain this through updates.

First, we solve K = 2.
The even and odd indices are independent, so let’s look at any one of them - say, the odd indices.

Let the elements at the odd indices be x_1 \le x_2 \le\ldots\le x_k, where k = \left\lceil \frac{N}{2} \right\rceil.

Across updates, we need to be able to find the minimum and maximum among these.

The important observation is that if we add the same constant to every element of this sequence and take the results modulo M, the resulting sequence will be some cyclic shift of the original.
That is, suppose we add S to everything and take the results modulo M.
Define y_i = (x_i + S) \bmod M
Then, there will exist an index i such that

y_i \le y_{i+1} \le\ldots\le y_N \le y_1\le\ldots y_{i-1}

Note that if we’re able to find the appropriate index i, then the minimum/maximum will be y_i and y_{i-1} respectively; so finding the cyclic shift is enough.

If we know S, it’s not hard to find the appropriate cyclic shift: the two candidates are either index 1, or the smallest i such that x_i+S\ge M (given that S is reduced modulo M first, of course.)
The latter can be found quickly using binary search.

Thus, we’re able to compute the minimum and maximum elements of the odd-index elements fairly easily, even across updates - because consecutive updates can just be merged into a single overall shift operation.

The same can be done for the even-index elements, and hence we’re able to solve K = 2.

Next, let’s consider K \ge 3.
Here, we want to know the maximum difference between two non-adjacent elements.

From the solution to K = 2, we already know that we can find the minimum and maximum elements of the array after updates.

However, knowing just the minimum and maximum is not enough, since they may be adjacent now.

Instead, note that we actually have something even stronger: we have a relative order of all the array elements (since it’s just a cyclic shift of the initial order.)
Further, while knowing just the min/max won’t suffice, we don’t actually need to know too many elements either.

In particular, it can be shown that in an optimal pair (i, j) where A_i \le A_j, there can be at most two array elements smaller than A_i, and there can be at most two elements larger than A_j.

Proof

Let (i, j) be our chosen pair, and suppose there are three (or more) elements smaller than A_i.
Note that at most two of these elements can then be adjacent to A_j.

So, at least one of these smallest elements is not adjacent to A_j.
Pairing A_j with this smaller element will then result in a larger difference, contradicting (i, j) being optimal.

The same proof applies to having three (or more) elements larger than A_j.

So, while knowing the min/max alone is not enough, we don’t need to go too far away: it’s enough to just find the smallest three elements and largest three elements; and take the largest non-adjacent difference among these elements.

This gives us a \mathcal{O}(\log N) per query solution to the K\ge 3 version as well, since again only a binary search is needed to obtain the three mins/maxes.

TIME COMPLEXITY:

\mathcal{O}((N + Q)\log N) per testcase.

CODE:

Tester's code (C++)

#include <algorithm>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case){
    ll n,k,m,q; cin >> n >> k >> m >> q;
    vector<pll> a(n+5);
    rep1(i,n) cin >> a[i].ff;
    rep1(i,n) a[i].ss = i;
    sort(a.begin()+1,a.begin()+n+1);
    vector<pll> vals[2];
    rep1(i,n) vals[a[i].ss&1].pb(a[i]);
    
    auto get_dis = [&](ll x, ll y){
        // x --> y transition cost
        if(x <= y) return y-x;
        else return y+m-x;
    };
    
    auto get_imp = [&](ll x) -> vector<pll>{
        pll px = {x,-1};
        ll p = lower_bound(a.begin()+1,a.begin()+n+1,px)-a.begin();
        vector<pll> res;
        rep(i,3){
            if(p > n) p = 1;
            ll d = get_dis(x,a[p].ff);
            res.pb({d,a[p].ss});
            p++;
        }
        p = lower_bound(a.begin()+1,a.begin()+n+1,px)-a.begin()-1;
        rep(i,3){
            if(p < 1) p = n;
            ll d = get_dis(x,a[p].ff);
            res.pb({d,a[p].ss});
            p--;
        }
        
        sort(all(res));
        res.resize(unique(all(res))-res.begin());
        return res;
    };
    
    ll sum = 0;
    
    while(q--){
        ll x; cin >> x;
        sum -= x;
        sum = (sum%m+m)%m;
        ll ans = 0;
        
        if(k == 2){
            rep(t,2){
                if(sz(vals[t]) <= 1) conts;
                pll px = {sum,-1};
                ll p = lower_bound(all(vals[t]),px)-vals[t].begin();
                if(p == sz(vals[t])) p = 0;
                ll v1 = get_dis(sum,vals[t][p].ff);
                ll v2 = get_dis(sum,vals[t][(p-1+sz(vals[t]))%sz(vals[t])].ff);
                amax(ans,abs(v1-v2));
            }
        }
        else{
            auto c = get_imp(sum);
            ll siz = sz(c);
            rep(i,siz){
                for(int j = i+1; j < siz; ++j){
                    if(abs(c[i].ss-c[j].ss) > 1){
                        amax(ans,c[j].ff-c[i].ff);
                    }
                }
            }
        }
        
        cout << ans << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    cerr << "RUN SUCCESSFUL" << endl;

    return 0;
}