Professor Higashikata (Codeforces 1847D)
Tags: Greedy, dsu

Josuke is tired of his peaceful life in Morioh. Following in his nephew Jotaro's footsteps, he decides to study hard and become a professor of computer science. While looking up competitive programming problems online, he comes across the following one: Let $$$s$$$ be a binary string of length $$$n$$$. An operation on $$$s$$$ is defined as choosing two distinct integers $$$i$$$ and $$$j$$$ ($$$1 \leq i < j \leq n$$$), and swapping the characters $$$s_i, s_j$$$.Consider the $$$m$$$ strings $$$t_1, t_2, \ldots, t_m$$$, where $$$t_i$$$ is the substring $$$^\dagger$$$ of $$$s$$$ from $$$l_i$$$ to $$$r_i$$$. Define $$$t(s) = t_1+t_2+\ldots+t_m$$$ as the concatenation of the strings $$$t_i$$$ in that order.There are $$$q$$$ updates to the string. In the $$$i$$$-th update $$$s_{x_i}$$$ gets flipped. That is if $$$s_{x_i}=1$$$, then $$$s_{x_i}$$$ becomes $$$0$$$ and vice versa. After each update, find the minimum number of operations one must perform on $$$s$$$ to make $$$t(s)$$$ lexicographically as large$$$^\ddagger$$$ as possible. Note that no operation is actually performed. We are only interested in the number of operations.Help Josuke in his dream by solving the problem for him. —————————————————————— $$$\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.$$$\ddagger$$$ A string $$$a$$$ is lexicographically larger than a string $$$b$$$ of the same length if and only if the following holds:   in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a $$$1$$$, and the string $$$b$$$ has a $$$0$$$. 

Input: The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n,m,q \leq 2 \cdot 10^5$$$). The next line contains a binary string $$$s$$$ of length $$$n$$$, consisting only of digits $$$0$$$ and $$$1$$$.The $$$i$$$-th line of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$).The $$$i$$$-th line of the next $$$q$$$ lines contains a single integer $$$x_i$$$ ($$$1 \leq x_i \leq n$$$).

Output: Print $$$q$$$ integers. The $$$i$$$-th integer is the minimum number of operations that need to be performed on $$$s$$$ to get the lexicographically largest possible string $$$t(s)$$$ in the $$$i$$$-th round.

Note: In the first test case,Originally, $$$t(s) = s(1,2) + s(1,2) = 0101$$$.After the $$$1$$$-st query, $$$s$$$ becomes $$$11$$$ and consequently $$$t$$$ becomes $$$1111$$$. You don't need to perform any operation as $$$t(s)$$$ is already the lexicographically largest string possible.After the $$$2$$$-nd query, $$$s$$$ becomes $$$01$$$ and consequently $$$t$$$ becomes $$$0101$$$. You need to perform $$$1$$$ operation by swapping $$$s_1$$$ and $$$s_2$$$. Consequently, $$$t(s)$$$ becomes $$$1010$$$ which is the lexicographically largest string you can achieve.

Sample Inputs:
2 2 4
01
1 2
1 2
1
1
2
2

8 6 10
10011010
5 6
2 3
6 8
5 7
5 8
6 8
3
5
6
2
5
2
5
8
4
1

Sample Outputs:
0
1
0
1

2
3
2
2
1
2
2
2
2
2

Solution (Python):
t = []
sz = 0
default_value = 400000

def cmb(x, y):
    """"""
    return min(x, y)

def build(a):
    n = len(a)
    global sz
    sz = 1
    while sz < n:
        sz *= 2
    t.clear()
    t.extend([default_value] * (sz * 2))
    for i in range(n):
        t[sz + i] = a[i]
    for i in range(sz - 1, 0, -1):
        t[i] = cmb(t[i * 2], t[i * 2 + 1])
    return None

def update(i, x):
    i += sz
    t[i] = x
    i //= 2
    while i > 0:
        t[i] = cmb(t[i * 2], t[i * 2 + 1])
        i //= 2
    return None

def query(l, r):
    l += sz
    r += sz
    ans_left = ans_right = default_value
    while l <= r:
        if l % 2 == 1:
            ans_left = cmb(ans_left, t[l])
            l += 1
        if r % 2 == 0:
            ans_right = cmb(t[r], ans_right)
            r -= 1
        l //= 2
        r //= 2
    return cmb(ans_left, ans_right)
t2 = []
sz2 = 0
default_value2 = 0

def cmb2(x, y):
    """"""
    return x + y

def build2(a):
    n = len(a)
    global sz2
    sz2 = 1
    while sz2 < n:
        sz2 *= 2
    t2.clear()
    t2.extend([default_value2] * (sz2 * 2))
    for i in range(n):
        t2[sz2 + i] = a[i]
    for i in range(sz2 - 1, 0, -1):
        t2[i] = cmb2(t2[i * 2], t2[i * 2 + 1])
    return None

def update2(i, x):
    i += sz2
    t2[i] = x
    i //= 2
    while i > 0:
        t2[i] = cmb2(t2[i * 2], t2[i * 2 + 1])
        i //= 2
    return None

def query2(l, r):
    l += sz2
    r += sz2
    ans_left = ans_right = default_value2
    while l <= r:
        if l % 2 == 1:
            ans_left = cmb2(ans_left, t2[l])
            l += 1
        if r % 2 == 0:
            ans_right = cmb2(t2[r], ans_right)
            r -= 1
        l //= 2
        r //= 2
    return cmb2(ans_left, ans_right)

def main():
    (n, m, q) = readIntArr()
    s = input()
    eo = [n + 1] * n
    v = 0
    build(list(range(n)))
    for _ in range(m):
        (l, r) = readIntArr()
        l -= 1
        r -= 1
        while True:
            i = query(l, r)
            if i == 400000:
                break
            eo[i] = v
            v += 1
            update(i, 400000)
    csp = 0
    for v in eo:
        if v != n + 1:
            csp += 1
    arr = [s[i] - ord('0') for i in range(n)]
    cs1 = sum(arr)
    seg_arr = [0] * csp
    for i in range(n):
        if arr[i] == 1 and eo[i] != n + 1:
            seg_arr[eo[i]] = 1
    build2(seg_arr)
    ans = []
    for _ in range(q):
        i = int(input()) - 1
        cs1 += (arr[i] ^ 1) - arr[i]
        arr[i] ^= 1
        if eo[i] != n + 1:
            update2(eo[i], arr[i])
        positions_to_have_1s = min(cs1, csp)
        v = positions_to_have_1s - query2(0, positions_to_have_1s - 1)
        ans.append(v)
    multiLineArrayPrint(ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    ma[get_root(s)] = max(ma[rs], ma[rt])
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
(n, m, q) = map(int, input().split())
s = list(input().rstrip())
s = [0] + [i & 1 for i in s]
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
ma = [i for i in range(n + 1)]
visit = [0] * (n + 2)
y = [0] * (n + 1)
z = []
for _ in range(m):
    (l, r) = map(int, input().split())
    if visit[l]:
        l = ma[get_root(l)] + 1
    while l <= r:
        z.append(l)
        y[l] = len(z)
        visit[l] = 1
        for u in [l - 1, l + 1]:
            if visit[u]:
                unite(u, l)
        l = ma[get_root(l)] + 1
tree = [0] * (n + 5)
l = len(z)
for i in range(l):
    if s[z[i]]:
        add(i + 1, 1)
(c, c0) = (sum(s), get_sum0(n + 3))
ans = []
for _ in range(q):
    x = int(input())
    d = 1 if not s[x] else -1
    s[x] ^= 1
    c += d
    if y[x]:
        add(y[x], d)
        c0 += d
    ans0 = min(l, c) - get_sum0(c)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class fenwick(object):

    def __init__(self, n):
        self.n = n
        self.cul = [0] * n
        self.maxd = len(bin(n)) - 3

    def update(self, index, diff):
        i = index
        while i < self.n:
            self.cul[i] += diff
            i += i + 1 & -i - 1

    def getaccu(self, index):
        output = 0
        i = index
        while i >= 0:
            output += self.cul[i]
            i -= i + 1 & -i - 1
        return output

    def search(self, target):
        accunum = 0
        accuindex = 0
        for i in range(self.maxd, -1, -1):
            d = 1 << i
            if accuindex + d > self.n:
                continue
            if accunum + self.cul[accuindex + d - 1] <= target:
                accunum += self.cul[accuindex + d - 1]
                accuindex += d
        return accuindex

def main(t):
    (n, m, q) = map(int, input().split())
    s = list(input().decode('utf-8')[:n])
    ops = []
    fen = fenwick(n)
    for i in range(n):
        fen.update(i, 1)
    seq = []
    for _ in range(m):
        (l, r) = map(int, input().split())
        ops.append((l, r))
    ops.append((1, n))
    cut = 0
    for (i, (l, r)) in enumerate(ops):
        if i == m:
            cut = len(seq)
        l -= 1
        r -= 1
        loc = fen.getaccu(l - 1)
        num = fen.getaccu(r) - loc
        for _ in range(num):
            index = fen.search(loc)
            seq.append(index)
            fen.update(index, -1)
    transfer = [0] * n
    for i in range(n):
        transfer[seq[i]] = i
    tot = 0
    fen2 = fenwick(n)
    for i in range(n):
        if s[i] == '1':
            fen2.update(transfer[i], 1)
            tot += 1
    for _ in range(q):
        index = int(input())
        index -= 1
        if s[index] == '1':
            s[index] = '0'
            tot -= 1
            fen2.update(transfer[index], -1)
        else:
            s[index] = '1'
            tot += 1
            fen2.update(transfer[index], 1)
        take = min(cut, tot)
        accu = fen2.getaccu(take - 1)
        ans = take - accu
        sys.stdout.write(str(ans) + '\n')
T = 1
t = 1
while t <= T:
    main(t)
    t += 1