關鍵技巧：時間點離散化 + 區間塗色

• 收集所有 st, ed，排序去重，映射到 1..K
• 線段樹支援區間賦值（蓋色）、單點查詢
• 下推標記：pushdown 將父節點顏色傳給子節點

完整 AC 程式碼

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

const int MAXN = 100010;

struct Cow {
    int x, y, c; // 位置、速度
    int st, ed;  // 時間區間
    bool operator<(const Cow& o) const { return y > o.y; } // 遠到近
    void read() {
        scanf("%d%d%d", &x, &y, &c);
        x = -x; // 統一朝向
        st = c * (x - 1);
        ed = st + c;
    }
} cows[MAXN];

pair events[MAXN * 2];
int tree[MAXN * 4];
bool visible[MAXN];

void pushdown(int rt) {
    if (tree[rt]) {
        tree[rt<<1] = tree[rt];
        tree[rt<<1|1] = tree[rt];
        tree[rt] = 0;
    }
}

void update(int l, int r, int L, int R, int c, int rt) {
    if (l == L && r == R) { tree[rt] = c; return; }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (R <= mid) update(l, mid, L, R, c, rt<<1);
    else if (L > mid) update(mid+1, r, L, R, c, rt<<1|1);
    else {
        update(l, mid, L, mid, c, rt<<1);
        update(mid+1, r, mid+1, R, c, rt<<1|1);
    }
}

int query(int l, int r, int pos, int rt) {
    if (l == r) return tree[rt];
    pushdown(rt);
    int mid = (l + r) >> 1;
    return (pos <= mid) ? query(l, mid, pos, rt<<1) : query(mid+1, r, pos, rt<<1|1);
}

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cows[i].read();
    sort(cows + 1, cows + n + 1);
    
    // 離散化時間點
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        events[++cnt] = {cows[i].st, &cows[i].st};
        events[++cnt] = {cows[i].ed, &cows[i].ed};
    }
    sort(events + 1, events + cnt + 1);
    int T = 0;
    for (int i = 1; i <= cnt; i++) {
        if (i == 1 || events[i].first != events[i-1].first) T += 2;
        *events[i].second = T;
    }
    
    // 遠到近塗色
    for (int i = 1; i <= n; i++)
        update(1, T, cows[i].st, cows[i].ed, i, 1);
    
    // 查詢每個時間點最終顏色
    for (int i = 1; i <= T; i++)
        visible[query(1, T, i, 1)] = true;
    
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += visible[i];
    cout << ans << '\n';
    return 0;
}

關鍵點總結

• 遠到近處理順序：近處奶牛遮擋遠處，後塗色覆蓋前塗色
• 時間點與區間區別：離散化時端點各佔一個單位，區間包含端點
• 線段樹區間賦值：標記下推保證查詢正確
• 等價於 POJ Mayor's posters：海報覆蓋問題同構