LOJ #3538. 「JOI Open 2018」冒泡排序 2 题解

Description

冒泡排序是一个对序列排序的算法。现在我们要将一个长度为 $N$ 的序列 $A_0,A_1,\ldots ,A_{N-1}$​ 按不降顺序排序。当两个相邻的数没有按正确顺序排列时，冒泡排序会交换这两个数的位置。每次扫描这个序列就进行这种交换。更确切地说，在一趟扫描中，对于 $i=0,1,\ldots ,N-2$，并按这个顺序，如果 $A_i>A_{i+1}$​，那么我们就交换这两个数的位置。众所周知任何序列经过有限趟扫描后一定可以按非降顺序排好序。对于一个序列 $A$，我们定义用冒泡排序的扫描趟数为使用如上算法使得 $A$ 排好序的情况下所扫描的趟数。

JOI 君有一个长度为 $N$ 的序列 $A$。他打算处理 $Q$ 次修改 $A$ 的值的询问。更明确地说，在第 $(j+1)\ (0\le j\le Q-1)$ 次询问，$A_{X_j}$ 的值会变为 $V_j$。

JOI 君想知道处理每次修改之后，用冒泡排序的扫描趟数。

$N,Q\leq 5\times 10^5$。

Solution

首先容易发现答案为 $\displaystyle\max_{i=1}^{n}{\left(\sum_{j=1}^{i-1}{[a_j>a_i]}\right)}$，直接维护需要用树套树或者分块，可能会比较慢。

注意到一个可能作为答案的 $i$ 一定是严格后缀最小值，否则换成任意一个后缀里比它更小的数会更优。当 $i$ 是后缀最小值时，上面那个式子可以弱化条件，即 $\sum_{j=1}^{i-1}{[a_j>a_i]}=\sum_{j=1}^{\color{red}{n}}{[a_j>a_i]}-(n-i)$。

因为减掉的 $n-i$ 只会更多，所以不会算优，而最优解一定可以用这个表示，那么对于每个数值维护其最后一次出现的位置即可。

时间复杂度：$O((n+q)\log n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e6 + 5;

int n, q, m;
int a[kMaxN], x[kMaxN], v[kMaxN], unq[kMaxN];
std::set<int> st[kMaxN];

int getid(int x) { return std::lower_bound(unq + 1, unq + 1 + m, x) - unq; }

void discrete() {
  std::sort(unq + 1, unq + 1 + m);
  m = std::unique(unq + 1, unq + 1 + m) - (unq + 1);
  for (int i = 1; i <= n; ++i) a[i] = getid(a[i]);
  for (int i = 1; i <= q; ++i) v[i] = getid(v[i]);
}

struct SGT {
  int mx[kMaxN * 4], tag[kMaxN * 4];
  void pushup(int x) { mx[x] = std::max(mx[x << 1], mx[x << 1 | 1]); }
  void addtag(int x, int v) { mx[x] += v, tag[x] += v; }
  void pushdown(int x) {
    if (tag[x]) addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]), tag[x] = 0;
  }
  void build(int x, int l, int r) {
    if (l == r) return void(mx[x] = *st[l].rbegin() - n);
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void update(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }
} sgt;

void update(int x, int v) {
  sgt.update(1, 1, m, 1, a[x] - 1, -1);
  int lst = *st[a[x]].rbegin();
  st[a[x]].erase(x);
  sgt.update(1, 1, m, a[x], a[x], *st[a[x]].rbegin() - lst);

  a[x] = v;
  sgt.update(1, 1, m, 1, a[x] - 1, 1);
  lst = *st[a[x]].rbegin();
  st[a[x]].emplace(x);
  sgt.update(1, 1, m, a[x], a[x], *st[a[x]].rbegin() - lst);
}

void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i], unq[++m] = a[i];
  for (int i = 1; i <= q; ++i) {
    std::cin >> x[i] >> v[i];
    ++x[i];
    unq[++m] = v[i];
  }
  discrete();
  for (int i = 1; i <= m; ++i) st[i].emplace(-1e9);
  for (int i = 1; i <= n; ++i) st[a[i]].emplace(i);
  sgt.build(1, 1, m);
  for (int i = 1; i <= n; ++i) sgt.update(1, 1, m, 1, a[i] - 1, 1);
  for (int i = 1; i <= q; ++i) {
    update(x[i], v[i]);
    std::cout << sgt.mx[1] << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}