CF1270H Number of Components 题解

Description

给一个长度为 \(n\) 的数组 \(a\)，\(a\) 中的元素两两不同。

对于每个数对 \((i,j)(i<j)\)，若 \(a_i<a_j\)，则让 \(i\) 向 \(j\) 连一条边。求图中连通块个数。

支持 \(q\) 次修改数组某个位置的值，每次修改后输出图中连通块个数。

\(n,q\le 5\times 10^5,1\le a_i\le 10^6\)，保证任意时刻数组中元素两两不同。

Solution

考虑怎么求一个序列有几个连通块。

首先有个性质是每个连通块一定是一个区间，证明就考虑钦定 \(i<k<j\) 且 \(i\) 和 \(j\) 连通。如果 \(a_i<a_j\)，则 \(a_i<a_k\) 和 \(a_k<a_j\) 必定满足至少一个。

如果 \(a_i>a_j\)，由于 \(i,j\) 连通，所以一定存在 \(x<i\) 且 \(a_i>a_j>a_x\) 或 \(x>j\) 且 \(a_x>a_i>a_j\)。这样就规约到了 \(a_i<a_j\) 的情况。故结论得证。

所以连通块数就是满足 \(\min_{i=1}^{k}{a_i}>\max_{i=k+1}^{n}{a_i}\) 的 \(k\) 的数量。

考虑枚举前缀的最小值 \(x\)，将 \(a\) 数组中大于等于 \(x\) 的位置设成 \(1\)，小于 \(x\) 的位置设成 \(0\)，则合法的 \(x\) 一定满足 \(01\) 序列为 \(11110000\) 的形式，即 \(10\) 的出现次数为 \(1\)。

设 \(cnt_x\) 表示 \(x\) 的 \(01\) 序列中 \(10\) 的出现次数。于是题目转化为求对于所有在 \(a\) 数组中出现了的 \(x\) 中 \(cnt_x=1\) 的 \(x\) 的数量，维护一个值域的线段树即可。

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

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e6 + 5;

int n, q, m;
int a[kMaxN], pos[kMaxN], x[kMaxN], unq[kMaxN];

struct SGT {
  int mi[kMaxN * 4], tag[kMaxN * 4], tot[kMaxN * 4], cnt[kMaxN * 4];

  void pushup(int x) {
    mi[x] = std::min(tot[x << 1] ? mi[x << 1] : 1e9, tot[x << 1 | 1] ? mi[x << 1 | 1] : 1e9);
    tot[x] = tot[x << 1] + tot[x << 1 | 1];
    cnt[x] = 0;
    if (tot[x << 1] && mi[x] == mi[x << 1]) cnt[x] += cnt[x << 1];
    if (tot[x << 1 | 1] && mi[x] == mi[x << 1 | 1]) cnt[x] += cnt[x << 1 | 1];
  }

  void addtag(int x, int v) {
    mi[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(cnt[x] = 1);
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }

  void update1(int x, int l, int r, int ql, int v) {
    if (l == r) return void(tot[x] = v);
    pushdown(x);
    int mid = (l + r) >> 1;
    if (ql <= mid) update1(x << 1, l, mid, ql, v);
    else update1(x << 1 | 1, mid + 1, r, ql, v);
    pushup(x);
  }

  void update2(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;
    update2(x << 1, l, mid, ql, qr, v), update2(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  int query() { return tot[1] && mi[1] == 1 ? cnt[1] : 0; }
} sgt;

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

  for (int i = 0; i <= n + 1; ++i)
    a[i] = std::lower_bound(unq + 1, unq + 1 + m, a[i]) - unq;
  for (int i = 1; i <= q; ++i)
    x[i] = std::lower_bound(unq + 1, unq + 1 + m, x[i]) - unq;
}

void update(int x, int y, int v) {
  if (x > y) sgt.update2(1, 1, m, y + 1, x, v);
}

void dickdreamer() {
  std::cin >> n >> q;
  a[0] = 1e9, a[n + 1] = -1e9;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i <= q; ++i) std::cin >> pos[i] >> x[i];
  discrete();
  sgt.build(1, 1, m);
  for (int i = 1; i <= n; ++i) sgt.update1(1, 1, m, a[i], 1);
  for (int i = 0; i <= n; ++i) update(a[i], a[i + 1], 1);
  for (int i = 1; i <= q; ++i) {
    update(a[pos[i] - 1], a[pos[i]], -1), update(a[pos[i]], a[pos[i] + 1], -1);
    sgt.update1(1, 1, m, a[pos[i]], 0);
    a[pos[i]] = x[i];
    update(a[pos[i] - 1], a[pos[i]], 1), update(a[pos[i]], a[pos[i] + 1], 1);
    sgt.update1(1, 1, m, a[pos[i]], 1);
    std::cout << sgt.query() << '\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;
}