可恶的 ABC，前几场 F 这么水，这场这么逆天，害得我惯性思维先做 F 掉大分。
掉大分了，所以：
我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好了，说解法。
赛时想了半个小时没想到除了数据结构以外的解法，那正解应该就是数据结构了。
考虑线段树。
注意到把一种商品买空最多只有 nnn 次，其余的要么买 000 个要么买 kkk 个。
所以我们可以维护：
* cnt[u]\text{cnt}[u]cnt[u]：没被买空的商品种数，即不为 000 的 AiA_iAi 个数。
* tree[u]\text{tree}[u]tree[u]：在没被买空的商品中，商品个数的最小值，也就是不为 000 的 AiA_iAi 最小值。为方便记录，如果该区间所有商品都被买空，则 tree[u]=0\text{tree}[u]=0tree[u]=0。
push_up函数如下：
好的，然后看怎么修改、查询。
注意到上面提到的把一种商品买空最多只有 nnn 次，所以我们可以分为两种情况：有商品数量小于等于 kkk，没有商品数量小于等于 kkk。
当一个区间有商品数量小于等于 kkk 时，我们可以不管左右区间是否已经在查询区间内，继续递归下去，直到查到具体的那几个商品，然后清空。
当全部大于 kkk 时，和正常线段树操作一样，在查询区间内打个标记结束。
注意正常买的商品种数不是 r−l+1r-l+1r−l+1，而是 cnt[u]\text{cnt}[u]cnt[u]。
这样的时间复杂度是多少呢？
首先分析都大于 kkk 的情况，很显然左右子节点的结果也会大于 kkk，所以单次询问时间复杂度是 O(logn)O(\log n)O(logn) 的。
然后再看有小于等于 kkk 的情况，会分成两个，其中如果有一个是大于 kkk，则会落到上面那个情况，单次 O(logn)O(\log n)O(logn)；否则会分成具体的商品。根据上面清空不超过 nnn 次的结论，也可以轻松得出清空的总复杂度是 O(n)O(n)O(n) 的。
所以总时间复杂度是 O(n+qlogn)O(n+q\log n)O(n+qlogn)。
代码如下：
