Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Gorgeous Sequence

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 18667    Accepted Submission(s): 4509

Problem Description
There is a sequence $a$ of length $n$. We use $a_i$ to denote the $i$-th element in this sequence. You should do the following three types of operations to this sequence.

$0\ x\ y\ t$: For every $x \le i \le y$, we use $min(a_i, t)$ to replace the original $a_i$'s value.
$1\ x\ y$: Print the maximum value of $a_i$ that $x \le i \le y$.
$2\ x\ y$: Print the sum of $a_i$ that $x \le i \le y$.

The first line of the input is a single integer $T$, indicating the number of testcases.

The first line contains two integers $n$ and $m$ denoting the length of the sequence and the number of operations.

The second line contains $n$ separated integers $a_1, \ldots, a_n$ ($\forall 1 \le i \le n, 0 \le a_i < 2^{31}$).

Each of the following $m$ lines represents one operation ($1 \le x \le y \le n, 0\le t < 2^{31}$).

It is guaranteed that $T=100$, $\sum n \le 1000000, \ \sum m \le 1000000$.

For every operation of type $1$ or $2$, print one line containing the answer to the corresponding query.

Sample Input
1 5 5 1 2 3 4 5 1 1 5 2 1 5 0 3 5 3 1 1 5 2 1 5

Sample Output
5 15 3 12

Please use efficient IO method



Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-15 22:54:51, Gzip enabled