题目描述

给出一个序列，你的任务是求每次操作之后序列中 （a[j]-a[i]）/（j-i）【1<=i<j<=n】的最大值。

操作次数有Q次，每次操作需要将位子p处的数字变成y.

输入描述:

本题包含多组输入，每组输入第一行一个数字n，表示序列的长度。 然后接下来一行输入n个数，表示原先序列的样子。 再接下来一行一个数字Q，表示需要进行的操作的次数。 最后Q行每行两个元素p，y，表示本操作需要将位子p处的数字变成y. 数据范围： 3<=n<=200000 1<=Q<=200000 -1000000000<=a[i]<=1000000000

输出描述:

每组数据输出Q行，每行输出一个浮点数，保留两位小数，表示所求的最大值。

示例1

输入

52 4 6 8 1022 54 9

输出

3.003.00

说明

第一次操作之后的序列变成：2 5 6 8 10 第二次操作之后的序列变成：2 5 6 9 10

备注:

输入只有整形

题解

线段树。

通过观察可以发现，最大值的来源，肯定是相邻两个位置产生的。每次修改会影响两个位置的值，每次查询取整个区间的最大值即可。

#include 
      
       using namespace std; const int maxn = 200000 + 10;int a[maxn], s[4 * maxn];int n, q; void build(int l, int r, int rt) {  if(l == r) {    s[rt] = a[l + 1] - a[l];    return;  }  int mid = (l + r) / 2;  build(l, mid, 2 * rt);  build(mid + 1, r, 2 * rt + 1);  s[rt] = max(s[2 * rt], s[2 * rt + 1]);} void update(int pos, int val, int l, int r, int rt) {  if(l == r) {    s[rt] = val;    return;  }  int mid = (l + r) / 2;  if(pos <= mid) update(pos, val, l, mid, 2 * rt);  else if(pos > mid) update(pos, val, mid + 1, r, 2 * rt + 1);  s[rt] = max(s[2 * rt], s[2 * rt + 1]);} int main() {  while(~scanf("%d", &n)) {    for(int i = 1; i <= n; i ++) {      scanf("%d", &a[i]);    }    build(1, n - 1, 1);    scanf("%d", &q);    while(q --) {      int x, y;      scanf("%d%d", &x, &y);      a[x] = y;      if(x != 1) update(x - 1, a[x] - a[x - 1], 1, n - 1, 1);      if(x != n) update(x, a[x + 1] - a[x], 1, n - 1, 1);      printf("%d.00\n", s[1]);    }  }  return 0;}