#P51779. 「LOJ」 线段树:关于时间
「LOJ」 线段树:关于时间
题目描述
有 个整数 组成一个序列。有一个存储三元组的列表,开始时该列表为空。
有 个操作,这些操作分为两种:
- 将 加入列表中。
- 求 。
每执行完一个操作,就读取一遍列表,对于其中的每一组 , 都加上 (这不算做操作)。
输入格式
第一行一个整数 ,表示序列长度。
第二行 个整数。
第三行一个整数 ,表示操作数。
然后 行,先输入一个数 , 为 或 。
- 若 为 ,读入 个整数 。
- 若 为 ,读入 个整数 。
输出格式
对于每个操作 ,输出一行,一个整数, 。
样例
3
1 2 3
4
1 1 3 1
2 1 1
1 2 3 2
2 2 3
2
15
列表 | 输出 | ||
---|---|---|---|
开始 | 1 2 3 |
||
1 1 3 1 |
1 3 1 < |
||
读取列表 | 1 3 1 |
2 3 4 |
|
2 1 1 |
1 3 1 |
2 |
|
读取列表 | 1 3 1 |
3 4 5 |
|
1 2 3 2 |
1 3 1 2 3 2 < |
||
读取列表 | 1 3 1 2 3 2 |
4 7 8 |
|
2 2 3 |
1 3 1 2 3 2 |
15 |
|
读取列表 | 1 3 1 2 3 2 |
5 10 11 |
数据范围与提示
对于 的数据,暴力可过。
对于 的数据, , 。