segments operation
题号:NC24033
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长为n的连续序列,有m次操作,操作有两种:

1、 对于区间[L,R]的每个元素aimin(ai,x)

2、对于位置x,求包含位置x,最长的且不含0元素的最长的区间的区间和,若x位置为0则输出0

输入描述:

第一行一个数T表示有T组数据(T≤10)。
每组数据的第一行为两个数分别为n,m(1≤n,m≤105)。
每组数据的第二行n个数表示给定的连续序列。
接下来M行每行包含2或4个整数,表示一个操作,具体如下:

操作1: 格式:1 L R x(含义:更新ai=min(ai,x)(L≤i≤R));

操作2: 格式:2 x(含义:对于位置x,求包含位置x,最长的且不含0元素的最长的区间的区间和,若x位置为0则输出0);

所有数字均小于105

输出描述:

对于操作2,每行输出一个数,表示符合题意的区间和。
示例1

输入

复制
1
5 4
5 4 3 2 1
1 1 5 4
2 2
1 2 3 0
2 4

输出

复制
14
3