Xét trường hợp ~st = 0~ và ~d~ cố định

Không mất tính tổng quát, giả sử chúng ta bắt đầu tại hòn đảo bên trái nhất và di chuyển sang phải. Rõ ràng, chúng ta chỉ cần di chuyển sang phải và không cần di chuyển sang trái vào bất kỳ lúc nào. Giả sử trong một lời giải tối ưu, hòn đảo ~\text{right}~ là hòn đảo xa nhất mà ta sẽ đi đến. Khi đó, chúng ta có thể tham quan tối đa ~d - \text{right}~ hòn đảo trong số các hòn đảo có nhãn ~0, 1, \dots, \text{right}~. Để tối ưu, ta cần tham quan ~d - \text{right}~ hòn đảo có số lượng điểm du lịch lớn nhất. Nói cách khác, nếu ta sắp xếp các hòn đảo có nhãn từ ~0~ đến ~\text{right}~ theo số điểm du lịch giảm dần, ta cần tìm tổng của ~d - \text{right}~ số lượng điểm du lịch lớn nhất.

Thuật toán

Trước tiên, chúng ta sắp xếp các hòn đảo theo số lượng điểm tham quan của chúng theo thứ tự giảm dần. Sau đó, theo thứ tự này, chúng ta đặt chúng làm lá trên cây đoạn segment tree từ trái sang phải với tất cả các lá ban đầu ở trạng thái không hoạt động. Số lượng điểm tham quan bây giờ là giá trị của các lá. Giai đoạn khởi tạo mất thời gian ~\mathcal{O}(n \log n)~. Chúng ta sẽ bật một lá khi nó được truy cập trong quá trình tìm kiếm nghiệm. Chúng ta lặp qua tất cả các giá trị có thể của hòn đảo xa nhất bên phải mà ta có thể di chuyển đến. Do đó, thời gian để tìm một nghiệm cho trường hợp đặc biệt này là ~\mathcal{O}(n \log n)~.

Xét trường hợp ~st = 0~ và tất cả các giá trị có thể của ~d~

Bây giờ chúng ta sẽ mô tả cách giải quyết trường hợp trung gian này. Trong giải pháp trước, chúng ta có thể tìm số lượng điểm tham quan tối đa có thể ghé thăm với mỗi giá trị ~d~. Gọi ~f(d)~ là nhãn của hòn đảo mà ta di chuyển đến trong ~d~ ngày để đạt được số điểm tham quan tối đa. Lưu ý rằng ~f(d)~ có thể không duy nhất. Nếu có nhiều lựa chọn, chúng ta chọn hòn đảo có nhãn nhỏ nhất. Bây giờ, ta muốn xây dựng một bảng cho tất cả các giá trị có thể của ~d~. Ý tưởng là sử dụng phương pháp đệ quy chia để trị.

Gọi ~M~ là số tối đa của ~d~. Để mô tả dễ dàng hơn, giả sử ~M~ là lũy thừa của 2. Để tính toán các nghiệm của ~f(1), f(2), \dots, f(M)~, trước tiên chúng ta tìm ~f\left(\frac{M}{2}\right)~ bằng thuật toán trước đó bằng cách lặp qua tất cả các hòn đảo từ ~0~ đến ~n~, sau đó tiếp tục đệ quy để tính ~f(1), f(2), \dots, f\left(\frac{M}{2} - 1\right)~ trong một nhánh bằng cách chỉ xét các hòn đảo từ ~0~ đến ~f\left(\frac{M}{2}\right)~, và tính các giá trị còn lại trong nhánh thứ hai bằng cách chỉ xét các hòn đảo từ ~f\left(\frac{M}{2}\right)~ đến ~n~. Trong nhánh tính ~f(1), f(2), \dots, f\left(\frac{M}{2} - 1\right)~, trước tiên ta tính ~f\left(\frac{M}{4}\right)~ trong phạm vi từ ~0~ đến ~f\left(\frac{M}{2}\right)~.

Nhìn chung, tổng thời gian tiêu tốn trong mỗi mức đệ quy là ~\mathcal{O}(n \log n)~. Tổng số mức đệ quy là ~\mathcal{O}(\log n)~. Do đó, độ phức tạp tổng thể là ~\mathcal{O}(n \log^2 n)~.

Trong quá trình giải quyết trường hợp trung gian này, vai trò của cây đoạn trở nên rõ ràng hơn. Đầu tiên, chúng ta chỉ cần khởi tạo một lần duy nhất. Thứ hai, chúng ta có thể dễ dàng bật hoặc tắt một lá để phù hợp với phạm vi các hòn đảo mà ta quan tâm ở mỗi mức đệ quy. Ví dụ, chỉ một nửa số lá là hoạt động trong mức đệ quy thứ hai.

Giải pháp tổng quát cho giá trị bất kỳ của ~st~

Bây giờ chúng ta sẽ trình bày giải pháp tổng quát. Khi ~st~ có giá trị tùy ý, nghiệm có thể được tìm thấy trong một trong hai trường hợp sau:

1. Trước tiên, chúng ta di chuyển sang phải đến một hòn đảo, sau đó di chuyển sang trái từ điểm đó và cuối cùng dừng lại ở một hòn đảo bên trái của ~st~.

2. Hoặc chúng ta di chuyển sang trái đến một hòn đảo, sau đó di chuyển sang phải từ điểm đó và cuối cùng dừng lại ở một hòn đảo bên phải của ~st~.

Điều quan trọng là chúng ta chỉ thay đổi hướng một lần. Không mất tính tổng quát, giả sử chúng ta xét trường hợp đầu tiên.

Trước tiên, ta sử dụng giải pháp cho trường hợp đơn giản để tìm ~f(t)~ cho tất cả các giá trị có thể của ~t~. Sau đó, chúng ta cũng sử dụng giải pháp tương tự để tìm ~g(t)~, trong đó ~g(t)~ là hòn đảo mà ta sẽ dừng lại trong nghiệm tối ưu nếu chỉ di chuyển sang trái và hòn đảo xuất phát là ~st - 1~. Chúng ta bắt đầu xét ~d_0~, số ngày dành cho việc di chuyển và thăm thú các hòn đảo ở bên phải, bao gồm cả ~st~. Sử dụng nghiệm của bài toán trung gian, ta biết ~f(d_0)~. Khi đó, ta có thể dành ~d - d_0 - (f(d_0) - st) - 1~ ngày để di chuyển đến các hòn đảo bên trái của ~st~.

Độ phức tạp: ~\mathcal{O}(n \log^2 n)~.

#include "bits/stdc++.h"
#define fi first
#define sc second
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
const ll maxn = 300005;

ll n;
ll a[maxn];
ll d;
ll st;
ll opt[maxn];
pll t[2 * maxn];
ll ls[2 * maxn], rs[2 * maxn], tsz = 0, root = 0;
ll id[maxn];
pll b[maxn];

void init(ll &v, ll tl, ll tr)
{
    if (!v)
        v = ++tsz;
    if (tl == tr)
    {
        t[v] = {0, 0};
        return;
    }
    ll mid = (tl + tr) / 2;
    init(ls[v], tl, mid);
    init(rs[v], mid + 1, tr);
    t[v] = {0, 0};
}

ll get(ll v, ll tl, ll tr, ll k)
{
    if (k == 0)
        return 0;
    if (k >= t[v].sc)
        return t[v].fi;
    ll mid = (tl + tr) / 2;
    if (k >= t[rs[v]].sc)
        return t[rs[v]].fi + get(ls[v], tl, mid, k - t[rs[v]].sc);
    return get(rs[v], mid + 1, tr, k);
}

void upd(ll v, ll tl, ll tr, ll i, bool e)
{
    if (v == root)
    {
        i = id[i];
    }
    if (tl == tr)
    {
        if (e)
            t[v] = {b[i].fi, 1};
        else
            t[v] = {0, 0};
        return;
    }
    ll mid = (tl + tr) / 2;
    if (i <= mid)
        upd(ls[v], tl, mid, i, e);
    else
        upd(rs[v], mid + 1, tr, i, e);
    t[v] = {t[ls[v]].fi + t[rs[v]].fi, t[ls[v]].sc + t[rs[v]].sc};
}

ll cr;
ll dpr[maxn];
ll dpl[maxn];
bool bf = 0;

void dp(ll l, ll r, ll tl, ll tr)
{
    if (l > r)
        return;
    ll mid = (l + r) / 2;
    if (bf)
        tl = st, tr = n;
    while (cr > tl)
    {
        upd(root, 1, n, cr, 0);
        cr--;
    }
    while (cr < tl)
    {
        upd(root, 1, n, cr + 1, 1);
        cr++;
    }
    opt[mid] = -1;
    dpr[mid] = -1;
    for (ll i = tl; i <= tr; i++)
    {
        ll ck = mid - 2 * (i - st);
        if (ck < 0)
            break;
        ll cur = get(root, 1, n, ck);
        if (cur > dpr[mid])
        {
            dpr[mid] = cur;
            opt[mid] = i;
        }
        if (i < n)
        {
            upd(root, 1, n, i + 1, 1);
            cr = i + 1;
        }
    }
    if (opt[mid] != -1)
    {
        dp(l, mid - 1, tl, opt[mid]);
        dp(mid + 1, r, opt[mid], tr);
    }
    else
    {
        dp(l, mid - 1, tl, tr);
        dp(mid + 1, r, tl, tr);
    }
    dpr[mid] = max(dpr[mid], 0LL);
}

void dp2(ll l, ll r, ll tl, ll tr)
{
    if (l > r)
        return;
    ll mid = (l + r) / 2;
    if (bf)
        tl = 1, tr = st - 1;
    while (cr < tr)
    {
        upd(root, 1, n, cr, 0);
        cr++;
    }
    while (cr > tr)
    {
        upd(root, 1, n, cr - 1, 1);
        cr--;
    }
    opt[mid] = -1;
    dpl[mid] = -1;
    for (ll i = tr; i >= tl; i--)
    {
        ll ck = mid - (st - i);
        if (ck < 0)
            continue;
        ll cur = get(root, 1, n, ck);
        if (cur > dpl[mid])
        {
            dpl[mid] = cur;
            opt[mid] = i;
        }
        if (i > 1)
        {
            upd(root, 1, n, i - 1, 1);
            cr = i - 1;
        }
    }
    if (opt[mid] != -1)
    {
        dp2(mid + 1, r, tl, opt[mid]);
        dp2(l, mid - 1, opt[mid], tr);
    }
    else
    {
        dp2(mid + 1, r, tl, tr);
        dp2(l, mid - 1, tl, tr);
    }
    dpl[mid] = max(dpl[mid], 0LL);
}

ll calc()
{
    for (ll i = 1; i <= n; i++)
        b[i] = {a[i], i};
    sort(b + 1, b + 1 + n);
    for (ll i = 1; i <= n; i++)
        id[b[i].sc] = i;
    init(root, 1, n);
    cr = st;
    upd(root, 1, n, st, 1);
    for (ll i = 0; i <= d; i++)
        dpr[i] = dpl[i] = opt[i] = 0;
    dp(1, d, st, n);
    for (ll i = 0; i <= d; i++)
        dpl[i] = opt[i] = 0;
    init(root, 1, n);
    cr = st - 1;
    if (cr)
        upd(root, 1, n, cr, 1);
    dp2(2, d, 1, st - 1);
    ll ans = 0;
    dpl[0] = dpl[1] = dpr[0] = 0;
    for (ll i = 0; i <= d; i++)
        ans = max(ans, dpl[i] + dpr[d - i]);
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> st >> d;
    st++;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll ans = calc();
    reverse(a + 1, a + 1 + n);
    st = n - st + 1;
    ans = max(ans, calc());
    cout << ans;
}