Codeforces Round 223 (Div. 1) - Sereja and Brackets 링크
(2023.07.12 기준 Difficulty *2000)

문제

n개의 소괄호가 주어진다. m개의 쿼리 l r이 주어질 때, [l, r] 구간에서 가장 긴 올바른 괄호 순서의 길이를 출력

알고리즘

세그먼트 트리

풀이

Non-Commutative combine function이다. 쉽게 말하면 두 노드를 combine할 때에 교환법칙이 통하지 않는 것이다.

먼저 노드의 구조체를 만들자. 올바르게 열렸다가 닫힌 괄호의 개수, 올바른 괄호에 쓰이지 않은 괄호 둘. 총 3개의 변수를 만들어야 한다.

struct Node
	Node.l = 0 -> 쓰이지 않은 (
    Node.r = 0 -> 쓰이지 않은 )
    Node.m = 0 -> 올바르게 열렸다가 닫힌 괄호의 개수 (쓰인 괄호들)

그리고 두 노드를 합칠 때는 왼쪽에는 쓰이지 않은 (, 오른쪽에는 쓰이지 않은 )가 필요할 것이다. 둘 중 작은 값이 올바른 괄호가 될 수 있는 수가 된다.

function combine(Node left, Node right)
	result = new Node
	usable = min(left.l, right.r) -> 올바른 괄호가 될 수 있는 수
    result.l = left.l + right.l - usable
    result.r = left.r + right.r - usable
    result.m = left.m + right.m + usable * 2 -> (, ) 각 두 개씩이므로 곱하기 2
    return result

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000, MAXH = 1 << (int)ceil(log2(MAXN) + 1);

int n;
string s;

struct Node{
    int l = 0; // unused (
    int r = 0; // unused )
    int m = 0; // length of the maximum correct (used)
};

struct ST{ // 0-based index
    Node tree[MAXH];

    void init();

    Node _merge(Node l, Node r){
        Node result;
        int usable = min(l.l, r.r);
        result.l = l.l + r.l - usable;
        result.r = l.r + r.r - usable;
        result.m = l.m + r.m + usable * 2;
        return result;
    }

    void _init(int nd, int st, int en){
        if (st == en){
            if (s[st] == '(') tree[nd].l++;
            else tree[nd].r++;
            return;
        }
        int mid = (st + en) >> 1;
        _init(nd << 1, st, mid);
        _init(nd << 1 | 1, mid + 1, en);
        tree[nd] = _merge(tree[nd << 1], tree[nd << 1 | 1]);
    }

    Node _query(int nd, int st, int en, int l, int r){
        if (r < st || en < l) return Node();
        if (l <= st && en <= r) return tree[nd];
        int mid = (st + en) >> 1;
        return _merge(_query(nd << 1, st, mid, l, r), _query(nd << 1 | 1, mid + 1, en, l, r));
    }

    int query(int l, int r){
        return _query(1, 0, n - 1, l, r).m;
    }
}st;

void ST::init(){
    _init(1, 0, n - 1);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    n = s.size();

    st.init();

    int m, l, r; cin >> m;
    while (m--){
        cin >> l >> r;
        cout << st.query(l - 1, r - 1) << '\n';
    }
}

• Python (TLE)

import sys; input = sys.stdin.readline
from math import ceil, log2

class Node:
    def __init__(self):
        self.l = 0 # unused (
        self.r = 0 # unused )
        self.m = 0 # length of the maximum correct (used)

class ST:
    def __init__(self):
        self.tree = [Node() for _ in range(h)]
        self._init(1, 0, n - 1)

    def _merge(self, l, r):
        result = Node()
        usable = min(l.l, r.r)
        result.l = l.l + r.l - usable
        result.r = l.r + r.r - usable
        result.m = l.m + r.m + usable * 2
        return result

    def _init(self, nd, st, en):
        if st == en:
            if s[st] == '(':
                self.tree[nd].l += 1
            else:
                self.tree[nd].r += 1
            return
        mid = (st + en) >> 1
        self._init(nd << 1, st, mid)
        self._init(nd << 1 | 1, mid + 1, en)
        self.tree[nd] = self._merge(self.tree[nd << 1], self.tree[nd << 1 | 1])

    def _query(self, nd, st, en, l, r):
        if r < st or en < l:
            return Node()
        if l <= st and en <= r:
            return self.tree[nd]
        mid = (st + en) >> 1 
        return self._merge(self._query(nd << 1, st, mid, l, r), self._query(nd << 1 | 1, mid + 1, en, l, r))

    def query(self, l, r):
        return self._query(1, 0, n - 1, l, r).m

s = input().strip()
n = len(s); h = 1 << ceil(log2(n) + 1)
st = ST()

for _ in range(int(input())):
    l, r = map(int, input().split())
    print(st.query(l - 1, r - 1))

여담

Python은 PyPy3로 비재귀, FASTIO 같은 모든 최적화를 해봐도 TLE이길래 AC 코드를 보니깐 무슨 리스트에 담아서 merge 함수 조차 비재귀로 구현해야 하더라.. 그냥 깔끔하게 포기. (그런걸 왜 해..)