Language: C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 2e5 + 100, INF = 1e9;
ll n;
vector<ll> vec;

int dp[SZ], tree[SZ * 8], p[SZ * 8];
vector<int> seg[SZ * 4];
map<int, int> mp[SZ * 4];

void pre(int v, int l, int r, int askl, int askr, int q) {
	if (l >= askr || r <= askl) return;

	if (l >= askl && r <= askr) {
		seg[v].push_back(q);
		return;
	}

	int mid = (l + r) / 2;
	pre(v * 2 + 1, l, mid, askl, askr, q);
	pre(v * 2 + 2, mid, r, askl, askr, q);
}

void push(int v) {
	for (int i = 1; i <= 2; i++) {
		tree[v * 2 + i] += p[v];
		p[v * 2 + i] += p[v];
	}
	p[v] = 0;
}

void add(int v, int l, int r, int askl, int askr) {
	push(v);
	if (l >= askr || r <= askl) return;

	if (l >= askl && r <= askr) {
		tree[v]++;
		p[v]++;
		return;
	}

	int mid = (l + r) / 2;
	add(v * 2 + 1, l, mid, askl, askr);
	add(v * 2 + 2, mid, r, askl, askr);
}

vector<ll> fn[SZ * 4];
ll brd[SZ * 4];

ll get_mx(int v, int l, int r, int askl, int askr, int ind) {
	if (l == r) return -INF;
	if (l >= askr || r <= askl) return -INF;

	if (l >= askl && r <= askr) return fn[ind][v];

	int mid = (l + r) / 2;
	return max(get_mx(v * 2 + 1, l, mid, askl, askr, ind), get_mx(v * 2 + 2, mid, r, askl, askr, ind));
}

void upd_f(int v, int l, int r, int pos, int val, int ind) {
	if (l == r - 1) {
		fn[ind][v] = val;
	}
	else {
		int mid = (l + r) / 2;
		if (pos < mid) {
			upd_f(v * 2 + 1, l, mid, pos, val, ind);
		}
		else {
			upd_f(v * 2 + 2, mid, r, pos, val, ind);
		}
		fn[ind][v] = max(fn[ind][v * 2 + 1], fn[ind][v * 2 + 2]);
	}
}


void rec(int v, int l, int r) {
	if (l == r - 1) {
		sort(seg[v].begin(), seg[v].end());
		auto it = unique(seg[v].begin(), seg[v].end());
		seg[v].erase(it, seg[v].end());

		fn[v].resize(seg[v].size() * 4);
		brd[v] = seg[v].size();
		for (int i = 0; i < seg[v].size(); i++) {
			mp[v][seg[v][i]] = i;
		}
	}
	else {
		int mid = (l + r) / 2;
		rec(v * 2 + 1, l, mid);
		rec(v * 2 + 2, mid, r);
		sort(seg[v].begin(), seg[v].end());
		auto it = unique(seg[v].begin(), seg[v].end());
		seg[v].erase(it, seg[v].end());

		if (v == 1) {
			cout << "";
		}
		fn[v].resize(seg[v].size() * 4);
		brd[v] = seg[v].size();
		for (int i = 0; i < seg[v].size(); i++) {
			mp[v][seg[v][i]] = i;
		}
	}
}

ll get(int v, int l, int r, int askl, int askr, int ind) {
	if (l == r) return -INF;
	if (l >= askr || r <= askl) return -INF;

	if (l >= askl && r <= askr) {
		ll vl = 0;
		get_mx(0, 0, brd[v], 0, mp[v][ind], v);
		return vl;
	}

	int mid = (l + r) / 2;
	return max(get(v * 2 + 1, l, mid, askl, askr, ind), get(v * 2 + 2, mid, r, askl, askr, ind));
}

void upd(int v, int l, int r, int pos, int val, int ind) {
	if (l == r - 1) {
		if (mp[v].find(ind) != mp[v].end()) {
			upd(0, 0, brd[v], mp[v][ind], val, v);
		}
	}
	else {
		int mid = (l + r) / 2;
		if (pos < mid) {
			upd(v * 2 + 1, l, mid, pos, val, ind);
		}
		else {
			upd(v * 2 + 2, mid, r, pos, val, ind);
		}

		if (mp[v].find(ind) != mp[v].end()) {
			upd_f(0, 0, brd[v], mp[v][ind], val, v);
		}
	}
}

int main() {
	fastInp;

	cin >> n;
	vec.resize(n);
	for (auto &cur : vec) cin >> cur;

	ll q;
	cin >> q;

	vector<vector<ll>> vls;
	vector<ll> pref(1);
	for (auto cur : vec) {
		pref.push_back(pref.back() + (cur == 0));
	}

	vls.resize(n + 2);
	while (q--) {
		int l, r;
		cin >> l >> r;
		l--; r--;
		vls[r].push_back(l);
	}

	for (int i = 1; i <= n; i++) {
		sort(vls[i].begin(), vls[i].end());

		for (auto cur : vls[i - 1]) {
			pre(0, 0, n + 1, i, i + 1, cur);
			pre(0, 0, n + 1, cur, i, cur);
		}
	}

	ll add = 0;
	rec(0, 0, n + 1);
	for (int i = 1; i <= n; i++) {
		sort(vls[i].begin(), vls[i].end());
		if (vec[i - 1] == 1) add++;
		dp[i] = dp[i - 1];

		if (vec[i - 1] == 0) dp[i] = dp[i - 1] + 1;
		for (auto cur : vls[i - 1]) {
			ll lngth = i - cur, zs = pref[i] - pref[cur];
			dp[i] = max(dp[i], lngth - zs + dp[cur]);

			dp[i] = max(dp[i], get(0, 0, n + 1, cur, i, cur) + add);
			upd(0, 0, n + 1, cur, dp[i] - add, cur);
		}
		
	}

	cout << n - (dp[n]);

	return 0;
}

/*
3
1 0 1
2
1 2
2 3

*/

Compiler output:
a.cc: In function 'int main()':
a.cc:198:36: error: no matching function for call to 'max(int&, ll)'
  198 |                         dp[i] = max(dp[i], lngth - zs + dp[cur]);
      |                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:198:36: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
  198 |                         dp[i] = max(dp[i], lngth - zs + dp[cur]);
      |                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:198:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  198 |                         dp[i] = max(dp[i], lngth - zs + dp[cur]);
      |                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:200:36: error: no matching function for call to 'max(int&, ll)'
  200 |                         dp[i] = max(dp[i], get(0, 0, n + 1, cur, i, cur) + add);
      |                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:200:36: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
  200 |                         dp[i] = max(dp[i], get(0, 0, n + 1, cur, i, cur) + add);
      |                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:200:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  200 |                         dp[i] = max(dp[i], get(0, 0, n + 1, cur, i, cur) + add);
      |                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~