TIOJ 1343：[IOI 2007, Day 1] Sails

 TIOJ 1343：[IOI 2007, Day 1] Sails

題目大意：有一艘海盜船正在建造中。這艘船有 $N$ 根船桅，每根船桅由同等長度的船桅片段所組成。每根船桅的片段數即是該根船桅的高度。每根船桅上各掛置了數片船帆，每一片船帆剛好可以掛在一個船桅片段上。船桅上的船帆可以掛在該船桅上任一船桅片段位置，但是每一船桅片段只能掛一片船帆。
不同的船帆掛置方式，受風時可產生不同的推力。某一船帆前面如有其他的船帆，該船帆受到的風力就會較小，而所能產生的推力也較小。定義每一船帆的反效率 ($\text{inefficiency}$)為位於這片船帆後面且同等高度的船帆數。請注意「在前面」或「在後面」是跟船的方向有關，在下圖中，「前面」指的是左邊，「後面」指的是右邊。
整艘船的總反效率則為所有船帆反效率的總和。
請寫一個程式，當給定 $N$ 個船桅的高度及船帆數時，計算出最小的總反效率。

解法：貪心 $+$ 線段樹。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1

const int INF = 1e9;
const int SIZE = 1e5 + 5;

int n, seg[4 * SIZE];
int mx, cnt[SIZE];

void modify (int pos, int l, int r, int p, int x) {
    if (p > mx || p <= 0)
        return;
    if (l == r)
        seg[pos] += x;
    else {
        int mid = (l + r) / 2;
        if (p <= mid)
            modify (lpos, l, mid, p, x);
        else
            modify (rpos, mid + 1, r, p, x);
        seg[pos] = min (seg[lpos], seg[rpos]);
    }
}

int min_left (int pos, int l, int r, int L, int R) {
    int mid = (L + R) / 2;
    if (l == L && r == R) {
        if (seg[pos] >= 0)
            return INF;
        if (L == R)
            return L;
        if (seg[lpos] < 0)
            return min_left (lpos, l, mid, L, mid);
        else
            return min_left (rpos, mid + 1, r, mid + 1, R);
    }
    if (r <= mid)
        return min_left (lpos, l, r, L, mid);
    if (l > mid)
        return min_left (rpos, l, r, mid + 1, R);
    return min (min_left (lpos, l, mid, L, mid), min_left (rpos, mid + 1, r, mid + 1, R));
}

int max_right (int pos, int l, int r, int L, int R) {
    if (l > r)
        return 1;
    int mid = (L + R) / 2;
    if (l == L && r == R) {
        if (seg[pos] >= 0)
            return 1;
        if (L == R)
            return L;
        if (seg[rpos] < 0)
            return max_right (rpos, mid + 1, r, mid + 1, R);
        else
            return max_right (lpos, l, mid, L, mid);
    }
    if (r <= mid)
        return max_right (lpos, l, r, L, mid);
    if (l > mid)
        return max_right (rpos, l, r, mid + 1, R);
    return max (max_right (lpos, l, mid, L, mid), max_right (rpos, mid + 1, r, mid + 1, R));
}

void build (int pos, int l, int r) {
    if (l == r)
        cnt[l] = cnt[l - 1] + seg[pos];
    else {
        int mid = (l + r) / 2;
        build (lpos, l, mid);
        build (rpos, mid + 1, r);
    }
}

void solve() {
    cin >> n;

    pair<int, int> p[n];
    for (int i = 0; i < n; i++) {
        cin >> p[i].F >> p[i].S;
        mx = max (mx, p[i].F);
    }
    sort (p, p + n);

    for (int i = 0; i < n; i++) {
        int h = p[i].F, k = p[i].S, spc = h - k;
        int fill_l = min_left (1, spc + 1, h, 1, mx), spc_r = max_right (1, 1, spc, 1, mx);
        if (h == k) {
            modify (1, 1, mx, 1, 1);
            modify (1, 1, mx, h + 1, -1);
        } else if (fill_l == INF) {
            modify (1, 1, mx, spc_r, 1);
            modify (1, 1, mx, spc_r + k, -1);
        } else {
            modify (1, 1, mx, fill_l, 1);
            modify (1, 1, mx, h + 1, -1);
            modify (1, 1, mx, spc_r, 1);
            modify (1, 1, mx, spc_r + k - h + fill_l - 1, -1);
        }
    }

    LL ans = 0;
    build (1, 1, mx);
    for (int i = 1; i <= mx; i++) {
        ans += 1ll * cnt[i] * (cnt[i] - 1) / 2;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！