Агуулгыг алгасах

Гүдгэр бүрхүүлийн арга ба Ли Чаогийн мод

Дараах бодлогыг авч үзье. $n$ хот байна. Та $1$-р хотоос $n$-р хот руу машинаар аялахыг хүсэж байна. Үүний тулд та бензин худалдаж авах хэрэгтэй. $k$-р хотод нэг литр бензин $cost_k$ өртөгтэй нь мэдэгдэж байна. Эхэндээ таны түлшний сав хоосон бөгөөд та километр тутамд нэг литр бензин зарцуулна. Хотууд нэг шулуун дээр өсөх дарааллаар байрлах ба $k$-р хот $x_k$ координаттай. Мөн та $k$-р хотод орохын тулд $toll_k$ хураамж төлөх ёстой. Таны даалгавар бол аялалыг хамгийн бага боломжит өртгөөр хийх явдал юм. Шийдийг динамик программчлалаар тооцоолж болох нь илэрхий:

$$dp_i = toll_i+\min\limits_{j<i}(cost_j \cdot (x_i - x_j)+dp_j)$$

Гэнэн арга танд $O(n^2)$ complexity өгөх ба үүнийг $O(n \log n)$ эсвэл $O(n \log [C \varepsilon^{-1}])$ болгон сайжруулж болно, энд $C$ нь боломжит хамгийн том $|x_i|$, $\varepsilon$ нь $x_i$-г авч үзэх нарийвчлал (бүхэл тооны хувьд $\varepsilon = 1$ бөгөөд ихэвчлэн ийм байдаг). Үүний тулд бодлогыг олонлогт $k \cdot x + b$ шугаман функцүүдийг нэмэх, мөн тодорхой $x$ цэг дэх функцүүдийн хамгийн бага утгыг олох болтол хураах боломжтойг анзаарах хэрэгтэй. Энд ашиглаж болох хоёр үндсэн арга байна.

Гүдгэр бүрхүүлийн арга

Энэ аргын санаа бол шугаман функцүүдийн доод гүдгэр бүрхүүлийг хөтлөх явдал юм. Үнэндээ тэдгээрийг шугаман функц гэж биш, харин хавтгай дээрх $(k;b)$ цэгүүд гэж авч үзэх нь арай илүү тохиромжтой байх бөгөөд ингэснээр бид өгөгдсөн $(x;1)$ цэгтэй хамгийн бага скаляр үржвэртэй цэгийг олох ёстой болно, өөрөөр хэлбэл энэ цэгийн хувьд $kx+b$ минимумчлагдах ба энэ нь анхны бодлоготой ижил юм. Ийм минимум нь доор харагдаж байгаачлан эдгээр цэгүүдийн доод гүдгэр дугтуй дээр зайлшгүй байх болно:

доод гүдгэр бүрхүүл

Гүдгэр бүрхүүл дээрх цэгүүд ба бүрхүүлийн ирмэгүүдийн нормаль векторуудыг хадгалах хэрэгтэй. $(x;1)$ асуулга ирэхэд та түүнтэй хоорондын өнцгөөрөө хамгийн ойр байх нормаль векторыг олох хэрэгтэй болох ба тэгвэл оновчтой шугаман функц түүний үзүүрийн цэгүүдийн нэгэнд харгалзана. Үүнийг харахын тулд $(x;1)$-тэй тогтмол скаляр үржвэртэй цэгүүд $(x;1)$-д ортогональ шулуун дээр оршдогийг анзаарах хэрэгтэй, тиймээс оновчтой шугаман функц нь $(x;1)$-ийн нормальтай коллинеар байх гүдгэр бүрхүүлийн шүргэгч бүрхүүлийг шүргэх цэг дэх функц байна. Энэ цэг нь түүний зүүн ба баруун талд орших ирмэгүүдийн нормалиуд $(x;1)$-ийн өөр өөр тал руу чиглэсэн байх цэг юм.

Энэ арга нь шугаман функц нэмэх асуулгууд $k$-ийн хувьд монотон байх үед, эсвэл бид офлайнаар ажиллаж байвал буюу эхлээд бүх шугаман функцийг нэмээд дараа нь асуулгад хариулж болох үед хэрэгтэй. Тиймээс бид хот/бензиний бодлогыг ийм аргаар бодож чадахгүй. Энэ нь онлайн асуулга боловсруулахыг шаардана. Гэвч онлайн асуулгатай ажиллах болбол бүх зүйл хүндэрч, зохих гүдгэр бүрхүүлийг хэрэгжүүлэхийн тулд ямар нэг олонлогийн өгөгдлийн бүтэц ашиглах хэрэгтэй болно. Гэвч онлайн аргыг түүний хүндрэлээс болж, мөн хоёр дахь арга (Ли Чаогийн мод) бодлогыг хамаагүй илүү энгийнээр бодох боломж олгодог тул энэ өгүүлэлд авч үзэхгүй. Энэ аргыг квадрат язгуурын задаргаагаар онлайнаар ч төвөггүй ашиглаж болохыг дурдах нь зүйтэй. Өөрөөр хэлбэл шинэ $\sqrt n$ шулуун тутамд гүдгэр бүрхүүлийг шинээр дахин байгуулна.

Энэ аргыг хэрэгжүүлэхийн тулд геометрийн зарим туслах функцээс эхлэх хэрэгтэй, энд бид C++-ийн комплекс тооны төрлийг ашиглахыг санал болгож байна.

typedef int ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
    return (conj(a) * b).x();
}

ftype cross(point a, point b) {
    return (conj(a) * b).y();
}

Энд бид шугаман функцүүдийг нэмэх үед тэдгээрийн $k$ зөвхөн өсдөг бөгөөд бид хамгийн бага утгыг олохыг хүсэж байна гэж үзнэ. Бид цэгүүдийг $hull$ вектор, нормаль векторуудыг $vecs$ векторт хадгална. Шинэ цэг нэмэхдээ бид гүдгэр бүрхүүл дэх сүүлийн ирмэг ба гүдгэр бүрхүүл дэх сүүлийн цэгээс шинэ цэг рүү чиглэсэн векторын хооронд үүсэх өнцгийг харах хэрэгтэй. Энэ өнцөг цагийн зүүний эсрэг чиглэсэн байх ёстой, өөрөөр хэлбэл бүрхүүл дэх сүүлийн нормаль вектор (бүрхүүлийн дотор чиглэсэн) ба сүүлийн цэгээс шинэ цэг рүү чиглэсэн векторын скаляр үржвэр сөрөг биш байх ёстой. Энэ нь үнэн биш л бол бид гүдгэр бүрхүүл дэх сүүлийн цэгийг харгалзах ирмэгийнх нь хамт устгах ёстой.

vector<point> hull, vecs;

void add_line(ftype k, ftype b) {
    point nw = {k, b};
    while(!vecs.empty() && dot(vecs.back(), nw - hull.back()) < 0) {
        hull.pop_back();
        vecs.pop_back();
    }
    if(!hull.empty()) {
        vecs.push_back(1i * (nw - hull.back()));
    }
    hull.push_back(nw);
}
Одоо ямар нэг цэг дэх хамгийн бага утгыг авахын тулд бид гүдгэр бүрхүүл дэх $(x;1)$-ээс цагийн зүүний эсрэг чиглэсэн эхний нормаль векторыг олно. Ийм ирмэгийн зүүн үзүүрийн цэг нь хариулт байх болно. $a$ вектор $b$ вектороос цагийн зүүний эсрэг чиглээгүй эсэхийг шалгахын тулд бид тэдгээрийн вектор үржвэр $[a,b]$ эерэг эсэхийг шалгах хэрэгтэй. 
int get(ftype x) {
    point query = {x, 1};
    auto it = lower_bound(vecs.begin(), vecs.end(), query, [](point a, point b) {
        return cross(a, b) > 0;
    });
    return dot(query, hull[it - vecs.begin()]);
}

Ли Чаогийн мод

Танд аль ч хоёр нь хамгийн ихдээ нэг удаа огтлолцох функцүүдийн олонлог өгөгдсөн гэж үзье. Хэрчмийн модны орой бүрд ямар нэг функцийг, хэрэв бид үндэснээс навч руу явбал замд тааралдсан функцүүдийн нэг нь тэр навч дахь хамгийн бага утгыг өгөх нь баталгаатай байхаар хадгалъя. Үүнийг хэрхэн байгуулахыг үзье.

Бид $[l,r)$ хагас хэрчимд харгалзах ямар нэг оройд байгаа бөгөөд тэнд $f_{old}$ функц хадгалагдсан ба бид $f_{new}$ функцийг нэмж байна гэж үзье. Тэгвэл огтлолцлын цэг $[l;m)$ эсвэл $[m;r)$-д байх ба энд $m=\left\lfloor\tfrac{l+r}{2}\right\rfloor$. Бид үүнийг $l$ ба $m$ цэгүүд дэх функцүүдийн утгыг харьцуулах замаар үр ашигтай олж чадна. Хэрэв давамгайлах функц өөрчлөгдвөл тэр нь $[l;m)$-д, эс бөгөөс $[m;r)$-д байна. Одоо огтлолцолгүй хэрчмийн хагасын хувьд бид доод функцийг сонгож, одоогийн оройд бичнэ. Энэ нь үргэлж $m$ цэгт доод байх функц байхыг та харж болно. Үүний дараа бид дээд байсан функцтэйгээр хэрчмийн нөгөө хагас руу рекурсивээр явна. Таны харж байгаагаар энэ нь хэрчмийн эхний хагаст зөв байдлыг хадгалах ба нөгөөд нь зөв байдал рекурсив дуудлагын явцад хадгалагдана. Ингэснээр бид функц нэмж, цэг дэх хамгийн бага утгыг $O(\log [C\varepsilon^{-1}])$-д шалгаж чадна.

Шинэ функц нэмэх үед оройд юу болж байгаагийн дүрслэл энд байна:

Ли Чаогийн модны орой

Одоо хэрэгжүүлэлт рүү орьё. Дахин хэлэхэд бид шугаман функцүүдийг хадгалахад комплекс тоо ашиглана.

typedef long long ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
    return (conj(a) * b).x();
}

ftype f(point a,  ftype x) {
    return dot(a, {x, 1});
}
Бид функцүүдийг $line$ массивт хадгалж, хэрчмийн модны хоёртын индексжүүлэлтийг ашиглана. Хэрэв та үүнийг том тоо эсвэл double дээр ашиглахыг хүсвэл динамик хэрчмийн мод ашиглах хэрэгтэй. Хэрчмийн модыг өгөгдмөл утгуудаар, жишээ нь $0x + \infty$ шулуунуудаар эхлүүлэх ёстой.

const int maxn = 2e5;

point line[4 * maxn];

void add_line(point nw, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(line[v], l);
    bool mid = f(nw, m) < f(line[v], m);
    if(mid) {
        swap(line[v], nw);
    }
    if(r - l == 1) {
        return;
    } else if(lef != mid) {
        add_line(nw, 2 * v, l, m);
    } else {
        add_line(nw, 2 * v + 1, m, r);
    }
}
Одоо ямар нэг $x$ цэг дэх минимумыг авахын тулд бид зүгээр л тэр цэг хүртэлх зам дагуух хамгийн бага утгыг сонгоно. 
ftype get(int x, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    if(r - l == 1) {
        return f(line[v], x);
    } else if(x < m) {
        return min(f(line[v], x), get(x, 2 * v, l, m));
    } else {
        return min(f(line[v], x), get(x, 2 * v + 1, m, r));
    }
}

Бодлогууд