303834: CF739C. Alyona and towers

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

Description

Alyona and towers

题意翻译

现在有$n$个数,$m$个操作,**每次区间加一个数**,对于**每一次**操作,你要找出**最长**的$\ a_l...a_r\ $,满足 $$\exists k\! \in\![l,r],a_l<a_{l+1}<a_{l+2}<...<a_k>a_{k+1}>a_{k+2}>...>a_r$$ 输出其长度。 输入: 第一行一个整数$n$,表示数的个数。 第二行$n$个整数$a_i$。 第三行一个整数$m$,表示操作个数。 下面$m$行,每行$3$个整数,$l_i,r_i,d_i$,表示将$l_i$到$r_i$的数字加$d_i$。 输出: 对于**每个**操作,输出操作完后的答案(见题意)。 样例解释: 1. 5 5 5 5 5 $\to$ 7 7 7 5 5 ,最长的是7 5,长度为2 2. 7 7 7 5 5 $\to$ 7 8 7 5 5 ,最长的是7 8 7 5 ,长度为4 3. 7 8 7 5 5 $\to$ 7 8 7 6 5 ,最长的是7 8 7 6 5 ,长度为5

题目描述

Alyona has built $ n $ towers by putting small cubes some on the top of others. Each cube has size $ 1×1×1 $ . A tower is a non-zero amount of cubes standing on the top of each other. The towers are next to each other, forming a row. Sometimes Alyona chooses some segment towers, and put on the top of each tower several cubes. Formally, Alyouna chooses some segment of towers from $ l_{i} $ to $ r_{i} $ and adds $ d_{i} $ cubes on the top of them. Let the sequence $ a_{1},a_{2},...,a_{n} $ be the heights of the towers from left to right. Let's call as a segment of towers $ a_{l},a_{l+1},...,a_{r} $ a hill if the following condition holds: there is integer $ k $ ( $ l<=k<=r $ ) such that $ a_{l}&lt;a_{l+1}&lt;a_{l+2}&lt;...&lt;a_{k}&gt;a_{k+1}&gt;a_{k+2}&gt;...&gt;a_{r} $ . After each addition of $ d_{i} $ cubes on the top of the towers from $ l_{i} $ to $ r_{i} $ , Alyona wants to know the maximum width among all hills. The width of a hill is the number of towers in it.

输入输出格式

输入格式


The first line contain single integer $ n $ ( $ 1<=n<=3·10^{5} $ ) — the number of towers. The second line contain $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — the number of cubes in each tower. The third line contain single integer $ m $ ( $ 1<=m<=3·10^{5} $ ) — the number of additions. The next $ m $ lines contain $ 3 $ integers each. The $ i $ -th of these lines contains integers $ l_{i} $ , $ r_{i} $ and $ d_{i} $ ( $ 1<=l<=r<=n $ , $ 1<=d_{i}<=10^{9} $ ), that mean that Alyona puts $ d_{i} $ cubes on the tio of each of the towers from $ l_{i} $ to $ r_{i} $ .

输出格式


Print $ m $ lines. In $ i $ -th line print the maximum width of the hills after the $ i $ -th addition.

输入输出样例

输入样例 #1

5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1

输出样例 #1

2
4
5

说明

The first sample is as follows: After addition of $ 2 $ cubes on the top of each towers from the first to the third, the number of cubes in the towers become equal to $ [7,7,7,5,5] $ . The hill with maximum width is $ [7,5] $ , thus the maximum width is $ 2 $ . After addition of $ 1 $ cube on the second tower, the number of cubes in the towers become equal to $ [7,8,7,5,5] $ . The hill with maximum width is now $ [7,8,7,5] $ , thus the maximum width is $ 4 $ . After addition of $ 1 $ cube on the fourth tower, the number of cubes in the towers become equal to $ [7,8,7,6,5] $ . The hill with maximum width is now $ [7,8,7,6,5] $ , thus the maximum width is $ 5 $ .

Input

题意翻译

现在有$n$个数,$m$个操作,**每次区间加一个数**,对于**每一次**操作,你要找出**最长**的$\ a_l...a_r\ $,满足 $$\exists k\! \in\![l,r],a_l<a_{l+1}<a_{l+2}<...<a_k>a_{k+1}>a_{k+2}>...>a_r$$ 输出其长度。 输入: 第一行一个整数$n$,表示数的个数。 第二行$n$个整数$a_i$。 第三行一个整数$m$,表示操作个数。 下面$m$行,每行$3$个整数,$l_i,r_i,d_i$,表示将$l_i$到$r_i$的数字加$d_i$。 输出: 对于**每个**操作,输出操作完后的答案(见题意)。 样例解释: 1. 5 5 5 5 5 $\to$ 7 7 7 5 5 ,最长的是7 5,长度为2 2. 7 7 7 5 5 $\to$ 7 8 7 5 5 ,最长的是7 8 7 5 ,长度为4 3. 7 8 7 5 5 $\to$ 7 8 7 6 5 ,最长的是7 8 7 6 5 ,长度为5

加入题单

上一题 下一题 算法标签: