思路：数据结构

动态区间删减，并且需要查询区间最大值，该特性可以使用线段树实现。

维护线段树区间最大值的下标，每次查询将最大下标对应的值删去并输出，直到没有最大值为止。

代码

C++

#include <iostream>
#include <vector>
using namespace std;

// 常量定义，用于指定线段树的大小和最大输入大小
const int MAX_SIZE = 100000;
const int LIMIT = MAX_SIZE + 10;

// 线段树结构体，用于处理区间查询和更新
struct SegmentTree {
    int size;              // 数据数组的大小
    vector<int> tree;      // 线段树数组
    vector<int> data;      // 存储元素的数据数组

    // 初始化线段树，传入数据长度和数据
    void init(int len, vector<int>& d) {
        size = len;
        tree.assign(4 * size, 0); // 分配足够大小的线段树数组
        data = d;                 // 保存传入的数据
    }

    // 构建线段树
    void build(int node, int start, int end) {
        if (start == end) {
            // 如果是叶节点，保存索引
            tree[node] = start;
        } else {
            int mid = (start + end) / 2;
            // 递归构建左右子树
            build(2 * node, start, mid);
            build(2 * node + 1, mid + 1, end);
            // 合并结果，根据条件选择较大值或索引较小者
            tree[node] = compare(tree[2 * node], tree[2 * node + 1]);
        }
    }

    // 比较两个索引对应的值，返回较大值或索引较小者
    int compare(int idx1, int idx2) {
        if (data[idx1] > data[idx2] || (data[idx1] == data[idx2] && idx1 < idx2))
            return idx1;
        return idx2;
    }

    // 更新线段树中的一个元素
    void update(int node, int start, int end, int idx, int value) {
        if (start == end) {
            // 如果是叶节点，直接更新
            data[idx] = value;
            tree[node] = idx;
        } else {
            int mid = (start + end) / 2;
            // 递归更新对应的子树
            if (idx <= mid)
                update(2 * node, start, mid, idx, value);
            else
                update(2 * node + 1, mid + 1, end, idx, value);
            // 合并结果
            tree[node] = compare(tree[2 * node], tree[2 * node + 1]);
        }
    }

    // 查询区间[l, r]内的最大值索引
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l)
            return -1; // 如果区间不重叠，返回-1
        if (l <= start && end <= r)
            return tree[node]; // 如果区间完全包含，返回当前节点结果
        int mid = (start + end) / 2;
        // 递归查询左右子树并合并结果
        int leftResult = query(2 * node, start, mid, l, r);
        int rightResult = query(2 * node + 1, mid + 1, end, l, r);
        if (leftResult == -1) return rightResult;
        if (rightResult == -1) return leftResult;
        return compare(leftResult, rightResult);
    }

    // 添加元素到线段树中（即更新元素值）
    void add(int idx, int value) {
        update(1, 1, size, idx, value);
    }

    // 从线段树中移除元素（即将值设为-1）
    void remove(int idx) {
        update(1, 1, size, idx, -1);
    }

    // 获取区间[l, r]内的最大值索引
    int getMaxIndex(int l, int r) {
        return query(1, 1, size, l, r);
    }
} segment[2];

int main() {
    int numOps, numElems;
    cin >> numOps >> numElems;
    vector<int> arr[2]; // 用于存储两个数组的数据
    arr[0].resize(numElems + 1, -1);
    arr[1].resize(numElems + 1, -1);
    vector<int> A(numElems), B(numElems);
    
    // 读取数组A的元素
    for (int i = 0; i < numElems; ++i) {
        cin >> A[i];
    }
    // 读取数组B的元素，并将数组A的值映射到arr数组中
    for (int i = 0; i < numElems; ++i) {
        cin >> B[i];
        arr[B[i]][i + 1] = A[i];
    }
    // 初始化并构建两个线段树
    for (int i = 0; i < 2; ++i) {
        segment[i].init(numElems, arr[i]);
        segment[i].build(1, 1, numElems);
    }
    // 处理查询操作
    while (numOps--) {
        int left, right, type, numQueries;
        cin >> left >> right >> type >> numQueries;
        while (numQueries--) {
            int index = segment[type].getMaxIndex(left, right);
            int value = segment[type].data[index];
            segment[type].remove(index); // 删除找到的最大值
            cout << (value != -1 ? index : -1) << ' ';
            if (value == -1) break; // 如果没有找到有效值，停止
        }
        cout << '\n';
    }
    return 0;
}

题目内容

塔塔商店里只卖两种商品，“塔可乐“和“塔马克”。

现在有$n$个人来到商店购物，第$i$个人有一个喜好区间$[l_i,r_i]$和购买目标商品，他只看货架上位于区间里的商品，并从中挑选$k_i$个保质期最长的塔可乐或者塔马克买走(如果有多个商品保质期相同，他会拿走区间中靠前的那个)。你能告诉塔塔每个人买走的商品编号吗。

输入描述

第一行输入两个整数$n$和$m(1≤n,m≤10^5)$代表来塔塔商店购物的人数和商品数量。

第二行输入$m$个整数$a_1, a_2,...,a_m(1≤a_i≤10^9)$代表商品的保质期。

第三行输入$m$个整数$b_1,b_2,...,b_m(0≤b_i≤1)$代表商品的种类，其中，$b_i=0$代表"塔可乐"、$b_i=1$代表"塔马克''。

此后$n$行，第$i$行输入四个整数$l_i,r_i,t_i$;和$k(1≤l_i≤r_i≤m;0≤t_i≤1;1≤k_i≤m)$代表第$i$个人的喜好区间、购买商品和购买件数。其中，$t_i$=0代表他想要购买“塔可乐”、$t_i=1$代表他想要购买“塔马克”。

输出描述

输出$n$行，第$i$行包含至多$k_i$个整数，代表第$i$个人购买的商品编号(如果有多个商品保质期相同，输出编号较小的那个)，你需要按照从小到大的顺序依次输出;如果没有买到足够的商品，使用一个$-1$替代。

输入

5 5
2 3 4 5 6
1 1 0 1 1
1 3 1 2
1 3 1 2
1 3 0 5
1 5 1 1
1 5 0 1

输出

2 1
-1
3 -1
5
-1

说明

●第一次询问，货架上的情况为${2,3,*,5,6}$ ($*$代表非目标商品，下划线代表喜好区间)，先买第二件，再买第一件;

●第二次询问，货架上的情况为{x,x,$*$,$5$,$6$}(x代表已售罄商品)，此时无法购买，直接输出$-1$;

●第三次询问，货架上的情况为{$*,*,4,5,6$}由于只剩一件商品，故先购买第三件，后输出$-1$代表没有买到足够数量的商品。