คำอธิบายวิธีทำพร้อม code สำหรับข้อ toi21_crystal

สรุปโจทย์

มีจักรวาลอยู่ $U$ จักรวาล และมี Crystal $N$ อัน
แต่ละอันมี

$p[i]$ : ตำแหน่ง
$w[i]$ : จักรวาล
$t[i]$ : เวลา

ต้องเก็บ Crystal เรียงตาม

$p[i]$ จากน้อยไปมาก
$t[i]$ จากน้อยไปมาก

ขณะที่อยู่ในจักรวาล $j$ สามารถทำได้ 1 อย่าง จาก 2 operations

เก็บ Crystal ในจักรวาลปัจจุบัน (ข้ามบางอันได้)
ย้ายไปจักรวาลอื่น แต่ต้องเสีย Crystal $K$ อัน (ถ้ามีเก็บมาแล้ว ≥ $K$ )

โจทย์: หาว่าเก็บ Crystal ได้มากสุดเท่าไร

Prerequisites

LIS
Fenwick Tree(ไม่จำเป็นต้องใช้ แต่เราจะใช้วิธีที่ใช้ Fenwick Tree)
Sweep line
Coordinate Compression

วิธีทำ

เราสามารถสังเกตเห็นได้ว่าถ้า $U=1$ แล้ว sort Crystal ด้วย $p[i]$ จากน้อยไปมาก จะเห็นได้ว่าเป็นโจทย์หาความยาว LIS ธรรมดา

ดังนั้นเราควรมี array $v$ ที่มีการ sort Crystal ด้วย $p_i$ จากน้อยไปมากแล้วทำ Sweepline ไปตามแต่ละตัวของ $v$

(หลังจากนี้การพูดถึง Crystal ที่ $i$ หมายถึง Crystal ที่ $i$ ของ array $v$ )
สมมติว่าเราอยากเก็บ Crystal ที่ $i$ มี 2 case คือ

Crystal ล่าสุดก่อนที่เราเก็บ Crystal $i$ อยู่จักรวาลเดียวกับ Crystal $i$
Crystal ล่าสุดก่อนที่เราเก็บ Crystal $i$ ไม่ได้อยู่จักรวาลเดียวกับ Crystal $i$

พิจารณา case ที่ 1 จะได้ว่าต้องหาจำนวน Crystal มากที่สุด(ให้ $c_1$ แทนค่านี้)โดยที่ Crystal ล่าสุดก่อนที่เราเก็บ Crystal $i$ อยู่จักรวาลเดียวกันกับ Crystal $i$ และ Crystal นั้นมีค่า $t<t[i]$

พิจารณา case ที่ 2 จะได้ว่าต้องหาจำนวน Crystal มากที่สุด(ให้ $c_2$ แทนค่านี้)โดยที่ Crystal ล่าสุดก่อนที่เราเก็บ Crystal $i$ อยู่คนละจักรวาลเดียวกันกับ Crystal $i$ และ Crystal นั้นมีค่า $t<t[i]$

จะได้ว่า ถ้าเราอยากเก็บ Crystal ที่ $i$ จะเก็บได้มากสุดคือ $\max(c_1,c_2-k)$ +1

เห็นได้ว่านี่ก็คือโจทย์ LIS โดยเราจะใช้ Fenwick tree เป็น data structure นี้ในการทำ LIS (ถ้าไม่รู้วิธีทำให้ลองศึกษาจากบทความนี้ Longest Increasing Subsequence using BIT
note: ในบทความนี้จะใช้ coordinate compression ด้วยซึ่งเป็นสิ่งที่เราจำเป็นต้องใช้)

Solution code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 1e5 + 5;
const int U = 1e3 + 5;

int u, k, n, ans;
map<int, int> com;
set<int> ins;
tuple<int, int, int> a[N];  // {t, w, p}

struct Fenwick {
    int fw[N];

    void update(int idx, int val) {
        while (idx < N) {
            fw[idx] = max(fw[idx], val);
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res = max(res, fw[idx]);
            idx -= idx & -idx;
        }
        return res;
    }
} fenwick[U];

int32_t main() {
	cin.tie(NULL)->sync_with_stdio(false);
    cin >> u >> k >> n;
    for (int i = 1; i <= n; i++) {
        auto& [t, w, p] = a[i];
        cin >> p >> w >> t;
        ins.emplace(p);
    }

    vector<int> temp(ins.begin(), ins.end());
    for (size_t i = 0; i < temp.size(); i++) {
        com[temp[i]] = i + 1;
    }

    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i++) {
        auto [t, w, pp] = a[i];
        int p = com[pp];

        int x1 = fenwick[w].query(p - 1) + 1;
        int x2 = fenwick[U - 1].query(p - 1) + 1 - k;
        int x  = max(x1, x2);

        fenwick[U - 1].update(p, x);
        fenwick[w].update(p, x);

        ans = max(ans, x);
    }

    cout << ans << "\n";
    return 0;
}

Total Time Complexity: $O(n log n)$