[CF1263E] Editor

设计一个只有一行的打字机，这一行的长度是无限大，一开始可以认为每个字符都是空。您的打字机有一个光标只指向一个字符，一开始指向最左侧的字符。使用者有三种操作：L 将光标向左移一格（当光标已经在最左侧时，忽略这次操作），R 将光标向右移一格，一个小写字符或者'(',')' 将当前字符替换为给定字符。您需要在每次操作后，判断这一行是否是合法括号序列，不是输出 -1，否则输出最多嵌套数。

Solution

预先构造出完整长度的序列，所有位置设置为空状态，按时间顺序处理所有操作

将 ( 视为 (1)，) 视为 (-1)，其它视为 (0)，线段树维护前缀和最大值、最小值与区间和

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n;
char op[N];

struct node {
    int mx,mn,val;
} tr[N*4];

int trans(char c) {
    if(c=='(') return 1;
    if(c==')') return -1;
    return 0;
}

node merge(node lc,node rc) {
    node res;
    res.mx = max(lc.mx, lc.val+rc.mx);
    res.mn = min(lc.mn, lc.val+rc.mn);
    res.val = lc.val + rc.val;
    return res;
}

void modify(int p,int l,int r,int pos,int key) {
    if(l==r) {
        tr[p].mx=tr[p].mn=tr[p].val=key;
    }
    else {
        if(pos<=(l+r)/2) modify(p*2,l,(l+r)/2,pos,key);
        else modify(p*2+1,(l+r)/2+1,r,pos,key);
        tr[p]=merge(tr[p*2],tr[p*2+1]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>op+1;
    int pos=1;
    for(int i=1;i<=n;i++) {
        if(op[i]=='R') ++pos;
        else if(op[i]=='L') {if(pos>1) --pos;}
        else modify(1,1,n,pos,trans(op[i]));
        int tmax=tr[1].mx, tmin=tr[1].mn;
        if(tmin>=0 && tr[1].val==0) cout<<tmax<<" ";
        else cout<<-1<<" ";
    }
}