Strict Evaluation

View as PDF
Submit solution
Points: 17
Time limit: 0.5s
Memory limit: 256M
Author:
richardzhang
Problem type

You have an array of N (1 \le N \le 100\,000) elements, indexed from 1 to N. There are Q (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] by v.
  • 2 l r v Make each value in the range [l,r] equal to v (i.e. for each element a_i, such that l \le i \le r, set a_i:=v).
  • 3 l r Output the minimum value in the range [l,r].

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

Input Specification

The first line has N and Q.

The second line has N integers, the original array.

The next 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

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

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.