AtCoder Regular Contest 196 (Div. 1) A,B,C,D問題メモ

from heapq import heappush, heappushpop


def sub(n, aaa):
    sq = []
    lq = []
    ss = 0
    ls = 0
    best = []
    for i in range(n):
        a = aaa[i]
        if i % 2 == 0:
            best.append(ls - ss)
            b = heappushpop(lq, a)
            ls += a - b
            heappush(sq, -b)
            ss += b
        else:
            best.append(-1)
            b = -heappushpop(sq, -a)
            ss += a - b
            heappush(lq, b)
            ls += b
    return best


def solve(n, aaa):
    bbb = sorted(aaa)
    if n % 2 == 0:
        ans = sum(bbb[n // 2:]) - sum(bbb[:n // 2])
        return ans

    fwd_best = sub(n, aaa)
    rev = list(reversed(aaa))
    bwd_best = sub(n, rev)
    bwd_best.reverse()

    best = 0
    for i in range(0, n, 2):
        best = max(best, fwd_best[i] + bwd_best[i])

    return best


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(ans)

from collections.abc import Callable
from operator import xor
from typing import Generic, TypeVar

T = TypeVar('T', int, float, tuple)  # データ構造に載せそうな型のうち、Immutable なもの（漏れてたら追加可）


class UnionFindWithPotential(Generic[T]):
    """ポテンシャル付きUnion-Find

    以下の2つのクエリを処理する。
      * unite(x,y,d): 2要素間の差分に対する制約 (x - y = d) を決める。
      * diff(x,y):    2要素間の差を返す。未定義（x と y が連結でない）なら None を返す。

    載せられるのはアーベル群に限る(?)。
    つまり2項間の「加算演算」「減算演算」が定義でき、また「加算演算が可換」である場合に限る。

    Attributes:
        table (list[int]): 各頂点の、親の頂点番号を表すList。または親である場合は(-要素数)
        values (list[T]): 各頂点の、親との差分を表すList
    """

    def __init__(self,
                 n: int,
                 init: T,
                 func: Callable[[T, T], T],
                 rev_func: Callable[[T, T], T]):
        """コンストラクタ

        Args:
            n: 要素数
            init: 単位元
            func: 2項間加算演算 (add)
            rev_func: 2項間減算演算 (sub)
        """
        self.table = [-1] * n
        self.values = [init] * n
        self.init = init
        self.func = func
        self.rev_func = rev_func

    def root(self, x: int) -> int:
        stack = []
        tbl = self.table
        vals = self.values

        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        if stack:
            val = self.init
            while stack:
                y = stack.pop()
                val = self.func(val, vals[y])
                vals[y] = val
                tbl[y] = x
        return x

    def is_same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def diff(self, x: int, y: int) -> T | None:
        """ x と y の差（y - x）を取得。同じグループに属さない場合は None。
        """
        if not self.is_same(x, y):
            return None
        vx = self.values[x]
        vy = self.values[y]
        return self.rev_func(vy, vx)

    def unite(self, x: int, y: int, d: T) -> bool:
        """ x と y のグループを、y - x = d となるように統合（順序に注意）
        既に x と y が同グループで、矛盾する場合は AssertionError。矛盾しない場合はFalse。
        同グループで無く、新たな統合が発生した場合はTrue。
        """
        rx = self.root(x)
        ry = self.root(y)
        vx = self.values[x]
        vy = self.values[y]
        if rx == ry:
            assert self.rev_func(vy, vx) == d
            return False

        rd = self.rev_func(self.func(vx, d), vy)
        self.table[rx] += self.table[ry]
        self.table[ry] = rx
        self.values[ry] = rd
        return True

    def get_size(self, x: int) -> int:
        return -self.table[self.root(x)]


def solve(h, w, field):
    rows = [[] for _ in range(h)]
    cols = [[] for _ in range(w)]
    bcnt = 0
    mapping = {}
    for i in range(h):
        for j in range(w):
            if field[i][j] == 'A':
                continue
            rows[i].append(j)
            cols[j].append(i)
            mapping[i, j] = bcnt
            bcnt += 1
    all_a_row_cnt = 0
    all_a_col_cnt = 0
    for i in range(h):
        if (w - len(rows[i])) % 2 == 1:
            return 0
        if len(rows[i]) == 0:
            all_a_row_cnt += 1
    for j in range(w):
        if (h - len(cols[j])) % 2 == 1:
            return 0
        if len(cols[j]) == 0:
            all_a_col_cnt += 1

    uft = UnionFindWithPotential(bcnt, 0, xor, xor)
    try:
        for i in range(h):
            row = rows[i]
            for ri in range(len(row) - 1):
                j1 = row[ri]
                j2 = row[ri + 1]
                x = mapping[i, j1]
                y = mapping[i, j2]
                uft.unite(x, y, (j2 - j1 + 1) % 2)
        for j in range(w):
            col = cols[j]
            for ci in range(len(col) - 1):
                i1 = col[ci]
                i2 = col[ci + 1]
                x = mapping[i1, j]
                y = mapping[i2, j]
                uft.unite(x, y, (i2 - i1 + 1) % 2)
    except AssertionError:
        return 0

    free = all_a_row_cnt + all_a_col_cnt
    for i in range(bcnt):
        if uft.table[i] < 0:
            free += 1
    return pow(2, free, 998244353)


t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    field = [input() for _ in range(h)]
    ans = solve(h, w, field)
    print(ans)

import os
import sys

import numpy as np


def solve(n, s):
    MOD = 998244353
    SUM_E = np.array(
        [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456,
         131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443,
         56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)
    SUM_IE = np.array(
        [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882,
         927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183,
         824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)

    def bit_length(n):
        x = 0
        while 1 << x < n:
            x += 1
        return x

    def bit_scan_forward(n):
        x = 0
        while n & 1 == 0:
            n >>= 1
            x += 1
        return x

    def pow_mod(x, n, m):
        r = 1
        y = x % m
        while n > 0:
            if n & 1 == 1:
                r = (r * y) % m
            y = y * y % m
            n >>= 1
        return r

    def butterfly(aaa):
        n = aaa.size
        h = bit_length(n)

        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p] * now % MOD
                    aaa[i + offset] = (l + r) % MOD
                    aaa[i + offset + p] = (l - r) % MOD
                now = now * SUM_E[bit_scan_forward(~s)] % MOD

    def butterfly_inv(aaa):
        n = aaa.size
        h = bit_length(n)

        for ph in range(h, 0, -1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p]
                    aaa[i + offset] = (l + r) % MOD
                    aaa[i + offset + p] = ((l - r) * inow) % MOD
                inow = inow * SUM_IE[bit_scan_forward(~s)] % MOD

    def ntt(aaa, bbb):
        n = aaa.size
        m = bbb.size
        k = n + m - 1
        z = 1 << bit_length(k)
        raaa = np.zeros(z, np.int64)
        rbbb = np.zeros(z, np.int64)
        raaa[:n] = aaa
        rbbb[:m] = bbb
        butterfly(raaa)
        butterfly(rbbb)
        for i in range(z):
            raaa[i] = raaa[i] * rbbb[i] % MOD
        butterfly_inv(raaa)
        iz = pow_mod(z, MOD - 2, MOD)
        for i in range(k):
            raaa[i] = raaa[i] * iz % MOD
        return raaa[:k]

    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1 == 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions

    if s[0] != 0 or s[-1] != 1:
        return 0

    facts, finvs = prepare_factorials(n * 2, MOD)

    b_cnt = np.zeros(n * 2 + 1, np.int64)
    for i in range(n * 2):
        if s[i] == 0:
            b_cnt[i + 1] = b_cnt[i] + 1
        else:
            b_cnt[i + 1] = b_cnt[i]
    w_cnt = np.arange(n * 2 + 1, dtype=np.int64)
    w_cnt -= b_cnt

    dp = np.zeros(n * 2 + 1, np.int64)

    def bruteforce(l, r):
        for i in range(l, r - 1):
            for j in range(i + 1, r):
                b = b_cnt[j] - b_cnt[i]
                w = j - b_cnt[i] - b_cnt[j]
                if b > w:
                    continue
                c = facts[w] * finvs[w - b] % MOD
                dp[j] -= c * dp[i]
                dp[j] %= MOD

    dp[0] = -1
    tasks = [(0, n * 2 + 1, -1)]
    while len(tasks) > 0:
        l, r, m = tasks.pop()
        if m == -1:
            if r - l < 500:
                bruteforce(l, r)
                continue
            m = (l + r) // 2
            tasks.append((m, r, -1))
            tasks.append((l, r, m))
            tasks.append((l, m, -1))
        else:
            bc = b_cnt[m] - b_cnt[l]
            fff = np.zeros(bc + 1, np.int64)
            for i in range(l, m):
                key = b_cnt[i] - b_cnt[l]
                fff[key] += dp[i]
            ggg = facts[:(r - l) * 2]
            hhh = ntt(fff, ggg)
            for i in range(m, r):
                wb = w_cnt[i] - b_cnt[i]
                if wb < 0:
                    continue
                dp[i] -= hhh[w_cnt[i] - b_cnt[l]] * finvs[wb] % MOD
                dp[i] %= MOD

    return dp[n * 2]


SIGNATURE = '(i8,i1[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

n = int(input())
s = np.fromiter(map('BW'.index, input()), dtype=np.int8)
ans = solve(n, s)
print(ans)

町を頂点とし、上記の条件に違反しない人の集合のみで $S_i→T_i$ に有向辺を張った $N$ 頂点のグラフを考えると、 「内側で起終点が被らない」条件より、連結成分は折り返しのない1本の線グラフになる。

(例)
①-------->⑤-->⑦----->⑫<-----⑱

結ばれた頂点のポテンシャルは全て等しくなる。

2つの連結成分a,bの範囲が被っているとき、 「同じ向きの区間は公差しない」条件より、以下の事実が言える。

• a側の頂点は（範囲外でなければ）常にb側の←向きの辺上にあり、b側の頂点は（範囲外でなければ）常にa側の→向きの辺上にある
  • または、←→を逆にした内容

連結成分 a  ①-------->⑤-->⑦----->⑫<-----⑱
連結成分 b    ②--->④<---------⑩<------------⑳

上例で説明する。b側の区間（隣接頂点）を左から右に注目していく。
区間がa側の区間に内包されているとき（②④など）は特に辺の向きに制約はない。
区間がa側の頂点をまたぐとき、例えば④⑩はa側の⑤や⑦をまたいでいるが、この時は必ず以下が成立する。

• 「④が属するa側の区間（①→⑤）に張られた辺の向き」と「⑩が属するa側の区間（⑦→⑫）に張られた辺の向き」は一致
• ④⑩間の辺の向きは、上記のa側の区間とは逆（←）

そうでなければ、a,bで同じ方向の区間が交差してしまうことになる。
これを繰り返すと、b側の頂点はa側の→向きの辺上にしか存在せず、a側の頂点はb側の←向きの辺上にしか存在しないことが示せる。

ポテンシャルの大小関係は、一方の頂点が、他方の→←どっち向きの辺の上に存在するかで決まるため、 例の場合は「aの各頂点のポテンシャル < bの各頂点のポテンシャル」が常に成立する。
つまり、たとえば「ポテンシャルの大小関係が ④ > ⑤ > ⑩ となってしまって、ともにbに属する④と⑩のポテンシャルが一致しなくて矛盾」というようなことが発生しないと示せる。

連結成分が3つ以上の場合でも、ポテンシャルの大小関係は推移律を満たし、循環することはない。

ポテンシャルの大小関係が決まれば、ポテンシャルの値、ひいては $w_i$ はどうとでも決められる。

import random
from operator import xor


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func, rev_func=None):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.rev_func = rev_func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def sum_range(self, l, r):
        assert self.rev_func is not None
        assert 0 <= l < r
        result = self.sum(r - 1)
        if l > 0:
            result = self.rev_func(result, self.sum(l - 1))
        return result

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


def solve(n, m, q, segments, queries):
    fwd_fwt = FenwickTreeInjectable(n + 1, int, xor, xor)
    bwd_fwt = FenwickTreeInjectable(n + 1, int, xor, xor)
    fwd_s = [0] * (n + 1)
    fwd_t = [0] * (n + 1)
    bwd_s = [0] * (n + 1)
    bwd_t = [0] * (n + 1)
    next_conflict = [m] * m
    zobrist_value = [random.randrange(0, 1 << 60) for _ in range(m)]

    def can_add_segment(s, t):
        if s < t:
            if fwd_s[s] > 0 or fwd_t[t] > 0 or bwd_t[s] > 0 or bwd_s[t] > 0:
                return False
            elif s + 1 < t and fwd_fwt.sum_range(s + 1, t) != 0:
                return False
        else:
            if bwd_s[s] > 0 or bwd_t[t] > 0 or fwd_t[s] > 0 or fwd_s[t] > 0:
                return False
            elif t + 1 < s and bwd_fwt.sum_range(t + 1, s) != 0:
                return False
        return True

    l = 0
    r = 0
    sr, tr = 0, 0
    while r < m:
        while r < m:
            s, t = segments[r]
            s -= 1
            t -= 1
            if can_add_segment(s, t):
                if s < t:
                    fwd_s[s] += 1
                    fwd_t[t] += 1
                    fwd_fwt.add(s, zobrist_value[r])
                    fwd_fwt.add(t, zobrist_value[r])
                else:
                    bwd_s[s] += 1
                    bwd_t[t] += 1
                    bwd_fwt.add(s, zobrist_value[r])
                    bwd_fwt.add(t, zobrist_value[r])
                r += 1
            else:
                sr = s
                tr = t
                next_conflict[l] = r
                break
        else:
            # r==m and not ng
            break

        while l < r:
            s, t = segments[l]
            s -= 1
            t -= 1
            if s < t:
                fwd_s[s] -= 1
                fwd_t[t] -= 1
                fwd_fwt.add(s, zobrist_value[l])
                fwd_fwt.add(t, zobrist_value[l])
            else:
                bwd_s[s] -= 1
                bwd_t[t] -= 1
                bwd_fwt.add(s, zobrist_value[l])
                bwd_fwt.add(t, zobrist_value[l])
            l += 1
            if can_add_segment(sr, tr):
                if sr < tr:
                    fwd_s[sr] += 1
                    fwd_t[tr] += 1
                    fwd_fwt.add(sr, zobrist_value[r])
                    fwd_fwt.add(tr, zobrist_value[r])
                else:
                    bwd_s[sr] += 1
                    bwd_t[tr] += 1
                    bwd_fwt.add(sr, zobrist_value[r])
                    bwd_fwt.add(tr, zobrist_value[r])
                r += 1
                break
            else:
                next_conflict[l] = r

    ans = []
    for l, r in queries:
        ans.append(next_conflict[l - 1] >= r)

    return ans


def naive_next_conflict(n, m, q, segments, queries):
    def check(l):
        for i in range(l + 1, m):
            si, ti = segments[i]
            for j in range(l, i):
                sj, tj = segments[j]
                if si < ti and sj < tj:
                    if not (si < sj < tj < ti or sj < si < ti < tj or ti <= sj or tj <= si):
                        break
                elif ti < si and tj < sj:
                    if not (ti < tj < sj < si or tj < ti < si < sj or si <= tj or sj <= ti):
                        break
                else:
                    if si == tj or ti == sj:
                        break
            else:
                continue
            return i
        return m

    next_conflict = [m] * m
    for l in range(m):
        next_conflict[l] = check(l)

    return next_conflict


def check():
    n = 10
    m = 6
    segments = [(i, j) for i in range(1, n + 1) for j in range(1, n + 1) if i != j]
    q = 0
    queries = []
    for _ in range(100):
        segments = random.sample(segments, k=m)
        ans1 = solve(n, m, q, segments, queries)
        ans2 = naive_next_conflict(n, m, q, segments, queries)
        if ans1 == ans2:
            continue
        print('----')
        print(f'{n} {m} {q}')
        print('\n'.join(f'{a[0]} {a[1]}' for a in segments))
        print()
        print(f'{ans1=}')
        print(f'{ans2=}')


# check()

n, m, q = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(m)]
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, m, q, segments, queries)
print('\n'.join('Yes' if a else 'No' for a in ans))