Nhận xét #1 : Điều kiện ~|a_i - a_{i+1}|~ chia hết cho ~k~ tương đương ~a_i~ và ~a_{i+1}~ đồng dư khi chia cho ~k~, vậy ta không thể thay đổi thứ tự của các phần tử nếu chúng đồng dư khi chia cho ~k~.

Nhận xét #2 : Theo thuật toán kinh điển merge sort, luôn tồn tại cách để hợp nhất ~2~ dãy không giảm thành ~1~ dãy không giảm ~(~dãy sau khi hợp nhất chứa tất cả phần tử của ~2~ dãy ban đầu và không làm thay đổi thứ tự gốc của chúng~)~

Từ ~2~ nhận xét trên, với mỗi số ~x~ thỏa mãn ~0 \leq x < k~, ta lọc ra các phần tử ~a_j~ sao cho ~a_j \equiv x \pmod{k}~ rồi kiểm tra xem liệu chúng có được xếp theo thứ tự không giảm trong dãy ~a~ ban đầu. Nếu điều kiện này đúng với mọi ~x~ ~(0 \leq x < k)~ thì đáp án là Yes, không thì đáp án là No.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int LOG = 22; 
const int MAX = 2e5+5;
const int MOD = 1e9+7;
const int SQRT = 400;
const ll INF = 2e9;
const ll lon = 1e18;

int n, k;
int a[MAX];
vector<pii> temp;

bool check() {
    sort(all(temp));
    fo(i, 1, n) {
        if(temp[i].fi != temp[i-1].fi) continue;
        if(a[temp[i].se] < a[temp[i-1].se]) return false;
    }
    return true;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    if(t > 100) cout << "cac\n";
    while(t--) {
        cin >> n >> k;
        fo(i, 1, n) cin >> a[i];

        temp.clear();
        temp.pb(mk(-1, -1));
        fo(i, 1, n) temp.pb(mk(a[i] % k, i)); 

        if(check()) cout << "Yes";
        else cout << "No";
        cout << "\n";
    }
}