Codeforces Round #556 (Div. 2) E. Tree Generator™(선분 수 교 인간 시리즈)

제목 링크:https://codeforces.com/contest/1150/problem/E
제목: 현재 괄호 서열 이 있 습 니 다. 괄호 서열 은 먼저 순서대로 옮 겨 다 니 는 나무 구 조 를 표현 합 니 다. 왼쪽 괄호 는 현재 노드 에서 아래로 옮 겨 다 니 는 것 을 나타 내 고 오른쪽 괄호 는 위로 거 슬러 올 라 가 는 것 을 나타 냅 니 다.m m 개의 조작 이 있 고 매번 조작 할 때마다 두 개의 괄호 의 위 치 를 교환 하 며 교환 한 후에 괄호 의 일치 가 똑 같이 합 리 적 임 을 보증 합 니 다.현재 괄호 시퀀스 에 표 시 된 트 리 직경 을 출력 해 야 합 니 다.
문제 풀이 소감:

나 무 를 나무 사슬 로 레이 블 을 나눈다 고 가정 하면 레이 블 된 두 노드 a a, b b b 는 a < b a < b a < b > b 라면 그들의 l c m lcm lcm 는 반드시 a a 와 b b b b 사이 에 있 고 l c m lcm lcm 는 a a 와 b b b b 사이 의 깊이 가 가장 작은 노드 일 것 이다.

이 나무의 지름 은 a a a, b b, d e p t h [a] + d e p t h [b] - 2 * 8727 ° d e p t h [l c m] depth [a] + depth [b] - 2 * depth [lcm] depth [a] + depth [b] - 2 * 8727 ° depth [b] - 2 * depth [lcm] 의 최대 치 입 니 다.그러나 한 나무 에서 공식 적 으로 지름 을 찾 는 시간 이 복잡 하고 괄호 를 교환 할 때마다 나무 가 변형 되 기 때문에 괄호 를 나무 로 서열 화하 여 지름 을 찾 을 수 없다.

사실 자세히 살 펴 보면 우 리 는 각 노드 의 깊이 만 있 으 면 된다. 깊이 는 괄호 서열 에서 직접 얻 을 수 있다. 왼쪽 괄호 가 11 이 고 오른쪽 괄호 가 - 1 - 1 - 1 이 라 고 가정 하면 특정한 괄호 구간 이 대표 하 는 상대 적 인 깊이 를 직접 얻 을 수 있다.이렇게 하면 라인 트 리 를 직접 사용 하여 유지 할 수 있 습 니 다. 유지 해 야 할 값 이 비교적 많 습 니 다. 각 구간 의 것 을 포함 합 니 다.

M a x Max Max_ d e p t h depth depth: 현재 구간 의 가장 깊 은 노드 의 깊이 - d e p t h [a] depth [a] depth [a]

M i n Min Min_ d e p t h depth depth: 현재 구간 의 가장 얕 은 노드 의 깊이 - d e p t h [l c m] depth [lcm] depth [lcm]

M a x Max Max_ l v lv: 현재 구간 왼쪽 아들 최대 깊이 에서 오른쪽 아들 최소 깊이 빼 기×2—— d e p t h [ a ] − 2 ∗ d e p t h [ l c m ] depth[a]-2*depth[lcm] depth[a]−2∗depth[lcm]

M a x Max Max_ r v rv: 현재 구간 오른쪽 아들 의 최대 깊이 에서 왼쪽 아들 의 가장 얕 은 깊이 를 빼 기×2—— d e p t h [ b ] − 2 ∗ d e p t h [ l c m ] depth[b]-2*depth[lcm] depth[b]−2∗depth[lcm]

M a x Max Max_ l r v lrv lrv: 현재 구간 의 지름 (이것 은 위 에 있 는 두 개 를 직접 합치 면 끝 나 는 것 이 아니 라, M a x Max Max l v lv + 오른쪽 아들 의 최대 노드 깊이 인지 M a x Max r v rv + 왼쪽 아들 의 최대 노드 깊이 인지 판단 해 야 한다) - d e p t h [a] - 2 * 8727 ° d e p t h [l c m] + d e p t h [b] depth [a] - 2 * depth [lcm]+depth[b] depth[a]−2∗depth[lcm]+depth[b]

codeforces 원생 의 문제 풀이:https://codeforces.com/blog/entry/66783

#include 
using namespace std;
const int maxn = 2e5+100;

struct Node {
    int depth, Min_depth, Max_depth, Max_lv, Max_rv, Max_lrv;
}node[maxn<<2];

int n, m;
char parenthesis[maxn];

void init() {
    scanf("%d%d%s", &n, &m, parenthesis+1);
}

Node get_left_parenthesis() {
   return Node{1, 0, 1, 0, 1, 1};
}

Node get_right_parenthesis() {
    return Node{-1, -1, 0, 2, 1, 1};
}

Node shifted_left(int depth, int root) {
    return Node{node[root].depth + depth, node[root].Min_depth+depth, node[root].Max_depth+depth,
                node[root].Max_lv-depth, node[root].Max_rv-depth, node[root].Max_lrv};
}

void merge(int root) {
    int chl = root<<1;
    int chr = root<<1|1;

    Node rhs_shifted = shifted_left(node[chl].depth, chr);

    node[root].depth = rhs_shifted.depth;
    node[root].Min_depth = min(node[chl].Min_depth, rhs_shifted.Min_depth);
    node[root].Max_depth = max(node[chl].Max_depth, rhs_shifted.Max_depth);
    node[root].Max_lv = max(node[chl].Max_lv, max(rhs_shifted.Max_lv, node[chl].Max_depth - 2*rhs_shifted.Min_depth));
    node[root].Max_rv = max(node[chl].Max_rv, max(rhs_shifted.Max_rv, rhs_shifted.Max_depth - 2*node[chl].Min_depth));
    node[root].Max_lrv = max(max(node[chl].Max_lrv, rhs_shifted.Max_lrv), max(node[chl].Max_lv + rhs_shifted.Max_depth,
                                                                              rhs_shifted.Max_rv + node[chl].Max_depth));
}

void build_tree(int root, int l, int r) {
    if(l == r) {
        if(parenthesis[l] == '(') node[root] = get_left_parenthesis();
        else node[root] = get_right_parenthesis();
        return ;
    }

    int mid = l + r >> 1;
    build_tree(root<<1, l, mid);
    build_tree(root<<1|1, mid+1, r);

    merge(root);
}

int query_max() {
    return node[1].Max_lrv;
}

void change(int root, int l, int r, int find_pos, int change_pos) {
    if(l == r) {
        if(parenthesis[change_pos] == '(') node[root] = get_left_parenthesis();
        else node[root] = get_right_parenthesis();
        return ;
    }

    int mid = l + r >> 1;
    if(find_pos <= mid) {
        change(root<<1, l, mid, find_pos, change_pos);
    } else {
        change(root<<1|1, mid+1, r, find_pos, change_pos);
    }

    merge(root);
}

void change(int pos1, int pos2) {
    change(1, 1, 2*n-2, pos1, pos2);
    change(1, 1, 2*n-2, pos2, pos1);
}

int main() {
//    freopen("1.in", "r", stdin);
    init();
    build_tree(1, 1, 2*n-2);

    printf("%d
", query_max());
    while(m--) {
        int pos1, pos2; scanf("%d%d",&pos1, &pos2);
        change(pos1, pos2);
        swap(parenthesis[pos1], parenthesis[pos2]);
        printf("%d
", query_max());
    }
    return 0;
}