Strict Evaluation

Points: 17

Time limit: 0.5s

Memory limit: 256M

Author:

Problem type

You have an array of $N$ ~N~ $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~ elements, indexed from $1$ ~1~ to $N$ ~N~. There are $Q$ ~Q~ $(1 \le Q \le 100\,000)$ ~(1 \le Q \le 100\,000)~ operations you need to perform on it.

Each operation is one of the following:

1 l r v Increment each value in the range $[l,r]$ ~[l,r]~ by $v$ ~v~.
2 l r v Make each value in the range $[l,r]$ ~[l,r]~ equal to $v$ ~v~ (i.e. for each element $a_i$ ~a_i~, such that $l \le i \le r$ ~l \le i \le r~, set $a_i:=v$ ~a_i:=v~).
3 l r Output the minimum value in the range $[l,r]$ ~[l,r]~.

In operations 1 and 2, $v$ ~v~ is guaranteed to be an integer in the range $[1,100\,000]$ ~[1,100\,000]~. Every value in the starting array is also guaranteed to be in this range.

Input Specification

The first line has $N$ ~N~ and $Q$ ~Q~.

The second line has $N$ ~N~ integers, the original array.

The next $Q$ ~Q~ lines each contain an operation in the format described above.

Output Specification

For each operation of type 3, output the answer on its own line.

Sample Input

Sample Output

2
5

Comments

0

Evan commented on Feb. 3, 2022, 2:58 p.m. ← edit 2 →

Can someone take a look at my code and see whats wrong? I got 100 testcases AC and 101st testcase WA. I am very sad rn.

https://dmoj.ca/src/4277500

Edit: nvm I passed by putting #define int long long

1

Nils_Emmenegger commented on April 17, 2021, 9:34 p.m.

If you are using c++, defining your push_down function as inline may provide a speed boost.

0

Dan13llljws commented on Oct. 16, 2020, 12:09 a.m.

https://cses.fi/problemset/task/1735

-4
magicalsoup commented on Jan. 4, 2020, 4:21 p.m.
TFW you couldn't figure out what was wrong with your code when you used scanf instead of cin in your build function and you used

cin.tie(0); cin.sync_with_stdio(0)

And thought your implementation was wrong.

11

4fecta commented on Jan. 4, 2020, 3:57 a.m.

Can this be called Segment Tree Test 2?

5

omaewamoushindeiru commented on July 19, 2022, 8:30 p.m. ← edit 2 →

the problem setter is likely too lazy to rename the problem...

5

richardzhang commented on Jan. 9, 2020, 6:16 a.m.

I pretty much created it with the intent of just that, because I couldn't find a template problem that had both range increment and range assignment together to test things on lolol.