AtCoder Regular Contest 085 - NRE

You are given a sequence a = \{a_1, ..., a_N\} with all zeros, and a sequence b = \{b_1, ..., b_N\} consisting of 0 and 1. The length of both is N.
You can perform Q kinds of operations. The i-th operation is as follows:
 - Replace each of a_{l_i}, a_{l_i + 1}, ..., a_{r_i} with 1.
Minimize the hamming distance between a and b, that is, the number of i such that a_i \neq b_i, by performing some of the Q operations.

-----Constraints-----
 - 1 \leq N \leq 200,000
 - b consists of 0 and 1.
 - 1 \leq Q \leq 200,000
 - 1 \leq l_i \leq r_i \leq N
 - If i \neq j, either l_i \neq l_j or r_i \neq r_j.

-----Input-----
Input is given from Standard Input in the following format:
N
b_1 b_2 ... b_N
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

-----Output-----
Print the minimum possible hamming distance.

-----Sample Input-----
3
1 0 1
1
1 3

-----Sample Output-----
1

If you choose to perform the operation, a will become \{1, 1, 1\}, for a hamming distance of 1.

Source: atcoder | Difficulty: VERY_HARD


Solutions:
n = int(input())
b = list(map(int, input().split()))
ope = [[] for i in range(n)]
Q = int(input())
for i in range(Q):
	(l, r) = map(int, input().split())
	ope[r - 1].append(l - 1)
res = b.count(0)
Data = [(-1) ** ((b[i] == 1) + 1) for i in range(n)]
for i in range(1, n):
	Data[i] += Data[i - 1]
Data = [0] + Data
for i in range(n):
	ope[i].sort(reverse=True)
N = n + 1
N0 = 2 ** (N - 1).bit_length()
data = [None] * (2 * N0)
INF = (-2 ** 31, -2 ** 31)

def update(l, r, v):
	L = l + N0
	R = r + N0
	while L < R:
		if R & 1:
			R -= 1
			if data[R - 1]:
				data[R - 1] = max(v, data[R - 1])
			else:
				data[R - 1] = v
		if L & 1:
			if data[L - 1]:
				data[L - 1] = max(v, data[L - 1])
			else:
				data[L - 1] = v
			L += 1
		L >>= 1
		R >>= 1

def _query(k):
	k += N0 - 1
	s = INF
	while k >= 0:
		if data[k]:
			s = max(s, data[k])
		k = (k - 1) // 2
	return s

def query(k):
	return _query(k)[1]
for i in range(n + 1):
	update(i, i + 1, (-Data[i], -Data[i]))
if ope[0]:
	update(1, 2, (0, 0))
for i in range(1, n):
	val = query(i)
	update(i + 1, i + 2, (val + Data[i] - Data[i + 1], val + Data[i] - Data[i + 1]))
	for l in ope[i]:
		val = query(l)
		update(l + 1, i + 2, (val, val))
print(n - (res + query(n) + Data[n]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
B = list(map(int, readline().split()))
Q = int(readline())
m = map(int, read().split())
LR = sorted(zip(m, m))

class MaxSegTree:

	def __init__(self, raw_data):
		N = len(raw_data)
		self.size = 1 << N.bit_length()
		self.data = [0] * (2 * self.size)
		self.build(raw_data)

	def build(self, raw_data):
		for (i, x) in enumerate(raw_data):
			self.data[self.size + i] = x
		for i in range(self.size - 1, 0, -1):
			x = self.data[i + i]
			y = self.data[i + i + 1]
			self.data[i] = x if x > y else y

	def update(self, i, x):
		i += self.size
		self.data[i] = x
		i >>= 1
		while i:
			x = self.data[i + i]
			y = self.data[i + i + 1]
			self.data[i] = x if x > y else y
			i >>= 1

	def get_data(self, i):
		return self.data[i + self.size]

	def get_max(self, L, R):
		L += self.size
		R += self.size + 1
		x = 0
		while L < R:
			if L & 1:
				y = self.data[L]
				if x < y:
					x = y
				L += 1
			if R & 1:
				R -= 1
				y = self.data[R]
				if x < y:
					x = y
			L >>= 1
			R >>= 1
		return x
add1 = [0] * (N + 1)
add1[0] = sum(B)
for (i, x) in enumerate(B, 1):
	if x:
		add1[i] = add1[i - 1] - 1
	else:
		add1[i] = add1[i - 1]
add0 = [N - i - x for (i, x) in enumerate(add1)]
(add0, add1)
dp0 = MaxSegTree([0] * (N + 1))
dp1 = MaxSegTree([0] * (N + 1))
dp0.update(0, add0[0])
dp1.update(0, add1[0])
for (L, R) in LR:
	a = dp1.get_data(R)
	b = dp0.get_max(0, L - 1) + add1[L - 1] - add0[L - 1]
	c = dp1.get_max(L, R - 1)
	if b < c:
		b = c
	if a < b:
		dp1.update(R, b)
		dp0.update(R, b - add1[R] + add0[R])
answer = N - dp0.get_max(0, N)
print(answer)