#1756. 完美的队列

    ID: 1756 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest125来源:qoj.ac数据:公开样例

完美的队列

完美的队列

题目描述

标题: 完美的队列 - Problem - QOJ.ac

#4780. 完美的队列

Statistics

The problem was used in the following contests:

小 D 有 n 个 std::queue<int>,他把它们编号为 1 到 n。

小 D 对每个队列有不同的喜爱程度,如果有他不怎么喜欢的队列占用了太大的内存,小 D 就会不开心。

具体地说,如果第 i 个队列的 size() 大于 ai,小 D 就会对这个队列一直执行 pop() 直到其 size() 小等于 ai。

现在这些队列都是空的,小 D 觉得太单调了,于是他决定做一些操作。

每次操作都可以用 l r x 来描述,表示对编号在 [l,r] 内的所有队列执行 push(x) 操作。当然,每次操作结束后,小 D 都会用之前提到的方法来避免这些队列占用太大的内存。

小 D 的队列很神奇,所以他能用 O(1) 的时间执行每次操作。

相信大家的队列都能做到,于是小 D 把这道题出给大家送分。

为了证明你确实执行了这些操作,你需要在每次操作后输出目前还在队列内的权值种数。

输入格式

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

第二行 n 个正整数,第 i 个表示 ai。

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

输出格式

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

样例数据

样例输入

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

样例输出

1
2
2

样例解释

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

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

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

子任务

对于所有数据,n,m,ai,x≤105,l≤r。

共 20 个测试点,每个测试点 5 分,其中第 k 个测试点满足 n,m,ai,x≤5000k。

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

  • 测试点 5:ai=1;
  • 测试点 7:ai=2;
  • 测试点 9:ai=10;
  • 测试点 11:ai≤10;
  • 测试点 13,15:∑ai≤106。

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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