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

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

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

সমস্যাসমূহ#