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$。实现非常巧妙，可以看代码…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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;
}