Editor

发表于 分类于 ，

    您要设计一个只有一行的打字机，这一行的长度是无限大，一开始可以认为每个字符都是空。您的打字机有一个光标只指向一个字符，一开始指向最左侧的字符。

    使用者有三种操作：

    • L 将光标向左移一格（当光标已经在最左侧时，忽略这次操作）

    • R 将光标向右移一格

    • 一个小写字符或者'(',')' 将当前字符替换为给定字符

    您需要在每次操作后，判断这一行是否是合法括号序列（例如 (ahakioi) 就是合法的，(ige))(tscore 就是非法的），不是输出 -1，否则输出最多嵌套数（例如 ()(())()() 的最多嵌套数是 2，(()(()())())(()) 的最多嵌套数是 3）。

    第一行输入一个正整数 $n(1\le n\le 10^6)$ 表示操作数

    接下来一行一个长度为 $n$ 的字符串，只含 L,R,(,),小写字母，表示操作序列，第 $i$ 个字符表示第 $i$ 次操作。

    输出 $n$ 个正整数表示每次操作后的结果。

    ```plain

    1. (

    2. (

    3. (a

    4. (a

    5. (ab

    6. (ab

    7. (ab)

    8. (ab)

    9. (a))

    10. (a))

    11. (())

    ```

Editor

Created by LXC on Sat Feb 10 13:54:14 2024

https://codeforces.com/problemset/problem/1263/E

ranting: 2100

tag: data structures, implementation

problem

您要设计一个只有一行的打字机，这一行的长度是无限大，一开始可以认为每个字符都是空。您的打字机有一个光标只指向一个字符，一开始指向最左侧的字符。

使用者有三种操作：

  • L 将光标向左移一格（当光标已经在最左侧时，忽略这次操作）

  • R 将光标向右移一格

  • 一个小写字符或者’(‘,’)’ 将当前字符替换为给定字符

您需要在每次操作后，判断这一行是否是合法括号序列（例如 (ahakioi) 就是合法的，(ige))(tscore 就是非法的），不是输出 -1，否则输出最多嵌套数（例如 ()(())()() 的最多嵌套数是 2，(()(()())())(()) 的最多嵌套数是 3）。

第一行输入一个正整数 $n(1\le n\le 10^6)$ 表示操作数

接下来一行一个长度为 $n$ 的字符串，只含 L,R,(,),小写字母，表示操作序列，第 $i$ 个字符表示第 $i$ 次操作。

输出 $n$ 个正整数表示每次操作后的结果。

1
2
3
4
5
6
7
8
9
10
11
1. (
2. (
3. (a
4. (a
5. (ab
6. (ab
7. (ab)
8. (ab)
9. (a))
10. (a))
11. (())

solution

栈的应用

对于合法串，需要的最少颜色其实就是最大括号的嵌套深度

用两个栈维护，光标左侧的字符，和光标以及右侧的字符。

此外我们需要维护前缀/后缀嵌套括号的最大深度。

对于光标前的字符串其每个前缀的最大嵌套括号深度求解。我们将(视为1,)视为-1。求前缀和得到$wl$，并维护前缀和的最大值$dl$则是当前前缀的最大嵌套括号深度。如果出现前缀和为-1,则括号序列无效，我们将深度设为无穷。

对于光标前的字符串其每个前缀的最大嵌套括号深度求解。我们将)视为1,(视为-1。求前缀和得到$wr$，并维护前缀和的最大值$dr$则是当前前缀的最大嵌套括号深度。如果出现前缀和为-1,则括号序列无效，我们将深度设为无穷。

对于每次操作，只需要操作两个栈的栈顶最多一次。$O(1)$复杂度

对于每次操作后，整个串的最大深度，wl是左串中多余的(，wr是右串中多余的)，若两者数量不同则无法组成合法串，相同则为最大深度贡献wl。此外dl和dr是左右两串的最大深度，整个串的最大深度也由两者贡献。注意非法串dl和dr中最大值为无穷大。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> dl(1, 0), dr(1,0), wl(1,0), wr(1,0);
    string l, r;
    for (char i:s) {
        if (i == 'L') {
			if (!l.empty()) {
            	r.push_back(l.back());
            	l.pop_back();
            	dl.pop_back();
            	wl.pop_back();
            	if (r.back() == ')') {
                	wr.push_back(wr.back()+1);
                	dr.push_back(max(dr.back(), wr.back()));
            	} else if (r.back() == '(') {
                	wr.push_back(wr.back()-1);
                	if (wr.back() < 0) dr.push_back(INF);
                	else dr.push_back(max(dr.back(), wr.back()));
            	} else {
                	wr.push_back(wr.back());
                	dr.push_back(dr.back());               
            	}
            }
        } 
        else if (i == 'R') {
        	if (r.empty()) {
                l.push_back(' ');
                dl.push_back(dl.back());
                wl.push_back(wl.back());
            } else {
                l.push_back(r.back());
                r.pop_back();
                dr.pop_back();
                wr.pop_back();
                if (l.back() == '(') {
                    wl.push_back(wl.back()+1);
                    dl.push_back(max(dl.back(), wl.back()));
                } else if (l.back() == ')') {
                    wl.push_back(wl.back()-1);
                    if (wl.back() < 0) dl.push_back(INF);
                    else dl.push_back(max(dl.back(), wl.back()));
                } else {
                    wl.push_back(wl.back());
                    dl.push_back(dl.back());               
                }   
            } 
        }
        else if (i == '(') {
			if (r.size()) {
            	wr.pop_back();
        		dr.pop_back();
                r.pop_back();    
            }
            r.push_back('(');
            wr.push_back(wr.back()-1);
            if (wr.back() < 0) dr.push_back(INF);
            else dr.push_back(max(dr.back(), wr.back()));
        }
        else if (i == ')') {
			if (r.size()) {
            	wr.pop_back();
        		dr.pop_back();
                r.pop_back();    
            }
            r.push_back(')');
            wr.push_back(wr.back()+1);
            dr.push_back(max(dr.back(), wr.back()));
        }
		else {
			if (r.size()) {
            	wr.pop_back();
        		dr.pop_back();
                r.pop_back();    
            }
            r.push_back(i);
            wr.push_back(wr.back());
            dr.push_back(dr.back());
        }
        if (wl.back() != wr.back()) {
            cout << "-1 ";
        } else {
            int t = max({dr.back(), dl.back(), wl.back()});
        	cout << (t == INF?-1:t) << " ";
        }
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}