LibreOJ

2461 「2018 集训队互测 Day 1」完美的队列

内存限制：256 MB 时间限制：5000 ms

题目描述

小 D 有 $n$ 个 `std::queue`，他把它们编号为 $1$ 到 $n$。 小 D 对每个队列有不同的喜爱程度，如果有他不怎么喜欢的队列占用了太大的内存，小 D 就会不开心。 具体地说，如果第 $i$ 个队列的 `size()` 大于 $a_i$，小 D 就会对这个队列一直执行 `pop()` 直到其 `size()` 小等于 $a_i$。 现在这些队列都是空的，小 D 觉得太单调了，于是他决定做一些操作。 每次操作都可以用 `l r x` 来描述，表示对编号在 $[l,r]$ 内的所有队列执行 `push(x)` 操作。当然，每次操作结束后，小 D 都会用之前提到的方法来避免这些队列占用太大的内存。 小 D 的队列很神奇，所以他能用 $O(1)$ 的时间执行每次操作。 相信大家的队列都能做到，于是小 D 把这道题出给大家送分。 为了证明你确实执行了这些操作，你需要在每次操作后输出目前还在队列内的权值种数。

输入格式

第一行两个正整数 $n,m$，分别表示队列个数和操作个数。

第二行 $n$ 个正整数，第 $i$ 个表示 $a_i$。

接下来 $m$ 行，每行三个正整数 l r x，其中第 $i$ 行表示第 $i$ 次操作。

输出格式

输出共 $m$ 行，每行一个非负整数，表示第 $i$ 次操作结束后所有队列中的权值种数。

样例

第一次操作后，队列变成 ${1}{1}{}$，还在队列内的权值有 $1$，共 $1$ 种。

第二次操作后，队列变成 ${1}{1,2}{2}$，还在队列内的权值 $1,2$，共 $2$ 种。

第三次操作后，队列变成 ${3}{2,3}{2,3}$，还在队列内的权值有 $2,3$，共 $2$ 种。

数据范围与提示

对于所有数据，$n,m,a_i,x\leq 10^5$，$l\leq r$。

共 $20$ 个测试点，每个测试点 $5$ 分，其中第 $k$ 个测试点满足 $n,m,a_i,x\leq 5000k$。

特别地，以下几个测试点满足一些特殊性质：

测试点 $5$：$a_i=1$；
测试点 $7$：$a_i=2$；
测试点 $9$：$a_i=10$；
测试点 $11$：$a_i\leq 10$；
测试点 $13,15$：$\sum a_i\leq 10^6$。

对于每个测试点，你需要通过满足该点数据范围及性质的所有数据才能获得该点的分数。

样例

样例输入 1

3 3
1 2 3
1 2 1
2 3 2
1 3 3

样例输出 1

1
2
2