programming.in.th · ข้อ 2004

คู่ที่ได้ยินกัน: หมุนพิกัดเพื่อแยกเงื่อนไขสองแกนที่พัวพันกันออกจากกัน

ข้อที่ยกของจากบทผลรวมสะสมกับต้นไม้เฟนวิกมาใช้จริงทั้งชุด แกนของมันคือเอกลักษณ์บรรทัดเดียวที่ทำให้เงื่อนไขซึ่งผูกสองแกนไว้ด้วยกัน กลายเป็นเงื่อนไขที่ตรวจแยกกันได้ กับบทเรียนว่าทำไมท่าเดียวกันนี้ถึงช่วยอะไรไม่ได้เลยบนกระดานสามมิติ

โจทย์ · ตุ๊กตาสัตว์คู่ไหนได้ยินเสียงกันบ้าง

เมอโกกับสลาฟโกจะเล่นเกมด้วยกัน เริ่มจากเลือกกระดานหนึ่งใบจากสามแบบ คือกระดานที่ช่องเรียงเป็นแถวเดียว (1 มิติ) เรียงเป็นตาราง (2 มิติ) หรือเรียงเป็นลูกบาศก์ (3 มิติ) จากนั้นเมอโกวางตุ๊กตาสัตว์ตัวจิ๋ว N ตัวลงไปในช่องต่าง ๆ ช่องหนึ่งซ้อนกันหลายตัวก็ได้

ระยะห่างระหว่างสองช่องคือจำนวนก้าวที่น้อยที่สุดที่ตุ๊กตาต้องเดินจากช่องหนึ่งไปอีกช่องหนึ่ง โดยหนึ่งก้าวคือขยับไปช่องที่ติดกัน ตุ๊กตาสองตัวได้ยินเสียงกันเมื่อช่องของมันห่างกันไม่เกิน D งานของสลาฟโกคือนับว่ามีตุ๊กตากี่คู่ที่ได้ยินเสียงกัน

เดินได้ทีละก้าวไปช่องที่ติดกันแปลว่าระยะห่างคือผลบวกของส่วนต่างในแต่ละแกน บนกระดานสองมิติ ช่อง (5, 2) กับช่อง (8, 4) จึงห่างกัน |5 − 8| + |2 − 4| = 5 ก้าว ไม่ใช่ระยะเส้นตรง ระยะแบบนี้มีชื่อว่า ระยะแมนฮัตตัน (Manhattan distance ตั้งตามผังถนนของเกาะแมนฮัตตันที่ตัดกันเป็นบล็อกสี่เหลี่ยม จะข้ามจากบล็อกหนึ่งไปอีกบล็อกต้องเดินไปตามถนน ทะลุตึกไม่ได้)

ค่า M ที่ต่างกันคนละโลกในสามกระดานไม่ใช่เรื่องบังเอิญ มันคือคำใบ้ที่โจทย์แปะไว้ให้ตั้งแต่ต้น ว่าสามกระดานนี้ไม่ได้ตั้งใจให้แก้ด้วยวิธีเดียวกัน

ตัวอย่างที่สามคือแปดมุมของลูกบาศก์ที่มีด้านยาว 10 คู่ที่ห่างกันพอดี 10 คือคู่ที่อยู่ปลายขอบเดียวกัน ลูกบาศก์มีขอบ 12 เส้น คำตอบจึงเป็น 12 ส่วนคู่ที่อยู่ตรงข้ามกันบนหน้าเดียวกันห่าง 20 ก้าว เกินไปแล้ว

ตรงไหนที่ทำให้ข้อนี้ไม่ง่าย

วิธีที่ตรงที่สุดคือไล่ดูทุกคู่ ซึ่งเขียนสามบรรทัดจบและถูกต้องแน่นอน ปัญหาคือจำนวนคู่ ที่ N = 100 000 มีคู่ทั้งหมด N(N−1)/2 คือราว 4,999,950,000 คู่ ห้าพันล้านครั้งของงานเบา ๆ ยังไงก็ไม่จบใน 4 วินาที และนี่คือเหตุผลที่โจทย์กำชับเรื่องจำนวนเต็ม 64 บิต เพราะคำตอบเองก็ทะลุ int ได้ในกรณีที่ทุกคู่ได้ยินกันหมด

กระดานหนึ่งมิติพอมองออกไม่ยากว่าเรียงแล้วกวาดก็จบ ที่หนักคือกระดานสองมิติ เพราะเงื่อนไข |Δx| + |Δy| ≤ D มีค่าสัมบูรณ์สองก้อนบวกกัน มันไม่ใช่เงื่อนไขที่แยกเป็นแกน x อย่างหนึ่งแกน y อย่างหนึ่งได้ บริเวณที่ได้ยินถึงกันจึงไม่ใช่กรอบสี่เหลี่ยมที่โครงสร้างข้อมูลทั่วไปชอบ แต่เป็นสี่เหลี่ยมข้าวหลามตัดที่วางเอียงอยู่กลางตาราง

ลองเอง · หมุนกระดานดู

นี่คือกระดานจากตัวอย่างที่สอง กดที่ตุ๊กตาตัวไหนก็ได้เพื่อเลือกมัน พื้นที่สีเขียวคือช่องทั้งหมดที่ได้ยินเสียงตัวนั้น เลื่อนแถบเพื่อเปลี่ยนค่า D แล้วกดปุ่มหมุนเพื่อดูกระดานเดิมในมุมใหม่

ลองเล่นดูก่อนนะครับ พอมีคำตอบในใจแล้ว ค่อยไปดูเฉลย

เฉลย ตอนที่ 1 · กระดานหนึ่งมิติ

// กระดานหนึ่งมิติ: เรียงแล้วเดินสองตัวชี้
sort(x.begin(), x.end());
ll ans = 0;
int j = 0;
for (int i = 0; i < N; i++) {
    while ((ll)x[i] - x[j] > D) j++;   // j เดินหน้าอย่างเดียว ไม่เคยถอยกลับ
    ans += i - j;                      // ทุกตัวตั้งแต่ j ถึง i-1 อยู่ในระยะได้ยิน
}

เฉลย ตอนที่ 2 · สองมิติ กับเอกลักษณ์บรรทัดเดียว

// กระดานสองมิติ: หมุนพิกัดก่อน แล้วกวาดตาม u พร้อมนับ v ด้วย BIT
vector<pair<int,int>> q(N);
for (int i = 0; i < N; i++)
    q[i] = {p[i].first + p[i].second, p[i].first - p[i].second + M};   // (u, v)
sort(q.begin(), q.end());

BIT bit;
bit.init(2 * M + 2);
ll ans = 0;
int j = 0;
for (int i = 0; i < N; i++) {
    while ((ll)q[i].first - q[j].first > D) { bit.add(q[j].second, -1); j++; }
    ans += bit.range((int)max<ll>(1, q[i].second - D),
                     (int)min<ll>(2 * M + 1, q[i].second + D));
    bit.add(q[i].second, 1);
}

เฉลย ตอนที่ 3 · สามมิติ ที่การหมุนช่วยไม่ได้แล้ว

// กระดานสามมิติ: M เล็กมาก ทำผลรวมสะสมสองมิติเก็บไว้ทุกชั้น z
for (auto& a : p) {
    int u = a[0] + a[1], v = a[0] - a[1] + M;
    pre[a[2]][at(u, v)]++;                       // นับตัวลงชั้นของมันก่อน
}
for (int z = 1; z <= M; z++) {                   // แล้วค่อยทำผลรวมสะสมทีละชั้น
    auto& g = pre[z];
    for (int u = 1; u <= U + 1; u++)
        for (int v = 1; v <= V + 1; v++)
            g[at(u, v)] += g[at(u - 1, v)] + g[at(u, v - 1)] - g[at(u - 1, v - 1)];
}

ll ans = 0;
for (auto& a : p) {
    int u = a[0] + a[1], v = a[0] - a[1] + M, z = a[2];
    for (int zz = max(1LL, z - D); zz <= min<ll>(M, z + D); zz++) {
        ll r = D - abs(zz - z);                  // ระยะที่เหลือให้ใช้บนระนาบ xy
        if (r > 2 * M) r = 2 * M;
        ans += box(zz, u - (int)r, v - (int)r, u + (int)r, v + (int)r);
    }
}
ans = (ans - N) / 2;                             // ตัวเองถูกนับด้วย และทุกคู่ถูกนับสองครั้ง

โค้ดเต็มและเวลาที่วัดได้

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int B, N, M;
ll D;

/* ---------- กระดานหนึ่งมิติ: เรียงแล้วเดินสองตัวชี้ ---------- */
ll solve1(vector<int>& x) {
    sort(x.begin(), x.end());
    ll ans = 0;
    int j = 0;
    for (int i = 0; i < N; i++) {
        while ((ll)x[i] - x[j] > D) j++;
        ans += i - j;
    }
    return ans;
}

/* ---------- กระดานสองมิติ: หมุน 45 องศา แล้วกวาดด้วย BIT ---------- */
struct BIT {
    vector<int> t;
    int n;
    void init(int n_) { n = n_; t.assign(n + 1, 0); }
    void add(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; }
    int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    int range(int a, int b) {
        a = max(a, 1); b = min(b, n);
        return b < a ? 0 : sum(b) - sum(a - 1);
    }
};

ll solve2(vector<pair<int,int>>& p) {
    vector<pair<int,int>> q(N);
    for (int i = 0; i < N; i++)
        q[i] = {p[i].first + p[i].second, p[i].first - p[i].second + M};
    sort(q.begin(), q.end());

    BIT bit;
    bit.init(2 * M + 2);
    ll ans = 0;
    int j = 0;
    for (int i = 0; i < N; i++) {
        while ((ll)q[i].first - q[j].first > D) { bit.add(q[j].second, -1); j++; }
        int lo = (int)max<ll>(1, q[i].second - D);
        int hi = (int)min<ll>(2 * M + 1, q[i].second + D);
        ans += bit.range(lo, hi);
        bit.add(q[i].second, 1);
    }
    return ans;
}

/* ---------- กระดานสามมิติ: ผลรวมสะสมสองมิติ เก็บไว้ทุกชั้น ---------- */
ll solve3(vector<array<int,3>>& p) {
    const int U = 2 * M + 1;                 // u = x + y อยู่ในช่วง 2..2M
    const int V = 2 * M + 1;                 // v = x - y + M อยู่ในช่วง 1..2M-1
    vector<vector<int>> pre((size_t)M + 1, vector<int>((size_t)(U + 2) * (V + 2), 0));
    auto at = [&](int u, int v) { return u * (V + 2) + v; };

    for (auto& a : p) {
        int u = a[0] + a[1], v = a[0] - a[1] + M;
        pre[a[2]][at(u, v)]++;
    }
    for (int z = 1; z <= M; z++) {
        auto& g = pre[z];
        for (int u = 1; u <= U + 1; u++)
            for (int v = 1; v <= V + 1; v++)
                g[at(u, v)] += g[at(u - 1, v)] + g[at(u, v - 1)] - g[at(u - 1, v - 1)];
    }
    auto box = [&](int z, int u1, int v1, int u2, int v2) {
        u1 = max(u1, 1); v1 = max(v1, 1);
        u2 = min(u2, U + 1); v2 = min(v2, V + 1);
        if (u1 > u2 || v1 > v2) return 0;
        auto& g = pre[z];
        return g[at(u2, v2)] - g[at(u1 - 1, v2)] - g[at(u2, v1 - 1)] + g[at(u1 - 1, v1 - 1)];
    };

    ll ans = 0;
    for (auto& a : p) {
        int u = a[0] + a[1], v = a[0] - a[1] + M, z = a[2];
        int zlo = (int)max<ll>(1, z - D), zhi = (int)min<ll>(M, z + D);
        for (int zz = zlo; zz <= zhi; zz++) {
            ll r = D - abs(zz - z);
            if (r < 0) continue;
            if (r > 2 * M) r = 2 * M;
            ans += box(zz, u - (int)r, v - (int)r, u + (int)r, v + (int)r);
        }
    }
    return (ans - N) / 2;
}

int main() {
    if (scanf("%d %d %lld %d", &B, &N, &D, &M) != 4) return 0;
    if (B == 1) {
        vector<int> x(N);
        for (int i = 0; i < N; i++) scanf("%d", &x[i]);
        printf("%lld\n", solve1(x));
    } else if (B == 2) {
        vector<pair<int,int>> p(N);
        for (int i = 0; i < N; i++) scanf("%d %d", &p[i].first, &p[i].second);
        printf("%lld\n", solve2(p));
    } else {
        vector<array<int,3>> p(N);
        for (int i = 0; i < N; i++) scanf("%d %d %d", &p[i][0], &p[i][1], &p[i][2]);
        printf("%lld\n", solve3(p));
    }
    return 0;
}

// ตัวตรวจแบบซื่อ ๆ ไล่ทุกคู่ ใช้ได้แค่ N หลักพัน
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int B, N, M;
    ll D;
    if (scanf("%d %d %lld %d", &B, &N, &D, &M) != 4) return 0;
    vector<array<int,3>> p(N, {0, 0, 0});
    for (int i = 0; i < N; i++)
        for (int k = 0; k < B; k++) scanf("%d", &p[i][k]);
    ll ans = 0;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++) {
            ll d = 0;
            for (int k = 0; k < B; k++) d += abs(p[i][k] - p[j][k]);
            if (d <= D) ans++;
        }
    printf("%lld\n", ans);
    return 0;
}

อีกทางสำหรับสามมิติ · CDQ divide and conquer

เฉลยของข้อนี้จัดการมิติที่สามด้วยการหมุนกระดาน ซึ่งใช้ได้เพราะรูปของโจทย์เอื้อให้ทำ แต่มีท่ามาตรฐานสำหรับปัญหารูปนี้ที่ใช้ได้โดยไม่ต้องพึ่งความพอดีของโจทย์ และคุ้มที่จะรู้เพราะมันเป็นท่าประจำของทุกโจทย์ที่ต้องนับคู่ที่เล็กกว่ากันครบทุกมิติ

ท่านั้นชื่อ CDQ divide and conquer และแนวคิดของมันคือลดจำนวนมิติ ด้วยการแบ่งครึ่ง ไม่ใช่ด้วยการหมุนหรือการเปลี่ยนพิกัด

ทำไมการแบ่งครึ่งลดมิติได้

ปัญหาคือนับคู่ที่ x เล็กกว่า และ y เล็กกว่า และ z เล็กกว่า พร้อมกันทั้งสามมิติ เริ่มด้วยการเรียงตาม x แล้วแบ่งอาเรย์เป็นสองครึ่ง

ตรงนี้คือหัวใจ คู่ที่เราต้องนับแบ่งได้เป็นสามพวก คู่ที่อยู่ในครึ่งซ้ายทั้งคู่ คู่ที่อยู่ในครึ่งขวาทั้งคู่ และคู่ที่คร่อมสองครึ่ง สองพวกแรกคือปัญหาเดิมที่เล็กลง จึงเรียกซ้ำได้ ส่วนพวกที่สามมิติแรกไม่ต้องเช็คอีกเลย เพราะทุกจุดในครึ่งซ้ายมี x เล็กกว่าทุกจุดในครึ่งขวาอยู่แล้วโดยการเรียง

พอมิติแรกหายไป งานที่เหลือคือปัญหาสองมิติ ซึ่งเราแก้ได้ด้วยท่าที่บทนี้ใช้อยู่แล้ว คือกวาดตาม y พร้อมถามเฟนวิกบน z และเพราะการเรียกซ้ำคืนของที่เรียงตาม y มาให้แล้วทั้งสองครึ่ง การกวาดจึงทำพร้อมกับการรวมกลับแบบ merge ได้เลย ไม่ต้องเรียงใหม่

ต้นทุนจึงเป็น O(n log² n) คือแบ่งครึ่ง log n ชั้น ชั้นละ n log n จากเฟนวิก ที่ n = 200,000 ผมรันโค้ดข้างล่างจริง ได้ 0.23 วินาที เทียบกับการไล่ทุกคู่ที่เป็นสองหมื่นล้านครั้ง

// CDQ divide and conquer: นับคู่ที่เล็กกว่ากันครบทั้งสามมิติ
// ให้จุด n จุด แต่ละจุดมี (x, y, z) นับจำนวนคู่ที่ xi<xj และ yi<yj และ zi<zj
//
// ข้อกำหนดของโค้ดชุดนี้: ค่า x ต้องไม่ซ้ำกัน
// เพราะการแบ่งครึ่งใช้ "ลำดับหลังเรียงตาม x" แทนการเทียบ x จริง ถ้ามี x ซ้ำ
// สองจุดที่ x เท่ากันอาจไปอยู่คนละครึ่งแล้วถูกนับ ซึ่งผิดเงื่อนไข xi<xj
// กรณีมี x ซ้ำต้องจับกลุ่ม x เท่ากันมาหักออกอีกชั้น ซึ่งไม่รวมในโค้ดนี้
#include <bits/stdc++.h>
using namespace std;

struct P { int x, y, z; };

int NZ;
vector<int> fen;
void fupd(int i, int v) { for (++i; i <= NZ; i += i & -i) fen[i] += v; }
int fqry(int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += fen[i]; return s; }

long long answer = 0;
vector<P> a, buf;

void cdq(int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    cdq(lo, mid);
    cdq(mid, hi);
    // ออกจากสองบรรทัดบน ทั้งสองครึ่งเรียงตาม y แล้ว รวมกลับแบบ merge พร้อมนับ
    // ทุกจุดในครึ่งซ้ายมี x เล็กกว่าทุกจุดในครึ่งขวาแน่นอน มิติแรกจึงไม่ต้องเช็คอีก
    int i = lo, j = mid, k = lo;
    while (i < mid || j < hi) {
        if (j >= hi || (i < mid && a[i].y < a[j].y)) {
            fupd(a[i].z, 1);                  // จุดซ้ายที่ y เล็กกว่า ใส่ลงเฟนวิกไว้
            buf[k++] = a[i++];
        } else {
            answer += fqry(a[j].z - 1);       // จุดขวา ถามว่ามีซ้ายกี่ตัวที่ z เล็กกว่า
            buf[k++] = a[j++];
        }
    }
    for (int t = lo; t < mid; t++) fupd(a[t].z, -1);   // ล้างเฟนวิกให้ว่างก่อนออกจากชั้นนี้
    for (int t = lo; t < hi; t++) a[t] = buf[t];
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    a.resize(n);
    buf.resize(n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
    // ย่อ z ให้เป็นดัชนีติดกัน เฟนวิกจึงมีขนาดพอดีกับจำนวนค่าที่ต่างกันจริง
    vector<int> zs;
    for (const P& p : a) zs.push_back(p.z);
    sort(zs.begin(), zs.end());
    zs.erase(unique(zs.begin(), zs.end()), zs.end());
    for (P& p : a) p.z = (int)(lower_bound(zs.begin(), zs.end(), p.z) - zs.begin());
    NZ = (int)zs.size() + 2;
    fen.assign(NZ + 2, 0);

    sort(a.begin(), a.end(), [](const P& p, const P& q) { return p.x < q.x; });
    cdq(0, n);
    printf("%lld\n", answer);
    return 0;
}

// ตัวตรวจอิสระของ CDQ: ไล่ทุกคู่แล้วเช็คสามเงื่อนไขตรง ๆ
// ไม่มีการแบ่งครึ่ง ไม่มีเฟนวิก จึงไม่ได้ทดสอบข้ออ้างของท่านั้นเลย
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<array<int, 3>> p(n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", &p[i][0], &p[i][1], &p[i][2]);
    long long c = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && p[i][0] < p[j][0] && p[i][1] < p[j][1] && p[i][2] < p[j][2]) c++;
    printf("%lld\n", c);
    return 0;
}

สรุปบรรทัดเดียว

|a| + |b| = max(|a+b|, |a−b|) คือทั้งหมดที่ข้อนี้ต้องการ มันเปลี่ยนเงื่อนไขที่พัวพันสองแกน ให้กลายเป็นสองเงื่อนไขที่ตรวจแยกกันได้ ส่วนกระดานสามมิติที่หมุนไม่ได้ โจทย์ก็ชดเชยให้ด้วยกระดานที่เล็กจนทำตารางค้างไว้ได้

แหล่งที่มา

1. โจทย์ Pairs บน programming.in.th ข้อ 2004 programming.in.th/tasks/2004 (สืบค้น 6 กันยายน 2026)
2. ต้นทางของโจทย์คือ International Olympiad in Informatics 2007 วันแข่งที่สอง จัดที่เมืองซาเกร็บ ประเทศโครเอเชีย 15 ถึง 22 สิงหาคม 2007