F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5374. -- [2018国家集训队互测]完美的队列

5374: [2018国家集训队互测]完美的队列

Time Limit: 120 Sec  Memory Limit: 256 MB
Submit: 23  Solved: 16
[Submit][Status][Discuss]

Description

小D有n个std::queue<int>,他把它们编号为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把这道题出给大家送分。为了证明你确实执行了
这些操作,你需要在每次操作后输出目前还在队列内的权值种数。

Input

第一行两个正整数n,m,分别表示队列个数和操作个数。
第二行n个正整数,第i个表示a_i。
接下来m行,每行三个正整数l r x,其中第i行表示第i次操作。
对于所有数据,n,m,a_i,x≤10^5。

Output

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

Sample Input

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

Sample Output

1
2
2
样例解释
第一次操作后,队列变成{1}{1}{},还在队列内的权值有1,共1种。
第二次操作后,队列变成{1}{1,2}{2},还在队列内的权值1,2,共2种。
第三次操作后,队列变成{3}{2,3}{2,3},还在队列内的权值有2,3,共2种。

HINT

Source

day1

[Submit][Status][Discuss]

HOME Back