• [F] 卖瓜

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Gealo突发奇想,想去卖西瓜。于是他进了n个西瓜,他将西瓜排成一行,编号1到n,重量a[1]到a[n]。
    假设顾客有两种操作,操作1是问Gealo西瓜编号l到r之间的最大重量和最小重量之差是多少。
    操作2是买去编号为i的瓜,而之后Gealo将一个新的重量为x的瓜补上编号为i的位置。
  • 输入
  • 输入一个数t(t <= 5),表示有t组数据。
    接下来每组数据第一行输入两个数n(1 <= n <= 10^4)和q(1 <= q <= 10^4),表示有n个瓜和q个操作。
    接下来一行输入n个数a[1]到a[n],表示瓜的重量(0 < a[i] <= 10^9)。
    接下来q行,有两种操作:
    1 l r 表示操作一(1 <= l <= r <= n)
    2 i x 表示操作二(1 <= i <= n) (0 < x <= 10^9)

  • 输出
  • 对于每一个操作一,输出一行区间最大最小的重量之差。
  • 样例输入
  • 1
    4 3
    1 4 3 2
    1 1 4
    2 2 9
    1 1 4
  • 样例输出
  • 3
    8
    
  • 提示
  • 来源
  • 本站或者转载
  • 操作

显示春菜