[蓝桥杯 2021 国 AB] 翻转括号序列

Luogu

IDLGP8765

Time2000ms

Memory512MB

DifficultyP5

线段树二分2021蓝桥杯国赛

给定一个长度为 $n$ 的括号序列，要求支持两种操作: 1. 将 $\left[L_{i}, R_{i}\right]$ 区间内（序列中的第 $L_{i}$ 个字符到第 $R_{i}$ 个字符）的括号全部翻转(左括号变成右括号，右括号变成左括号)。 2. 求出以 $L_{i}$ 为左端点时，最长的合法括号序列对应的 $R_{i}$ （即找出最大的 $R_{i}$ 使 $\left[L_{i}, R_{i}\right]$ 是一个合法括号序列）。 ## Input 输入的第一行包含两个整数 $n, m$，分别表示括号序列长度和操作次数。第二行包含给定的括号序列，括号序列中只包含左括号和右括号。接下来 $m$ 行，每行描述一个操作。如果该行为 `1 L R`, 表示第一种操作，区间为 $\left[L, R\right]$；如果该行为 `2 L` 表示第二种操作，左端点为 $L$ 。 ## Output 对于每个第二种操作，输出一行，表示对应的 $R_{i}$。如果不存在这样的 $R_{i}$，请输出 $0$ 。 [samples] ## Note 对于 $20 \%$ 的评测用例，$n, m \leq 5000$; 对于 $40 \%$ 的评测用例，$n, m \leq 30000$; 对于 $60 \%$ 的评测用例，$n, m \leq 100000$; 对于所有评测用例，$1 \leq n \leq 10^{6}, 1 \leq m \leq 2 \times 10^{5}$ 。蓝桥杯 2021 国赛 A 组 H 题（B 组 I 题）。

Samples

Input #1

7 5
((())()
2 3
2 2
1 3 5
2 3
2 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2021 国 AB] 翻转括号序列",
    "description": {
      "content": "给定一个长度为 $n$ 的括号序列，要求支持两种操作: 1. 将 $\\left[L_{i}, R_{i}\\right]$ 区间内（序列中的第 $L_{i}$ 个字符到第 $R_{i}$ 个字符）的括号全部翻转(左括号变成右括号，右括号变成左括号)。 2. 求出以 $L_{i}$ 为左端点时，最长的合法括号序列对应的 $R_{i}$ （即找出最大的 $R_{i}$ 使 $\\left[L_{i},",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8765"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的括号序列，要求支持两种操作:\n\n1. 将 $\\left[L_{i}, R_{i}\\right]$ 区间内（序列中的第 $L_{i}$ 个字符到第 $R_{i}$ 个字符）的括号全部翻转(左括号变成右括号，右括号变成左括号)。\n\n2. 求出以 $L_{i}$ 为左端点时，最长的合法括号序列对应的 $R_{i}$ （即找出最大的 $R_{i}$ 使 $\\left[L_{i},...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments