第五回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 180）A,B,C,D問題メモ

from itertools import groupby

n = int(input())
s = input()
t = []
for i, c in enumerate(s):
    if (i % 2 == 0) == (c == 'A'):
        t.append(0)
    else:
        t.append(1)
ans = 1
MOD = 1_000_000_007
for a, itr in groupby(t):
    k = (len(list(itr)) + 1) // 2
    ans = ans * k % MOD
print(ans)

def find(n, aaa, pos, ans):
    for d in range(1, n):
        for a in range(n - d):
            i = pos[a]
            j = pos[a + d]
            if i - j >= k:
                ans.append(f'{j + 1} {i + 1}')
                pos[a], pos[a + d] = pos[a + d], pos[a]
                aaa[i], aaa[j] = aaa[j], aaa[i]
                return True
    return False


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa = [a - 1 for a in aaa]
pos = [0] * n
for i, a in enumerate(aaa):
    pos[a] = i
ans = []
while True:
    if find(n, aaa, pos, ans):
        continue
    break

print(len(ans))
print('\n'.join(ans))

from collections import defaultdict

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp0 = [1] * 21
dp1 = {}
dp2 = {}
ans = 1
for a in aaa:
    ndp1 = defaultdict(int, dp1)
    ndp2 = defaultdict(int, dp2)
    if a != 0:
        ndp1[a] += dp0[a]
        dp0[a] = 0
    for acc, pat in dp1.items():
        if acc + a == 0:
            ans += pat
            ans %= MOD
            for i in range(21):
                dp0[i] += pat
                dp0[i] %= MOD
        else:
            ndp2[acc + a] += pat
            ndp2[acc + a] %= MOD
    for acc, pat in dp2.items():
        if acc + a == 0:
            ans += pat
            ans %= MOD
            for i in range(21):
                dp0[i] += pat
                dp0[i] %= MOD
        else:
            ndp2[acc + a] += pat
            ndp2[acc + a] %= MOD
    dp1 = ndp1
    dp2 = ndp2

ans += sum(dp2.values()) % MOD
ans %= MOD
print(ans)

import bisect
from collections import defaultdict
from typing import TypeVar, Generic, Callable, List

T = TypeVar('T')


class SparseTable(Generic[T]):
    def __init__(self, aaa: List[T], identity: T, func: Callable[[T, T], T]):
        self.n = n = len(aaa)
        self.log_n = log_n = (n - 1).bit_length()

        table = [aaa.copy()]
        table.extend([identity] * n for _ in range(log_n - 1))

        for i in range(1, log_n):
            width = 1 << (i - 1)
            for j in range(n - width * 2 + 1):
                table[i][j] = func(table[i - 1][j], table[i - 1][j + width])
        self.table = table
        self.func = func

    def query(self, l: int, r: int) -> T:
        d = r - l
        if d == 1:
            return self.table[0][l]
        k = (d - 1).bit_length() - 1
        k2 = 1 << k
        return self.func(self.table[k][l], self.table[k][r - k2])


class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


def solve(aaa, max_in_query, st_min, queries, ans, rev):
    INF = 1 << 60
    INF2 = 1 << 50
    segments = [(aaa[0], INF2)]
    segments_idx = [0]
    sgt = SegmentTreeInjectable(n, lambda: INF, min)
    sgt.update(0, aaa[0] + INF2)
    for r in range(1, n):
        a = aaa[r]
        min_val = INF2
        while segments and segments[-1][0] <= a:
            mx, mn = segments.pop()
            segments_idx.pop()
            min_val = min(min_val, mx, mn)

        while segments and segments[-1][1] >= min_val:
            segments.pop()
            segments_idx.pop()

        sgt.update(len(segments), a + min_val)
        segments.append((a, min_val))
        segments_idx.append(r)

        if r in queries:
            for qi, l in queries[r]:
                sl = bisect.bisect_left(segments_idx, l)
                sr = len(segments)
                k = segments_idx[sl]
                tmp = INF
                if l < k:
                    tmp = st_min.query(l + 1, k) + segments[sl][0]
                if sl + 1 < sr:
                    tmp = min(tmp, sgt.get_range(sl + 1, sr))
                tmp += max_in_query[qi]
                # print(f'{i=} {l=} {r=} {tmp=}')
                ans[qi] = min(ans[qi], tmp)


n, q = map(int, input().split())
aaa = list(map(int, input().split()))
st_max = SparseTable(aaa, 0, max)

queries_fwd = defaultdict(list)
queries_bwd = defaultdict(list)
ans = [0] * q
max_in_query = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    queries_fwd[r - 1].append((i, l - 1))
    queries_bwd[n - l].append((i, n - r))
    ans[i] = min(
        aaa[l - 1] + aaa[l] + st_max.query(l + 1, r),
        aaa[l - 1] + aaa[r - 1] + st_max.query(l, r - 1),
        aaa[r - 2] + aaa[r - 1] + st_max.query(l - 1, r - 2),
    )
    max_in_query[i] = st_max.query(l - 1, r)

st_min = SparseTable(aaa, 1 << 60, min)
solve(aaa, max_in_query, st_min, queries_fwd, ans, False)
aaa.reverse()
st_min = SparseTable(aaa, 1 << 60, min)
solve(aaa, max_in_query, st_min, queries_bwd, ans, True)

print('\n'.join(map(str, ans)))