lessons/参考实现/12-历年真题/洛谷-P11833.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using int64 = std::int64_t;

class SegmentTree {
public:
    explicit SegmentTree(const std::vector<int64>& values)
        : n_(static_cast<int>(values.size()) - 1),
          sum_(4 * n_ + 4), lazy_(4 * n_ + 4), has_lazy_(4 * n_ + 4, false) {
        minimum_.resize(4 * n_ + 4);
        maximum_.resize(4 * n_ + 4);
        build(1, 1, n_, values);
    }

    int64 range_sum(int left, int right) {
        if (left > right) return 0;
        return range_sum(1, 1, n_, left, right);
    }

    void range_assign(int left, int right, int64 value) {
        if (left <= right) range_assign(1, 1, n_, left, right, value);
    }

    int64 point_value(int position) {
        return range_sum(position, position);
    }

    // The maintained array is nondecreasing. Return n+1 if no value >= target.
    int first_at_least(int left, int64 target) {
        return first_at_least(1, 1, n_, left, target);
    }

    // Return 0 if no value <= target in [1, right].
    int last_at_most(int right, int64 target) {
        return last_at_most(1, 1, n_, right, target);
    }

private:
    int n_;
    std::vector<int64> sum_;
    std::vector<int64> minimum_;
    std::vector<int64> maximum_;
    std::vector<int64> lazy_;
    std::vector<bool> has_lazy_;

    void apply(int node, int left, int right, int64 value) {
        sum_[node] = value * (right - left + 1);
        minimum_[node] = maximum_[node] = value;
        lazy_[node] = value;
        has_lazy_[node] = true;
    }

    void push(int node, int left, int right) {
        if (!has_lazy_[node] || left == right) return;
        int middle = (left + right) / 2;
        apply(node * 2, left, middle, lazy_[node]);
        apply(node * 2 + 1, middle + 1, right, lazy_[node]);
        has_lazy_[node] = false;
    }

    void build(int node, int left, int right, const std::vector<int64>& values) {
        if (left == right) {
            sum_[node] = values[left];
            minimum_[node] = maximum_[node] = values[left];
            return;
        }
        int middle = (left + right) / 2;
        build(node * 2, left, middle, values);
        build(node * 2 + 1, middle + 1, right, values);
        sum_[node] = sum_[node * 2] + sum_[node * 2 + 1];
        minimum_[node] = minimum_[node * 2];
        maximum_[node] = maximum_[node * 2 + 1];
    }

    int64 range_sum(int node, int left, int right, int query_left, int query_right) {
        if (query_left <= left && right <= query_right) return sum_[node];
        push(node, left, right);
        int middle = (left + right) / 2;
        int64 result = 0;
        if (query_left <= middle)
            result += range_sum(node * 2, left, middle, query_left, query_right);
        if (query_right > middle)
            result += range_sum(node * 2 + 1, middle + 1, right, query_left, query_right);
        return result;
    }

    void range_assign(int node, int left, int right, int query_left, int query_right,
                      int64 value) {
        if (query_left <= left && right <= query_right) {
            apply(node, left, right, value);
            return;
        }
        push(node, left, right);
        int middle = (left + right) / 2;
        if (query_left <= middle)
            range_assign(node * 2, left, middle, query_left, query_right, value);
        if (query_right > middle)
            range_assign(node * 2 + 1, middle + 1, right, query_left, query_right, value);
        sum_[node] = sum_[node * 2] + sum_[node * 2 + 1];
        minimum_[node] = minimum_[node * 2];
        maximum_[node] = maximum_[node * 2 + 1];
    }

    int first_at_least(int node, int left, int right, int query_left, int64 target) {
        if (right < query_left || maximum_[node] < target) return n_ + 1;
        if (left == right) return sum_[node] >= target ? left : n_ + 1;
        push(node, left, right);
        int middle = (left + right) / 2;
        int result = first_at_least(node * 2, left, middle, query_left, target);
        if (result != n_ + 1) return result;
        return first_at_least(node * 2 + 1, middle + 1, right, query_left, target);
    }

    int last_at_most(int node, int left, int right, int query_right, int64 target) {
        if (left > query_right || minimum_[node] > target) return 0;
        if (left == right) return sum_[node] <= target ? left : 0;
        push(node, left, right);
        int middle = (left + right) / 2;
        int result = last_at_most(node * 2 + 1, middle + 1, right, query_right, target);
        if (result != 0) return result;
        return last_at_most(node * 2, left, middle, query_right, target);
    }
};

struct Box {
    int index;
    int64 deadline;
    int64 target_normalized;
};

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

    int test_point, test_cases;
    std::cin >> test_point >> test_cases;
    (void)test_point;
    while (test_cases--) {
        int n;
        std::cin >> n;
        std::vector<int64> normalized(n + 1);
        std::vector<Box> boxes(n);
        for (int i = 1; i <= n; ++i) {
            int64 initial, target, deadline;
            std::cin >> initial >> target >> deadline;
            normalized[i] = initial - i;
            boxes[i - 1] = {i, deadline, target - i};
        }

        std::sort(boxes.begin(), boxes.end(), [](const Box& lhs, const Box& rhs) {
            if (lhs.deadline != rhs.deadline) return lhs.deadline < rhs.deadline;
            return lhs.index < rhs.index;
        });

        SegmentTree tree(normalized);
        int64 elapsed = 0;
        bool possible = true;
        for (const Box& box : boxes) {
            int i = box.index;
            int64 current = tree.point_value(i);
            int64 target = box.target_normalized;
            if (current < target) {
                int first = tree.first_at_least(i, target);
                int right = first - 1;
                int64 old_sum = tree.range_sum(i, right);
                elapsed += target * (right - i + 1) - old_sum;
                tree.range_assign(i, right, target);
            } else if (current > target) {
                int last = tree.last_at_most(i, target);
                int left = last + 1;
                int64 old_sum = tree.range_sum(left, i);
                elapsed += old_sum - target * (i - left + 1);
                tree.range_assign(left, i, target);
            }
            if (elapsed > box.deadline) possible = false;
        }
        std::cout << (possible ? "Yes\n" : "No\n");
    }
    return 0;
}