ARC85-NRE

發表於 更新於 Disqus：

你有一個序列長度為 $n$ 的序列 $a$，一開始 $a_i=0\ \forall 1\le i\le n$，然後輸入會給你一個長度為 $n$ 的序列 $b$，並且 $b_i \in \{0, 1\}$。

然後輸入會給你可以使用的 $Q$ 筆操作 $l_i,\ r_i$，代表把 $a_l,a_{l+1},a_{l+2},\cdots,a_{r-1},a_r$ 都設成 1。

你可以挑一些操作出來把他給用在序列上，可以全用也可以不用任何操作。
問你操作完的最小 hamming distance 是多少。
其中 hamming distnace 為滿足 $a_i\neq b_i$ 的 $i$ 的數量。

$N, Q\le 2\times 10^5$

這題真的是個酷酷題目。
首先我們考慮 dp，如果 $dp_i$ 為考慮前 $i$ 個答案之類的，在遇到線段相交的情形很容易爛掉。

所以一個維度的 dp 似乎沒辦法解決問題，只好多用一維紀錄當前這格是否為 $1$。

可是如果 $dp_{i,j}$ 的 $j$ 只有紀錄「是不是」的狀態也很難做（你會不知道你的操作右界是作到多少）。

所以改成令 $dp_{i,j}$ 為考慮前 $i$ 格以及所有左界不超過 $i$ 的操作的答案，且最後一個操作的右界是 $j$（如果還沒實行過操作則 $j=0$），換句話說：區間 $[i,j]$ 都是 $1$（如果 $j\lt i$ 代表第 $i$ 格是 $0$）。

那這樣就很好做了呀！
當我們的 $i$ 進到了某個操作的左界，且目前的 $j$ 不超過那個操作的右界，那實施了這個操作的話就會造成 $j$ 被更新。

然後就能順便根據 $b$ 的值來決定當前哪些的狀態答案會增加。更正式的來說令 $cost_{i, j}$ 代表當前的狀態要不要增加答案，則：

$$cost_{i, j}=\begin{cases} 1 & \text{if}\ ( b_i=0\ \&\&\ i\le j)\ ||\ (b_i=1\ \&\&\ j\lt i) \\ 0 & \text{otherwise} \end{cases}$$
接著是 dp 轉移式：
$$dp_{i, j} = cost_{i, j} + \begin{cases} \min_{0\le k\le i} dp_{i-1,k} & \text{if}\ \exists c \text{ such that } (l_c=i\ \&\&\ r_c=j) \\ dp({i-1,j}) & \text{otherwise} \end{cases}$$
如果你像我一樣看到數學式會怕的話可以看 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
int dp[N][N], b[N]; // dp[i][j] = INF forall i,j
vector<int> que[N]; // right bounds of queries that left bounds is i
for(int i = 1; i <= n; i++)
	cin >> b[i];
for(int i = 0; i < q; i++) {
	int l, r;
	cin >> l, r;
	que[l].push_back(r);
}
dp[0][0] = 0;
for(int i = 1; i <= n; i++) {
	for(int j = 0; j <= n; j++)
		dp[i][j] = dp[i - 1][j];

	for(int r : que[i]) {
		for(int k = 0; k <= i; k++)
			dp[i][r] = min(dp[i][r], dp[i - 1][k]);
	}

	if(b[i] == 1) {
		for(int j = 0; j < i; j++)
			dp[i][j]++;
	}
	else {
		for(int j = i; j <= n; j++)
			dp[i][j]++;
	}
}

但我們沒解決根本上的問題：狀態數就已經是 $\mathcal{O}(N^2)$ 了。

這就是這題的特點，雖然沒辦法再減少狀態數了，可是轉移式十分規律。
每到一個新的 $i$，除了那些詢問的右界以外，剩下都只是單純的區間加值。而詢問的右界也不難，只是前綴查詢最小值再單點修改而已。

這些都是可以用線段樹作到的。區間加值的操作只會做 $\mathcal{O}(N)$ 次，而前綴查詢最小值以及單點修改只會做 $\mathcal{O}(Q)$ 次。總共複雜度會是 $\mathcal{O}(NlogN + QlogN)$。

雖然狀態數是 $\mathcal{O}(N^2)$，但由於轉移很規律，所以透過資料結構我們只在以上的複雜度就能把全部的狀態算完了！

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
	cerr << "\e[1;33m" << s << " = [";
	while(l != r) {
		cerr << *l;
		cerr << (++l == r ? ']' : ',');
	}
	cerr << "\e[0m\n";
}

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-7;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

const int N = 2e5 + 25;
struct segtree {
	int arr[N << 1], tag[N], n;
	void init(int _n) {
		n = _n;
		memset(arr, 0x3f, sizeof arr);
	}
	void upd(int p, int v) {
		arr[p] += v;
		if(p < n)
			tag[p] += v;
	}
	void push(int p) {
		for(int h = __lg(p); ~h; h--) {
			int i = p >> h;
			upd(i, tag[i >> 1]);
			upd(i ^ 1, tag[i >> 1]);
			tag[i >> 1] = 0;
		}
	}
	void pull(int p) {
		for(; p > 1; p >>= 1)
			arr[p >> 1] = min(arr[p], arr[p ^ 1]) + tag[p >> 1];
	}
	void edt(int p, int v) {
		p += n;
		push(p);
		arr[p] = min(arr[p], v);
		pull(p);
	}
	void add(int l, int r, int v) {
		int tl = l + n, tr = r + n - 1;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				upd(l++, v);
			if(r & 1)
				upd(--r, v);
		}
		pull(tl); pull(tr);
	}
	int que(int l, int r) {
		int res = INF;
		push(l + n); push(r + n - 1);
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				res = min(res, arr[l++]);
			if(r & 1)
				res = min(res, arr[--r]);
		}
		return res;
	}
} tree;

signed main() {
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	for(int i = 1; i <= n; i++)
		cin >> arr[i];
	tree.init(n + 1);
	tree.edt(0, 0);

	vector<vector<int>> que(n + 1);
	int q;
	cin >> q;
	for(int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		que[l].push_back(r);
	}
	for(int i = 1; i <= n; i++) {
		for(int r : que[i]) {
			tree.edt(r, tree.que(0, r + 1));
		}
		if(arr[i])
			tree.add(0, i, 1);
		else
			tree.add(i, n + 1, 1);
	}
	cout << tree.que(0, n + 1) << '\n';
}