哈尔滨理工大学第七届程序设计竞赛决赛（网络赛-高年级组）E

题目描述

给出一个序列，你的任务是求每次操作之后序列中（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

输入

输出

3.00
3.00

说明

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

备注:

输入只有整形

题解

线段树。

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

#include <bits/stdc++.h>
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
", s[1]);
    }
  }
  return 0;
}