括号

Luogu

IDLGP10513

Time1000ms

Memory512MB

DifficultyP5

线段树洛谷原创O2优化洛谷月赛

圆给了你一个长度为 $n$ 的字符串 $S$，$S$ 仅由 ```(``` 和 ```)``` 构成。她会对其做 $m$ 次操作，操作有两种类型： 1. ```1 l r```，她会翻转 $l$ 到 $r$ 的括号，即 ```(``` 变 ```)```，```)``` 变 ```(```。 1. ```2 l r```，她想知道区间 $\left[ l,r\right]$ 中最长合法括号子序列的长度除以 $2$ 的答案。圆认为以下的括号序列是合法的： 1. 空序列是一个合法序列。 1. 如果 ```A``` 是一个合法序列，则 ```(A)``` 也是一个合法序列。 1. 如果 ```A``` 和 ```B``` 都是合法序列，则 ```AB``` 也是一个合法序列。圆认为，序列 $a$ 的子序列是满足 $1\le i_1<i_2<···<i_k \le n$ 的序列 $[a_{i_1},a_{i_2},...a_{i_k}]$。由于操作太多了，她算不过来，请你帮帮她吧。 ## Input 第一行一个整数 $n$。第二行一个长度为 $n$ 的字符串 $S$，保证仅由 ```(``` 和 ```)``` 构成。第三行一行一个整数 $m$。接下来 $m$ 行，每行三个数 $op$，$l$，$r$，对应上面的两种操作。 ## Output 对于每一个 $op=2$ 的操作，输出一行一个整数，表示答案。 [samples] ## Note **【样例解释】** - 第一次截取的字符串是 ```()```，答案为 $1$。 - 翻转后字符串变为 ```))(())```。 - 第二次截取的字符串是 ```)(```，答案为 $0$。 - 第三次截取的字符串是 ```())```，答案为 $1$。 - 第四次截取的字符串是 ```(())```，答案为 $2$。 **【数据范围】** - 对于 $10\%$ 的数据，$1 \leq n,m \leq 500$； - 对于 $20\%$ 的数据，$1 \leq n,m \leq 5000$； - 对于 $40\%$ 的数据，$1 \leq n,m \leq 2\times 10^5$； - 另有 $10\%$ 的数据，满足 $op=2$ 且数据随机生成； - 另有 $15\%$ 的数据，满足 $op=2$ 但不保证数据随机生成；对于所有数据，保证 $1\le n \le 5\times 10^5$，$1\le m \le 5 \times 10^5$，$1 \le l \le r \le n$，$op \in \{1,2\}$。数据有梯度。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "括号",
    "description": {
      "content": "圆给了你一个长度为 $n$ 的字符串 $S$，$S$ 仅由 ```(``` 和 ```)``` 构成。 她会对其做 $m$ 次操作，操作有两种类型： 1. ```1 l r```，她会翻转 $l$ 到 $r$ 的括号，即 ```(``` 变 ```)```，```)``` 变 ```(```。 1. ```2 l r```，她想知道区间 $\\left[ l,r\\right]$ 中最长合法括号子",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10513"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "圆给了你一个长度为 $n$ 的字符串 $S$，$S$ 仅由 ```(``` 和 ```)``` 构成。\n\n她会对其做 $m$ 次操作，操作有两种类型：\n\n1. ```1 l r```，她会翻转 $l$ 到 $r$ 的括号，即 ```(``` 变 ```)```，```)``` 变 ```(```。\n1. ```2 l r```，她想知道区间 $\\left[ l,r\\right]$ 中最长合法括号子...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments