কনভেক্স হাল ট্রিক এবং লি চাও ট্রি#

নিচের সমস্যাটা দেখো। $n$ টি শহর আছে। তুমি গাড়িতে করে শহর ১ থেকে শহর $n$-এ যেতে চাও। এর জন্য তোমাকে কিছু পেট্রোল কিনতে হবে। জানা আছে যে $k$-তম শহরে এক লিটার পেট্রোলের দাম $cost_k$। শুরুতে তোমার ফুয়েল ট্যাঙ্ক খালি আর তুমি প্রতি কিলোমিটারে এক লিটার পেট্রোল খরচ করো। শহরগুলো একই রেখায় ক্রমবর্ধমান ক্রমে আছে, যেখানে $k$-তম শহরের স্থানাঙ্ক $x_k$। এছাড়াও $k$-তম শহরে ঢুকতে তোমাকে $toll_k$ দিতে হবে। তোমার কাজ হলো সবচেয়ে কম খরচে ভ্রমণ করা। স্পষ্টতই সমাধানটা ডায়নামিক প্রোগ্রামিং (DP) দিয়ে বের করা যায়:

$$dp_i = toll_i+\min\limits_{jনেইভ পদ্ধতিতে $O(n^2)$ কমপ্লেক্সিটি হবে, যেটা $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$ ন্যূনতম যা মূল সমস্যার একই। এই ন্যূনতম অবশ্যই এই বিন্দুগুলোর লোয়ার কনভেক্স এনভেলোপে থাকবে যেমনটি নিচে দেখা যায়:

lower convex hull

কনভেক্স হালের বিন্দু আর হালের এজগুলোর নরমাল ভেক্টর রাখতে হবে। যখন তোমার $(x;1)$ কুয়েরি থাকে, তখন তোমাকে এর সাথে কোণের দিক থেকে সবচেয়ে কাছের নরমাল ভেক্টর খুঁজতে হবে। তাহলে অপটিমাল লিনিয়ার ফাংশন এর কোনো একটা প্রান্তবিন্দুর সাথে সংশ্লিষ্ট হবে। এটা বুঝতে লক্ষ্য করো, $(x;1)$ এর সাথে ধ্রুবক ডট প্রোডাক্টবিশিষ্ট বিন্দুগুলো $(x;1)$ এর সাথে লম্ব একটা রেখায় থাকে। তাই অপটিমাল লিনিয়ার ফাংশন হবে সেটা যেখানে কনভেক্স হালের ট্যানজেন্ট লাইন $(x;1)$ এর নরমালের সাথে সমরেখ হয়ে হালকে স্পর্শ করে। এই বিন্দুটা এমন যে এর বাম আর ডানের এজের নরমালগুলো $(x;1)$ এর বিভিন্ন পাশে নির্দেশিত।

এই পদ্ধতিটি উপকারী যখন লিনিয়ার ফাংশন যোগ করার কুয়েরিগুলো $k$-এর দিক থেকে মনোটোন অথবা আমরা অফলাইনে কাজ করি, অর্থাৎ আমরা প্রথমে সব লিনিয়ার ফাংশন যোগ করে তারপর কুয়েরির উত্তর দিতে পারি। তাই আমরা এই উপায়ে শহর/পেট্রোল সমস্যা সমাধান করতে পারি না। সেটির জন্য অনলাইন কুয়েরি হ্যান্ডল করা প্রয়োজন। তবে অনলাইন কুয়েরি হ্যান্ডল করা কঠিন আর একটা সঠিক কনভেক্স হাল ইমপ্লিমেন্ট করতে কোনো ধরনের সেট ডাটা স্ট্রাকচার (data structure) ব্যবহার করতে হবে। অনলাইন পদ্ধতি এই আর্টিকেলে কঠিনতার কারণে কনসিডার করা হবে না এবং কারণ দ্বিতীয় পদ্ধতি (লি চাও ট্রি) সমস্যাটি অনেক সহজে সমাধান করতে দেয়। উল্লেখযোগ্য যে স্কয়ার-রুট-ডিকম্পোজিশন দ্বারা জটিলতা ছাড়াই এই পদ্ধতি অনলাইনে ব্যবহার করা যায়। অর্থাৎ, প্রতি $\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$ বিন্দুতে ফাংশনের ভ্যালু কম্পেয়ার করে আমরা এফিশিয়েন্টলি এটা বের করতে পারি। ছেদবিহীন অর্ধেক সেগমেন্টের জন্য আমরা নিচের ফাংশনটা বেছে নিয়ে বর্তমান ভার্টেক্সে লিখব। দেখা যায় এটা সবসময় সেটা হবে যেটা $m$ বিন্দুতে নিচে। এরপর আমরা রিকার্সিভভাবে সেগমেন্টের অন্য অর্ধে যাই, যেটা উপরে ছিল সেই ফাংশন নিয়ে। দেখা যায় এটা প্রথম অর্ধে সঠিকতা বজায় রাখবে আর অন্যটাতে রিকার্সিভ কলের সময় সঠিকতা থাকবে। তাহলে আমরা ফাংশন যোগ করতে আর বিন্দুতে মিনিমাম ভ্যালু চেক করতে পারি $O(\log [C\varepsilon^{-1}])$-এ।

ভার্টেক্সে নতুন ফাংশন যোগ করার সময় কী ঘটে তার চিত্র:

Li Chao Tree vertex

চলো এখন ইমপ্লিমেন্টেশনে যাই। আবারও আমরা লিনিয়ার ফাংশন রাখতে কমপ্লেক্স নম্বর ব্যবহার করব।

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 অ্যারেতে রাখব আর সেগমেন্ট ট্রির বাইনারি ইনডেক্সিং ব্যবহার করব। বড় সংখ্যা বা ডাবলে ব্যবহার করতে চাইলে, ডায়নামিক সেগমেন্ট ট্রি ব্যবহার করা উচিত। সেগমেন্ট ট্রি ডিফল্ট মান দিয়ে ইনিশিয়ালাইজ করতে হবে, যেমন $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));
    }
}

সমস্যাসমূহ#