Submission #1213388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213388		orzorzorz	Growing Trees (BOI11_grow)	C++20	0 / 100	38 ms	2116 KiB

grow

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static const int NMAX = 100000 + 1;  // 100000 樹＋1，方便做到 n+1

// 全域變數
ll bit[NMAX + 5];  // 差分 / Fenwick Tree
ll a[NMAX + 5];    // 排序後的樹高
int n, m;

// 在 Fenwick Tree 上做「單點加值」
void upd(int pos, ll val) {
    // pos 可能等於 n+1，但不超過 NMAX
    for (; pos <= NMAX; pos += pos & -pos) {
        bit[pos] += val;
    }
}

// Fenwick Tree 的 prefix sum：回傳差分陣列到 pos 的累積和
ll qry(int pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) {
        res += bit[pos];
    }
    return res;
}

// 透過二元搜尋，找出最小的 index i，使得 qry(i) ≥ val
// 若沒有人高度 ≥ val，就回傳 n+1
int f(ll val) {
    int l = 1, r = n, ans = n + 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (qry(mid) >= val) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 1) 把初始樹高排序
    sort(a + 1, a + n + 1);

    // 2) 我們視 a[0] = 0（代表第 0 個位置的高度 0），
    //    然後建立差分陣列 d[i] = a[i] - a[i-1]，並放進 Fenwick Tree
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        ll diff = a[i] - a[i - 1];
        // 差分: 在 i 開始 +diff，在 i+1 開始 -diff
        // 但因為我們只需要「差分型 Fenwick Tree」來做區間加＆單點查，
        // 直接用 upd(i, diff)；upd(i+1, -diff) 來構造原始高度 a[i]。
        upd(i, diff);
        upd(i + 1, -diff);
    }

    // 3) 處理 m 筆操作
    while (m--) {
        char ty;
        cin >> ty;
        if (ty == 'F') {
            // 「F c h」── 找到 c 棵最矮、且高度 ≥ h 的樹，各自 +1
            int c;
            ll h;
            cin >> c >> h;

            // (1) left = f(h) → 第一棵高度 ≥ h 的索引
            int left = f(h);
            if (left == n + 1) {
                // 沒有任何樹 ≥ h，直接跳過
                continue;
            }

            // (2) right = left + c - 1
            int right = left + c - 1;
            if (right > n) {
                // 如果超過 n，代表所有剩下的樹都要 +1
                upd(left,     1);
                upd(n + 1,   -1);
                continue;
            }

            // (3) 如果 a[right] < a[right+1]，我們可以一次把 [left..right] 全 +1
            //    注意 a[i] = qry(i) 給出第 i 棵樹當前的高度
            if (qry(right) != qry(right + 1)) {
                // safe to do whole interval
                upd(left,      1);
                upd(right + 1, -1);
                continue;
            }

            // (4) 否則表示 a[right] == a[right+1]，也就是卡在同一個 equal‐group 中間
            ll val = qry(right);        // 這群 equal‐group 的高度
            int newl = f(val);          //  equal‐group 起點 index
            int newr = f(val + 1);      //  equal‐group 結尾 + 1

            // (4a) 先把 [left..newl-1]（這些高度 < val）的樹全部 +1
            if (left <= newl - 1) {
                upd(left,      1);
                upd(newl,    -1);
            }

            // (4b) 再把 equal‐group 裡「真正要 +1 的 [newl..right]」各 +1
            upd(newl,        1);
            upd(right + 1,  -1);
        }
        else {
            // ty == 'C'：查詢「高度在 [x..y] 之間」有多少棵樹
            ll x, y;
            cin >> x >> y;

            // l = f(x) → 第一棵高度 ≥ x 的索引
            // r = f(y+1) → 第一棵高度 ≥ y+1 的索引
            int l = f(x);
            int r = f(y + 1);

            if (l == n + 1) {
                // 如果找不到高度 ≥ x，則都小於 x，答案 = 0
                cout << 0 << "\n";
            } else {
                // r = n+1 表示所有都 ≤ y；所以有效區間 [l..n]
                if (r == n + 1) {
                    r = n;
                } else {
                    // r 是第一個高度 ≥ y+1 的索引，要排除
                    r = r - 1;
                }
                if (r < l) {
                    cout << 0 << "\n";
                } else {
                    cout << (r - l + 1) << "\n";
                }
            }
        }
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10