数据结构的括号的嵌套的判断和匹配的算法,利用C语言编程实现

Problem Description
Miceren likes playing with brackets.

There are N brackets on his desk forming a sequence. In his spare time, he will do Q operations on this sequence, each operation is either of these two types:

  1. Flip the X-th bracket, i.e. the X-th bracket will become ) if it is ( before, otherwise become ( .

  2. In a given subsequence [L, R], query the K-th bracket position number after deleting all matched brackets. If the amount of brackets left is less than K, output -1.
    For example, if N = 10, L = 2, R = 9 and the sequence is ))(()))((). In the sub sequence [2, 9], the brackets sequence is )(()))((. After deleting all matched brackets, the sequence becomes ) )((. If K = 1, answer is 2. If K = 2, answer is 7. If K = 3, answer is 8. If K = 4, answer is 9. If K ≥ 5, answer is -1.

Miceren is good at playing brackets, instead of calculating them by himself.

As his friend, can you help him?

Input
The first line contains a single integer T, indicating the number of test cases.

Each test case begins with two integers N, Q, indicating the number of brackets in Miceren's desk and the number of queries.

Each of following Q lines describes an operation: if it is "1 X", it indicate the first type of operation. Otherwise it will be "2 L R K", indicating the second type of operation.

T is about 100.

1 ≤ N,Q ≤ 200000.

For each query, 1 ≤ X ≤ N and 1 ≤ L ≤ R ≤ N, 1 ≤ K ≤ N.

The ratio of test cases with N > 100000 is less than 10%.

Output
For each query operation, output the answer. If there is no K brackets left, output -1.

Sample Input
1
10 5
))(()))(()
2 2 9 2
2 2 9 3
2 2 9 5
1 3
2 2 9 5

Sample Output
7
8
-1
8

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐