Рубрики

Пары, участвующие в сбалансированных скобках

Для заданной строки скобок задача состоит в том, чтобы найти количество пар скобок, участвующих в сбалансированной последовательности в заданном диапазоне.

Примеры :

Input : ((())(()
Range : 1 5
Range : 3 8
Output : 2
         2
Explanation :  In range 1 to 5 ((()), 
there are the two pairs. In range 3 to 8 ())
((), there are the two pairs.

Input : )()()))
Range : 1 2
Range : 4 7
Output : 0
         1
Explanation :  In range 1 to 2 )( there 
is no any pair. In range 4 to 7 ())), 
there is the only pair

Условие: Сегмент деревьев

Подходить :
Здесь, в дереве сегментов, для каждого узла сохраните несколько простых элементов, таких как целые числа или множества, векторы и т. Д.
Для каждого узла оставьте три целых числа:
1. t = Ответ за интервал.
2. o = Количество открывающих скобок '(', оставшихся после удаления скобок тех, кто принадлежит к правильной последовательности скобок в этом интервале с длиной t.
3. c = Количество закрывающих скобок ')', оставшихся после удаления скобок тех, кто принадлежит к правильной последовательности скобок в этом интервале с длиной t.
Теперь, имея эти переменные, можно легко отвечать на запросы, используя дерево сегментов.

Ниже приведена реализация вышеуказанного подхода:

// код CPP для определения количества пар
// участвует в сбалансированных паратезах
#include <bits/stdc++.h>

using namespace std;

  
// Наш структурный узел

struct node {

      

    // требуется три переменные

    int t, o, c;

};

  
// Объявляем массив узлов очень больших
// размер, который действует здесь как дерево сегментов.

struct node tree_arr[5 * 1000];

  
// Чтобы построить сегментное дерево, мы передаем 1 как
// 'id' 0 как 'l' и l как 'n'.
// Здесь мы рассматриваем интервал запроса как [x, y)

void build(int id, int l, int r, string s)

{

    / * это базовое условие является общим для

       построить любое дерево сегментов * /

    // Это база

    // Остался только один элемент

    if (r - l < 2) {

          

        // Если этот элемент является открытой скобкой

        if (s[l] == '(')

            tree_arr[id].o = 1;

          

        // Если этот элемент является открытой скобкой

        else

            tree_arr[id].c = 1;

        return;

    }

  

    // Следующие три строки являются общими

    // для любого дерева сегментов.

    int mid = (l + r) / 2;

      

    // для левого дерева

    build(2 * id, l, mid, s); 

      

    // для правильного дерева

    build(2 * id + 1, mid, r, s);

  

    // Здесь мы берем минимум левого дерева

    // открывающие скобки и правое дерево

    // закрывающие скобки

    int tmp = min(tree_arr[2 * id].o, 

                  tree_arr[2 * id + 1].c);

  

    // мы добавляем это к нашему ответу.

    tree_arr[id].t = tree_arr[2 * id].t + 

              tree_arr[2 * id + 1].t + tmp;

  

    // Удалить ответ из открывающих скобок

    tree_arr[id].o = tree_arr[2 * id].o + 

               tree_arr[2 * id + 1].o - tmp;

  

    // Удалить ответ из открывающих скобок

    tree_arr[id].c = tree_arr[2 * id].c + 

               tree_arr[2 * id + 1].c - tmp;

}

  
// Это вернет ответ для каждого запроса.
// Здесь мы рассматриваем интервал запроса как [x, y)

node segment(int x, int y, int id, 

             int l, int r, string s)

{

    // Если заданный интервал находится вне диапазона

    if (l >= y || x >= r) {

        struct node tem;

        tem.t = 0;

        tem.o = 0;

        tem.c = 0;

        return tem;

    }

  

    // Если данный интервал полностью лежит

    if (x <= l && r <= y)

        return tree_arr[id];

  

    // Следующие три строки являются общими для

    // любое дерево сегментов.

    int mid = (l + r) / 2;

      

    // Для левого дерева

    struct node a = 

           segment(x, y, 2 * id, l, mid, s);

      

    // Для правильного дерева

    struct node b = 

           segment(x, y, 2 * id + 1, mid, r, s);

  

    // То же, что сделано в функции сборки

    int temp;

    temp = min(a.o, b.c);

    struct node vis;

    vis.t = a.t + b.t + temp;

    vis.o = a.o + b.o - temp;

    vis.c = a.c + b.c - temp;

  

    return vis;

}

  
// Код драйвера

int main()

{

    string s = "((())(()";

    int n = s.size();

  

    // диапазон для запроса

    int a = 3, b = 8;

      

    build(1, 0, n, s);

      

    // Здесь мы рассматриваем интервал запроса как [a, b)

    // Вычитаем 1 из «а», потому что индексы начинаются

    // с 0.

    struct node p = segment(a-1, b, 1, 0, n, s);

    cout << p.t << endl;

      

    return 0;

}

Выход:

2

Рекомендуемые посты:

Пары, участвующие в сбалансированных скобках

0.00 (0%) 0 votes