RE了，心态崩了，记录：紫色的bird

权值线段树 + 二分答案

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
using namespace std;
struct Edge
{
    int to;
    Edge *nextEdge;
};
struct Node
{
    int data;
    Node *leftChild;
    Node *rightChild;
};
list<Node> tree;
list<Edge> edges;
vector<Edge *> head;
vector<Node *> root;
vector<pair<int, pair<int, int>>> milk;
vector<pair<int, int>> price;
vector<int> oldToNew;
vector<int> newToOld;
int N, M;
int prizeRange; // 记录有多少个不同的prize
void BuildTree(Node *node, const int &l, const int &r)
{
    if (l != r)
    {
        int mid = (l + r) / 2;
        tree.push_back({0, NULL, NULL});
        node->leftChild = &tree.back();
        BuildTree(node->leftChild, l, mid);
        tree.push_back({0, NULL, NULL});
        node->rightChild = &tree.back();
        BuildTree(node->rightChild, mid + 1, r);
    }
}
Node *AddData(Node *node, const int &l, const int &r, const int &d)
{
    if (l == r && r == d)
    {
        tree.push_back({node->data + 1, NULL, NULL});
        return &tree.back();
    }
    else if (l > d || r < d)
    {
        return node;
    }
    else
    {
        int mid = (l + r) / 2;
        tree.push_back({node->data + 1, AddData(node->leftChild, 1, mid, d), AddData(node->rightChild, mid + 1, r, d)});
        return &tree.back();
    }
}
pair<int, int> SumData(Node *nodeLeft, Node *nodeRight, const int &l, const int &r, const int &k)
{
    if (l == r)
    {
        return {l, nodeRight->data - nodeLeft->data};
    }
    else
    {
        int mid = (l + r) / 2;
        int sumLeft = nodeRight->leftChild->data - nodeLeft->leftChild->data;
        int sumRight = nodeRight->rightChild->data - nodeLeft->rightChild->data;
        if (sumLeft >= k)
        {
            return SumData(nodeLeft->leftChild, nodeRight->leftChild, l, mid, k);
        }
        else if (sumLeft + sumRight >= k)
        {
            return SumData(nodeLeft->rightChild, nodeRight->rightChild, mid + 1, r, k - sumLeft);
        }
        else
        {
            return {0, 0};
        }
    }
}
int check(int g, const int &mid)
{
    int result = 0;
    int k = 1;
    while (g)
    {
        pair<int, int> top = SumData(root[mid - 1], root[N], 1, prizeRange, k);
        int it = top.first;
        if (!it)
        {
            break;
        }
        it = newToOld[it];
        while (it >= 0 && price[it - 1].first == price[it].first)
        {
            int pos = price[it].second;
            if (milk[pos].second.second * milk[pos].second.first > g)
            {
                result += g / milk[pos].second.first;
                g = 0;
            }
            else
            {
                result += milk[pos].second.second;
                g -= milk[pos].second.second * milk[pos].second.first;
            }
            it--;
        }
        int pos = price[it].second;
        if (milk[pos].second.second * milk[pos].second.first > g)
        {
            result += g / milk[pos].second.first;
            g = 0;
        }
        else
        {
            result += milk[pos].second.second;
            g -= milk[pos].second.second * milk[pos].second.first;
        }
        k += top.second;
    }
    return result;
}
int FindAns(const int &l, const int &r, const int &g, const int &p)
{
    if (l == r)
    {
        return check(g, l) < p ? 0 : l;
    }
    int mid = (l + r + 1) / 2;
    if (check(g, mid) < p)
    {
        return FindAns(l, mid - 1, g, p);
    }
    else
    {
        return FindAns(mid, r, g, p);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    milk.assign(N, {0, {0, 0}});
    root.assign(N + 1, NULL);
    price.assign(N, {0, 0});
    oldToNew.assign(N + 1, 0);
    newToOld.assign(2, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> milk[i].first >> milk[i].second.first >> milk[i].second.second;
    }
    sort(milk.begin(), milk.end());
    for (int i = 0; i < N; i++)
    {
        price[i] = {milk[i].second.first, i};
    }
    sort(price.begin(), price.end());
    prizeRange = 1;
    oldToNew[price[0].second] = prizeRange;
    newToOld[prizeRange] = 0;
    for (int i = 1; i < N; i++)
    {
        if (price[i].first != price[i - 1].first)
        {
            newToOld.push_back(0);
            prizeRange++;
        }
        oldToNew[price[i].second] = prizeRange;
        newToOld[prizeRange] = i;
    }
    tree.push_back({0, NULL, NULL});
    root[0] = &tree.back();
    BuildTree(root[0], 1, prizeRange);
    for (int i = 0; i < N; i++)
    {
        root[i + 1] = AddData(root[i], 1, prizeRange, oldToNew[i]);
    }
    while (M)
    {
        M--;
        int g, l;
        cin >> g >> l;
        int res = FindAns(1, N, g, l) - 1;
        if (res != -1)
        {
            cout << milk[res].first << "\n";
        }
        else
        {
            cout << -1 << "\n";
        }
    }
    return 0;
}