题意

给定一个数列 $a$，可以进行若干次操作，每次操作可以选择 $a$ 中出现过至少两次的 $x$，删除掉这两个 $x$，再插入新元素 $x+1$。

有 $q$ 次询问，每次询问都永久地将 $a_x$ 修改为 $y$，即强制在线。求：每次询问后，进行若干次操作，可以得到的最大的数值是多少。

分析

将两个相同的数字 $x$ 替换为一个 $x+1$，不难想到转化为二进制数的进位：$2^x + 2^x = 2^{x + 1}$。

而将 $a_x$ 修改为 $y$，可以类似地转化为，先给二进制数减去 $2^{a_x}$ 再加上一个 $2^y$。

将所有可以进位的位置全部进位，直到不能继续操作，即得到了最大的数值。

于是这道题目就转化成了一个高精度计算二进制加减法的题目。当然，由于数据范围较大，python 等语言自带的高精度运算无法通过此题。

可以使用一段伪代码来表示这个过程。

read n, q, a
for i in range(n):
    ans += 2 ** a[i]
for i in range(q):
    read k, l
    k = k - 1
    ans -= 2 ** a[k]
    a[k] = l
    ans += 2 ** a[k]
    print log2(ans)

注意到二进制数的特殊性：每一位上的值，要么是 $0$，要么是 $1$。同时，这道题目也具有特殊性：每次进行加减法的数字，都是 $2$ 的幂，即某个确定的二进制位。

那么我们只需要在程序中模拟二进制数加减法的进位、退位即可。

考虑用树状数组维护该二进制数的一段区间内，位为 $1$ 的个数。

如果一次加法操作之后，第 $x$ 位的值是 $2$，意味着需要进位。可以二分查找第 $x$ 位之后的第一个 $0$ 的位置 $y$，将第 $y$ 位进到 $1$，而 $x \sim y-1$ 位全部修改为 $0$。

如果一次减法操作之后，第 $x$ 位的值是 $-1$，意味着需要借位退位。可以二分查找第 $x$ 位之后第一个 $1$ 的位置 $y$，将第 $y$ 位的值修改为 $0$，而 $x \sim y-1$ 位全部修改为 $1$。

可以在树状数组当中同时维护差分数组 $d_i$ 和 $(i-1)\times d_i$ 的值，实现区间修改和区间查询。

总时间复杂度是 $\mathcal{O}((n+q)\log^2S)$，其中 $S = \sum a_i$。树状数组常数较小，可以轻松通过。

代码

主函数部分代码较长，主要是因为进位、退位部分代码写的比较臭，可重用性比较差，复制粘贴了三遍（

struct FenwickRange {
  int n;
  std::vector<ll> a, b;
  FenwickRange() {}
  FenwickRange(int n) : n(n) { a.resize(n + 1, 0), b.resize(n + 1, 0); }
  int lowbit(int x) { return x & -x; }
  void rangeAdd(int l, int r, ll val) {
    if (l > r) return;
    add(a, l, val);
    add(b, l, (l - 1) * val);
    add(a, r + 1, -val);
    add(b, r + 1, -r * val);
  }
  ll rangeSum(int l, int r) {
    if (l > r) return 0;
    if (l == 0) return rangeSum(1, r);
    ll R = r * sum(a, r) - sum(b, r);
    ll L = (l - 1) * sum(a, l - 1) - sum(b, l - 1);
    return R - L;
  }

 private:
  void add(std::vector<ll>& a, int x, ll val) {
    while (x <= n) {
      a[x] += val;
      x += lowbit(x);
    }
  }
  ll sum(std::vector<ll>& a, int pos) {
    ll res = 0;
    while (pos) {
      res += a[pos];
      pos -= lowbit(pos);
    }
    return res;
  }
};

void solution() {
  int n, q;
  read(n, q);
  std::vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) read(a[i]);
  const int maxBit = 2e5 + 50;
  FenwickRange fwk(maxBit);
  for (int i = 1; i <= n; ++i) {
    fwk.rangeAdd(a[i], a[i], 1);
    if (fwk.rangeSum(a[i], a[i]) >= 2) {  // 进位
      assert(fwk.rangeSum(a[i], a[i]) == 2);
      // 二分 a[i] 这一位之后的第一个 0 的位置
      int l = 1, r = maxBit - a[i], mid = (l + r) / 2;
      while (l < r) {
        int cnt1 = fwk.rangeSum(a[i] + 1, a[i] + mid);
        int need = mid;
        if (cnt1 >= need) {
          assert(cnt1 == need);
          l = mid + 1;
        } else {
          r = mid;
        }
        mid = (l + r) / 2;
      }
      fwk.rangeAdd(a[i], a[i], -2);
      assert(fwk.rangeSum(a[i] + 1, a[i] + mid - 1) == mid - 1);
      fwk.rangeAdd(a[i] + 1, a[i] + mid - 1, -1);
      fwk.rangeAdd(a[i] + mid, a[i] + mid, 1);
    }
  }

  for (int i = 1; i <= q; ++i) {
    int x, y;
    read(x, y);  // a[x] = y
    int del = a[x];
    fwk.rangeAdd(del, del, -1);
    if (fwk.rangeSum(del, del) <= -1) {  // 退位
      assert(fwk.rangeSum(del, del) == -1);
      // 二分 del 这一位之后的第一个 1 的位置
      int l = 1, r = maxBit - del, mid = (l + r) / 2;
      while (l < r) {
        int cnt1 = fwk.rangeSum(del + 1, del + mid);
        int cnt0 = mid - cnt1;
        int need = mid;
        if (cnt0 >= need) {
          assert(cnt0 == need);
          l = mid + 1;
        } else {
          r = mid;
        }
        mid = (l + r) / 2;
      }
      fwk.rangeAdd(del, del, 2);
      assert(mid - 1 - fwk.rangeSum(del + 1, mid - 1) == mid - 1);
      fwk.rangeAdd(del + 1, del + mid - 1, 1);
      fwk.rangeAdd(del + mid, del + mid, -1);
    }
    a[x] = y;
    fwk.rangeAdd(y, y, 1);
    if (fwk.rangeSum(y, y) >= 2) {  // 进位
      assert(fwk.rangeSum(y, y) == 2);
      // 二分 y 这一位之后的第一个 0 的位置
      int l = 1, r = maxBit - y, mid = (l + r) / 2;
      while (l < r) {
        int cnt1 = fwk.rangeSum(y + 1, y + mid);
        int need = mid;
        if (cnt1 >= need) {
          assert(cnt1 == need);
          l = mid + 1;
        } else {
          r = mid;
        }
        mid = (l + r) / 2;
      }
      fwk.rangeAdd(y, y, -2);
      assert(fwk.rangeSum(y + 1, y + mid - 1) == mid - 1);
      fwk.rangeAdd(y + 1, y + mid - 1, -1);
      fwk.rangeAdd(y + mid, y + mid, 1);
    }

    // 查找最高位
    int l = 1, r = maxBit, mid = (l + r + 1) / 2;
    while (l < r) {
      int cnt1 = fwk.rangeSum(mid, r);
      if (cnt1 >= 1) {
        l = mid;
      } else {
        r = mid - 1;
      }
      mid = (l + r + 1) / 2;
    }
    print(mid);
  }
}