8364: BZOJ4364:[IOI2014]wall砖墙

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

健佳正在用大小相同的砖块来砌起一面墙。这面墙由 列砖块所组成,它们从左到右的编号0至n-1。各列的高度可 以不同。各列的高度就是该列砖块的数量。健佳用如下方式来建造这面墙。最开始每列都没有砖块。此后,健佳通 过k个阶段的增加(adding)或移除(removing)砖块操作来砌墙。当所有k个阶段完成后,这面墙就砌好了。在每个阶 段中,健佳都会被告知一个连续的砖块列的范围,以及一个高度值h,然后他就完成如下过程:在增加砖块(adding )阶段,对于给定的列范围中高度小于h的列,健佳会增加砖块使它们的高度都恰好等于h。此时他不会改变那些高 度大于或等于h的列。在移除砖块(removing)阶段,对于给定的列范围中高度大于 的列,健佳会移除砖块使它们的 高度都恰好等于h。此时他不会改变那些高度小于或等于h的列。你的任务就是计算出这面墙的最后形状。


输入格式

第1行:n, k。 第2+i 行(0≤i≤k-1):op[i], left[i], right[i], height[i]。 n: 这面墙中的列数。 k: 阶段数。 op: 大小为k的数组;op[i]是第i个阶段的类型:1 表示增加阶段(adding) 而 2表示移除阶段(removing)  其中0≤i≤k-1。 left 和 right: 大小为k的数组;在第i个阶段中,列的范围从第left[i] 列开始到第right[i]列结束(包括两端 left[i] 和 right[i]),其中0≤i≤k-1。这里保证满足left[i]≤right[i]。 height: 大小为k的数组;height[i] 表示在阶段i的高度参数,其中0≤i≤k-1。


输出格式

共n行 第i行包含一个整数表示finalHeight[i]。 finalHeight: 大小为n的数组;你需要把第i列砖块的最终数量存放到finalHeight[i]中做为返回结果 其中0≤i≤n-1。


样例输入

输入样例1
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

输入样例2
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

样例输出

输出样例1
0
0
0
39412
39412
39412
48623
48623
48623
48623

输出样例2
3
4
5
4
3
3
0
0
1
0

提示

对于100%的数据,1n2,000,0001k500,000

2016.6.17时限放至60s


题目来源

鸣谢yts1999上传

加入题单

上一题 下一题 算法标签: