给定一个长度为nn的序列aia_i，序列的每个位置对应着图上的一个点，点ii与点jj之间存在连边，当且仅当 。现在有qq次修改操作，每次操作会修改某个位置上的值，你需要在每次修改之后回答图中有多少个联通块

n,q≤5×105,ai≤106n, q \leq 5 \times 10^5, a_i \leq 10^6

CF1270H

Solution

不难发现，一个联通块一定是序列上的一段区间。即原序列被若干个分界点分成若干个联通块，且对于每个分界点，一定满足往前的前缀minmin不小于往后的后缀maxmax。我们需要找到所有的分界点。

但是不好直接在序列上进行维护，因为修改一个数字可以会修改很多连边，于是可以考虑每一种权值对答案的贡献。

为了方便边界处理，首先设a0=∞,an+1=0a_0 = \infty, a_{n + 1} = 0。

对于权值xx而言，若把序列中所有≥x\ge x的数设为11，<x< x的数设为00，那么权值xx是分界点当且仅当新序列只存在一个0101交界处(即新序列形如1111100011111000)

考虑用线段树对权值维护一个函数f(x)f(x)，表示对于权值xx而言，新序列0101交界处的个数。显然只有当f(x)=1f(x) = 1的时候，该权值才会产生贡献。

考虑如何处理修改。不难发现修改一个位置的值的时候，只需要考虑和相邻两个位置大小关系的变化，在线段树上对于f(x)f(x)区间加减就可以了，所以线段树每个节点维护的是f(x)f(x)等于当前区间f(x)f(x)最小值的个数

需要注意只有在序列中出现了的权值需要考虑贡献，所以在线段树上还要维护一个是否存在的标记，以维护权值的出现和消失

Code

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 5e5;
const int MAXM = 1e6 + 1;

int N, Q;
int A[MAXN + 5], times[MAXM + 5];

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r

	const int MAX_NODE = MAXM << 2;

	struct info
	{
		int min, cnt, chk, tag;

		info (int _min = 0, int _cnt = 0, int _chk = 0, int _tag = 0) { min = _min, cnt = _cnt, chk = _chk, tag = _tag; }

		inline info operator + (const info &rhs) const
		{
			info o;
			o.tag = 0;
			o.min = min < rhs.min ? min : rhs.min;

			if (min < rhs.min) o.cnt = cnt;
			else if (min > rhs.min) o.cnt = rhs.cnt;
			else o.cnt = cnt + rhs.cnt;

			return o;
		}
		
	} node[MAX_NODE + 5];

	inline void push_up (int o) { node[o] = node[ls] + node[rs]; }

	inline void push_down (int o)
	{
		int &tag = node[o].tag;
		if (!tag) return ;
		node[ls].min += tag, node[ls].tag += tag;
		node[rs].min += tag, node[rs].tag += tag;
		tag = 0;
	}

	inline void update (int o, int l, int r, int x, int y, int val)
	{
		if (x > y) return ;
		if (x <= l && r <= y)
		{
			node[o].min += val, node[o].tag += val;
			return ;
		}

		push_down (o);
		if (x <= mid) update (lson, x, y, val);
		if (y > mid) update (rson, x, y, val);

		push_up (o);
	}

	inline void insert (int o, int l, int r, int x)
	{
		if (l == r) return void (node[o].chk = node[o].cnt = 1);
		push_down (o);
		if (x <= mid) insert (lson, x);
		else insert (rson, x);
		push_up (o);
	}

	inline void erase (int o, int l, int r, int x)
	{
		if (l == r) return void (node[o].chk = node[o].cnt = 0);
		push_down (o);
		if (x <= mid) erase (lson, x);
		else erase (rson, x);
		push_up (o);
	}

#undef mid
}

inline void Init ()
{
	A[0] = MAXM, A[N + 1] = 0;
	for (int i = 1; i <= N + 1; ++i) 
	{
		int l = min (A[i], A[i - 1]) + 1, r = max (A[i], A[i - 1]);
		SEG :: update (1, 1, MAXM, l, r, 1);
	}

	for (int i = 1; i <= N; ++i) ++times[A[i]], SEG :: insert (1, 1, MAXM, A[i]);
}

inline void Update (int l, int r, int val) { SEG :: update (1, 1, MAXM, l, r, val); }

inline void Solve ()
{
	Init ();
	while (Q--)
	{
		int x = read<int>(), y = read<int>();

		Update (min (A[x], A[x - 1]) + 1, max (A[x], A[x - 1]), -1);
		Update (min (A[x], A[x + 1]) + 1, max (A[x], A[x + 1]), -1);
		Update (min (y, A[x - 1]) + 1, max (y, A[x - 1]), 1);
		Update (min (y, A[x + 1]) + 1, max (y, A[x + 1]), 1);

		if ((--times[A[x]]) == 0) SEG :: erase (1, 1, MAXM, A[x]);
		if ((++times[y]) == 1) SEG :: insert (1, 1, MAXM, y);

		A[x] = y;

		printf("%d\n", SEG :: node[1].cnt);
	}
}

inline void Input ()
{
	N = read<int>(), Q = read<int>();
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
}

int main ()
{

#ifdef hk_cnyali
	freopen("H.in", "r", stdin);
	freopen("H.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}