思路:线段树模拟

我们需要实现：1.区间查询最值以及这个最值最靠左的位置 2.单点修改保质期为-1即可。

然后每次进行操作先查询day 和 区间最值的关系，如果day > mx 那么就不用查，直接输出-1

代码

python

# 实现一个维护最大值的线段树
# 1. 区间最值查询
# 2. 单点最值更新
class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n * 4)
        self.pos = [0] * (n * 4)
    
    def push_up(self, rt):
        self.tree[rt] = max(self.tree[rt << 1], self.tree[rt << 1 | 1])
        if self.tree[rt << 1] >= self.tree[rt << 1 | 1]:
            self.pos[rt] = self.pos[rt << 1]
        else:
            self.pos[rt] = self.pos[rt << 1 | 1]
    
    def build(self, rt, l, r, arr):
        if l == r:
            self.tree[rt] = arr[l]
            self.pos[rt] = l
            return
        m = (l + r) >> 1
        self.build(rt << 1, l, m, arr)
        self.build(rt << 1 | 1, m + 1, r, arr)
        self.push_up(rt)
    
    def query(self, rt, l, r, L, R):
        if L <= l and r <= R:
            return [self.tree[rt] , self.pos[rt]]
        m = (l + r) >> 1
        mx , pos = 0 , 10**9
        if L <= m:
            mx_l , pos_l = self.query(rt << 1, l, m, L, R)
            mx , pos = mx_l , pos_l
        if R > m:
            mx_r , pos_r = self.query(rt << 1 | 1, m + 1, r, L, R)
            if mx_r > mx:
                mx , pos = mx_r , pos_r
        return [mx , pos]
    # 单点更新
    def update (self , rt , l , r , pos , val):
        if l == r:
            self.tree[rt] = val
            return
        m = (l + r) >> 1
        if pos <= m:
            self.update(rt << 1, l, m, pos, val)
        else:
            self.update(rt << 1 | 1, m + 1, r, pos, val)
        self.push_up(rt)

n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
tree = SegmentTree(m)
tree.build(1, 1, m, a)
res = []
for i in range(n):
    day , l , r = map(int, input().split())
    mx , pos = tree.query(1, 1, m, l, r)
    if mx < day:
        res.append(-1)
    else:
        tree.update(1, 1, m, pos, -1)
        res.append(pos)
print(*res)

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小明店主发现商品的出纳账单遭到了毁坏，为了恢复，他翻阅了近期的监控和商品出售记录，得到了每一个人到店的日期和在哪一个位置取过物品(但是由于监控模糊，只能大致确定区间)。

每一个商品都有剩余保质期，每过一天剩余保质期都应该减一，当保质期为非负数时，都会被人购买;当保质期为负数时，就没有人再会买了;

保质期先于人员到店刷新。

假设第$i$个客人在$day_i$天来商店购物，且在$[l,r]$这个货架区间取过物品，那么他会挑选靠左的保质期最长的那个商品走。

请你帮助计算每一个人买走的商品编号。

输入描述

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

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

此后$n$行，第$i$行输入三个整数$day_i,l_i和r_i(1≤day_i≤10^5;1≤l_i≤r_i≤m)$代表第$i$个人的到店时间、

取货区间。

如果有多个人在同一天到店，那么先输入的人早于后输入的人到店。

输出描述

输出一行，包含$n$个整数，代表每一个人买走的商品编号，如果这个人的取货区间里没有满足条件的商品，输出$-1$替代。

示例1

输入

4 5
1 2 3 4 7
1 1 4
1 4 4
5 1 4
5 1 5

输出

4 -1 -1 5

说明

• 对于第一个顾客，买走保质期最长的第四个商品；
• 对于第二个顾客，由于第四个商品已经被买走了，所有他没有买到商品，输出-1；
• 对于第三个顾客，由于他是第五天来的，此时前四个商品都已经过期了，所有他也没没有买到商品，则输出-1

样例2

输入

3 5
2 2 2 2 2
1 1 5
2 1 5
3 1 5

输出

1 2 -1