TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4527
  • Problem
  • P4527「雅礼集训 2017 Day1」市场
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 2s,256m
    Description

    从前有一个贸易市场,在一位执政官到来之前都是非常繁荣的,自从他来了之后,发布了一系列奇怪的政令,导致贸易市场的衰落。

    \(n\) 个商贩,从 \(0 \sim n - 1\) 编号,每个商贩的商品有一个价格 \(a_i\),有两种政令:

    1. \(l, r, c\),对于 \(i \in [l, r], a_i \leftarrow a_i + c\)
    2. \(l, r, d\),对于 \(i \in [l, r], a_i \leftarrow \lfloor {a_i}/{d} \rfloor\)

    现在有一个外乡的旅客想要了解贸易市场的信息,有两种询问方式:

    1. 给定 $ l, r $,求 $ \min_{i \in [l, r]} a_i $
    2. 给定 $ l, r $,求 $ \sum_{i\in [l, r]} a_i $
    Input Format

    第一行为两个空格隔开的整数 \(n, q\) 分别表示商贩个数和政令 + 询问个数。
    第二行包含 \(n\) 个由空格隔开的整数 \(a_0 \sim a_{n - 1}\)
    接下来 \(q\) 行,每行表示一个操作,第一个数表示操作编号 \(1 \sim 4\),接下来的输入和问题描述一致。

    Output Format

    对于每个 3、4 操作,输出询问答案。

    Sample Input

    10 10
    -5 -4 -3 -2 -1 0 1 2 3 4
    1 0 4 1
    1 5 9 1
    2 0 9 3
    3 0 9
    4 0 9
    3 0 1
    4 2 3
    3 4 5
    4 6 7
    3 8 9

    Sample Output

    -2
    -2
    -2
    -2
    0
    1
    1

    Hint

    对于 \(30\%\) 的数据,\(n, q \leq 10 ^ 3\)
    对于 \(60\%\) 的数据,保证数据随机;
    对于 \(100\%\) 的数据,\(1 \leq n, q \leq 10 ^ 5, 0 \leq l \leq r \leq n - 1, c \in [-10 ^ {4}, 10 ^ 4], d \in [2, 10 ^ 9]\)