Sum of Matchings (Codeforces 1651E)
Tags: Greedy, graph matchings

Let's denote the size of the maximum matching in a graph $$$G$$$ as $$$\mathit{MM}(G)$$$.You are given a bipartite graph. The vertices of the first part are numbered from $$$1$$$ to $$$n$$$, the vertices of the second part are numbered from $$$n+1$$$ to $$$2n$$$. Each vertex's degree is $$$2$$$.For a tuple of four integers $$$(l, r, L, R)$$$, where $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$, let's define $$$G'(l, r, L, R)$$$ as the graph which consists of all vertices of the given graph that are included in the segment $$$[l, r]$$$ or in the segment $$$[L, R]$$$, and all edges of the given graph such that each of their endpoints belongs to one of these segments. In other words, to obtain $$$G'(l, r, L, R)$$$ from the original graph, you have to remove all vertices $$$i$$$ such that $$$i \notin [l, r]$$$ and $$$i \notin [L, R]$$$, and all edges incident to these vertices.Calculate the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

Input: The first line contains one integer $$$n$$$ ($$$2 \le n \le 1500$$$) — the number of vertices in each part.Then $$$2n$$$ lines follow, each denoting an edge of the graph. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$n + 1 \le y_i \le 2n$$$) — the endpoints of the $$$i$$$-th edge.There are no multiple edges in the given graph, and each vertex has exactly two incident edges.

Output: Print one integer — the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.


Sample Inputs:
5
4 6
4 9
2 6
3 9
1 8
5 10
2 7
3 7
1 10
5 8

Sample Outputs:
314

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
    return wrappedfunc

def main():
    N = int(input())
    adj = [[] for _ in range(2 * N)]
    for _ in range(2 * N):
        (u, v) = map(int, input().split())
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)
    seen = [0] * (2 * N)

    @bootstrap
    def dfs(u, cycle):
        seen[u] = 1
        cycle.append(u)
        for v in adj[u]:
            if seen[v]:
                continue
            yield dfs(v, cycle)
        yield None
    res = 0
    for u in range(N):
        if seen[u]:
            continue
        cycle = []
        dfs(u, cycle)
        S = len(cycle)
        (mnl, mxl, mnr, mxr) = (INF, -INF, INF, -INF)
        for v in cycle:
            if v < N:
                mnl = min(mnl, v)
                mxl = max(mxl, v)
            else:
                mnr = min(mnr, v - N)
                mxr = max(mxr, v - N)
        res += S // 2 * (mnl + 1) * (N - mxl) * (mnr + 1) * (N - mxr)
        debug(cycle)
        debug(mnl, mxl, mnr, mxr, res)
        for i in range(S):
            (mnl, mxl, mnr, mxr) = (INF, -INF, INF, -INF)
            for d in range(S):
                j = cycle[(i + d) % S]
                if j < N:
                    mnl = min(mnl, j)
                    mxl = max(mxl, j)
                else:
                    mnr = min(mnr, j - N)
                    mxr = max(mxr, j - N)
                if d % 2 == 1:
                    k = cycle[(i + S - 1) % S]
                    (mn1, mx1, mn2, mx2) = (mnl, mxl, mnr, mxr)
                    if i % 2 == 0:
                        k -= N
                    else:
                        (mn1, mx1, mn2, mx2) = (mn2, mx2, mn1, mx1)
                    if k < mn2:
                        res += (mn1 + 1) * (N - mx1) * (mn2 - k) * (N - mx2)
                    if k > mx2:
                        res += (mn1 + 1) * (N - mx1) * (mn2 + 1) * (k - mx2)
    return res
if __name__ == '__main__':
    out = main()
    print(out)

Solution (Python):
import sys
from sys import stdin
n = int(stdin.readline())
inf = float('inf')
lis = [[] for i in range(2 * n)]
for i in range(2 * n):
    (x, y) = map(int, stdin.readline().split())
    x -= 1
    y -= 1
    lis[x].append(y)
    lis[y].append(x)
inds = [None] * (2 * n)
ring = []
for i in range(2 * n):
    if inds[i] == None:
        rind = len(ring)
        ring.append([i])
        inds[i] = (rind, 0)
        v = i
        while True:
            if inds[lis[v][0]] == None:
                nex = lis[v][0]
            elif inds[lis[v][1]] == None:
                nex = lis[v][1]
            else:
                break
            inds[nex] = (rind, len(ring[-1]))
            ring[-1].append(nex)
            v = nex
ans = 0
for nr in ring:
    l = inf
    r = -inf
    L = inf
    R = -inf
    for i in nr:
        if i < n:
            l = min(l, i)
            r = max(r, i)
        else:
            L = min(L, i)
            R = max(R, i)
    now = (l + 1) * (n - r) * (L - n + 1) * (2 * n - R) * (len(nr) // 2)
    ans += now
    for fi in range(len(nr)):
        l = inf
        r = -inf
        L = inf
        R = -inf
        for i in range(len(nr) - 1):
            xx = nr[(i + fi) % len(nr)]
            if xx < n:
                l = min(l, xx)
                r = max(r, xx)
            else:
                L = min(L, xx)
                R = max(R, xx)
            (l2, r2, L2, R2) = (l + 1, n - r, L + 1 - n, 2 * n - R)
            notA = notX = nr[fi - 1]
            if l <= notA <= r or L <= notA <= R:
                l2 = 0
            if notA <= l:
                l2 = min(l2, l - notA)
            if r <= notA < n:
                r2 = min(r2, notA - r)
            if n <= notA <= L:
                L2 = min(L2, L - notA)
            if R <= notA < 2 * n:
                R2 = min(R2, notA - R)
            notA = notY = nr[(i + fi + 1) % len(nr)]
            if l <= notA <= r or L <= notA <= R:
                l2 = 0
            if notA <= l:
                l2 = min(l2, l - notA)
            if r <= notA < n:
                r2 = min(r2, notA - r)
            if n <= notA <= L:
                L2 = min(L2, L - notA)
            if R <= notA < 2 * n:
                R2 = min(R2, notA - R)
            if i != 0:
                ans += l2 * r2 * L2 * R2 * ((i + 1) // 2)
print(ans)

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(n,) = I()
botneigh = [[] for i in range(n)]
topneigh = [[] for i in range(n)]
edges = []
for i in range(2 * n):
    (x, y) = I()
    x = x - 1
    y = y - n - 1
    edges.append((x, y))
    botneigh[x].append(y)
    topneigh[y].append(x)
toplen = [0] * n
botlen = [0] * n
for i in range(n):
    if toplen[i] == 0:
        prev = i
        curr = topneigh[i][0]
        cycle = [prev]
        while curr != cycle[0] or len(cycle) % 2 == 1:
            cycle.append(curr)
            ccurr = curr
            if len(cycle) % 2 == 0:
                for j in range(2):
                    if botneigh[curr][j] != prev:
                        curr = botneigh[curr][j]
                        break
            else:
                for j in range(2):
                    if topneigh[curr][j] != prev:
                        curr = topneigh[curr][j]
                        break
            prev = ccurr
        for i in range(len(cycle)):
            if i % 2 == 0:
                toplen[cycle[i]] = len(cycle)
            else:
                botlen[cycle[i]] = len(cycle)
tot = 0
xtot = 0
for (x, y) in edges:
    old = tot
    smlbot = x
    bigbot = x
    smltop = y
    bigtop = y
    curr = x
    prev = y
    for i in range(toplen[y] // 2):
        for j in range(2):
            if botneigh[curr][j] != prev:
                nex = botneigh[curr][j]
        if nex < smltop:
            tot += (smltop - nex) * (n - bigtop) * (smlbot + 1) * (n - bigbot)
            smltop = nex
        elif nex > bigtop:
            tot += (smltop + 1) * (nex - bigtop) * (smlbot + 1) * (n - bigbot)
            bigtop = nex
        prev = curr
        curr = nex
        for j in range(2):
            if topneigh[curr][j] != prev:
                nex = topneigh[curr][j]
        if nex < smlbot:
            smlbot = nex
        elif nex > bigbot:
            bigbot = nex
        prev = curr
        curr = nex
    xtot += (smltop + 1) * (n - bigtop) * (smlbot + 1) * (n - bigbot)
for (x, y) in edges:
    smlbot = x
    bigbot = x
    smltop = y
    bigtop = y
    curr = y
    prev = x
    for i in range(toplen[y] // 2):
        for j in range(2):
            if topneigh[curr][j] != prev:
                nex = topneigh[curr][j]
        if nex < smlbot:
            tot += (smlbot - nex) * (n - bigbot) * (smltop + 1) * (n - bigtop)
            smlbot = nex
        elif nex > bigbot:
            tot += (nex - bigbot) * (smlbot + 1) * (smltop + 1) * (n - bigtop)
            bigbot = nex
        prev = curr
        curr = nex
        for j in range(2):
            if botneigh[curr][j] != prev:
                nex = botneigh[curr][j]
        if nex < smltop:
            smltop = nex
        elif nex > bigtop:
            bigtop = nex
        prev = curr
        curr = nex
print(tot // 2 + xtot // 2)