CF1270H Number of Components [线段树]

Number of Components

神仙题。。。

观察可以发现,如果图分成了两个联通块,一定存在i,使得\min_{ j \leq i } A_j > \max_{j > i} A_j

我们称这个位置为分界点。那么只需找出有多少分界点。

考虑分界点A_i = x,令> x的数为1\leq x的为0,形成01序列。特别的,令A_0 = + \infty, A_{n+1} = 0

可以发现,如果x是分界点的数,那么原数列为11110000的形式。

因为A_0 = + \infty, A_{n+1} = 0,在序列为11110000时,0,1的分界点最少,是1个。

所以只需找出有多少个x,满足代入后分界点是一个即可。

这个东西是可以用线段树维护的。具体来说就是在插入删除的时候分类讨论进行+1,-1。实现非常巧妙,可以看代码...

#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1e6 + 233;

int n, q, A[N], pos[N], val[N], lim;

#define ls(p) p << 1
#define rs(p) p << 1 | 1

int min[N * 4], cnt[N * 4], tag[N * 4];

inline void pushup(int p) {
  if (min[ls(p)] == min[rs(p)]) {
    min[p] = min[ls(p)];
    cnt[p] = cnt[ls(p)] + cnt[rs(p)];
  } else if (min[ls(p)] < min[rs(p)]) {
    min[p] = min[ls(p)];
    cnt[p] = cnt[ls(p)];
  } else {
    min[p] = min[rs(p)];
    cnt[p] = cnt[rs(p)];
  }
}

inline void push(int p, int v) {
  min[p] += v;
  tag[p] += v;
}

inline void pushdown(int p) {
  if (tag[p]) {
    push(ls(p), tag[p]);
    push(rs(p), tag[p]);
    tag[p] = 0;
  }
}

inline void modify(int p, int x, int v, int L, int R) {
  if (L == R) {
    cnt[p] += v;
    return;
  }
  pushdown(p);
  int mid = (L + R) >> 1;
  if (x <= mid)
    modify(ls(p), x, v, L, mid);
  else
    modify(rs(p), x, v, mid + 1, R);
  pushup(p);
}

inline void add(int p, int l, int r, int v, int L, int R) {
  if (l <= L && r >= R)
    return push(p, v);
  pushdown(p);
  int mid = (L + R) >> 1;
  if (l <= mid)
    add(ls(p), l, r, v, L, mid);
  if (r > mid)
    add(rs(p), l, r, v, mid + 1, R);
  pushup(p);
}

int query(int p, int l, int r, int L, int R) {
  if (l <= L && r >= R) {
    if (min[p] == 1)
      return cnt[p];
    return 0;
  }
  pushdown(p);
  int mid = (L + R) >> 1, ret = 0;
  if (l <= mid)
    ret = query(ls(p), l, r, L, mid);
  if (r > mid)
    ret += query(rs(p), l, r, mid + 1, R);
  return ret;
}

inline void update(int x, int y, int v) {
  if (x == y) return;
  if (x > y) std::swap(x, y);
  add(1, x, y - 1, v, 0, lim);
}

int main() {
  n = rd(), q = rd();
  for (int i = 1; i <= n; ++i) {
    A[i] = rd();
    lim = std::max(lim, A[i]);
  }
  for (int i = 1; i <= q; ++i) {
    pos[i] = rd();
    val[i] = rd();
    lim = std::max(lim, val[i]);
  }
  A[0] = ++lim;
  for (int i = 0; i <= n; ++i) {
    update(A[i], A[i + 1], 1);
    modify(1, A[i], 1, 0, lim);
  }
  for (int i = 1; i <= q; ++i) {
    int p = pos[i], v = val[i];
    modify(1, A[p], -1, 0, lim);
    update(A[p - 1], A[p], -1);
    update(A[p], A[p + 1], -1);
    modify(1, v, 1, 0, lim);
    update(A[p - 1], v, 1);
    update(v, A[p + 1], 1);
    A[p] = v;
    printf("%d\n", query(1, 1, lim - 1, 0, lim));
  }
  return 0;
}

发表评论

电子邮件地址不会被公开。必填项已用 * 标注