Codeforces 1263E - Editor （字首和、資料結構）

Codeforces Round #603 (Div. 2) E. Editor

題意

有一個長度為無限的文本編輯器，初始時光标在位置\(1\)

給定一個長度為\(n\)的字元串作為操作串，該字元串僅含有小寫英文字母及\('L'\)，\('R'\)，\('('\)，\(')'\)這四種字元

操作串自左向右每個字元表示文本編輯器的每一次操作

如果字元為\(L\)，表示光标向左移動\(1\)格，但如果光标原本就在位置\(1\)，則該操作無效

如果字元為\(R\)，表示光标向右移動\(1\)格

對于其餘所有字元\(c\)，表示光标所在位置的字元将會變成\(c\)（覆寫原文本）

其後對于每次操作進行一次詢問

如果忽略所有空格和小寫字母，隻看左右括号，問是否能夠達到括号比對（每個左括号的右邊都有與之對應的右括号）

若能，詢問括号的最深層次為多少；若不能，輸出\(-1\)

限制

\(1\le n\le 10^6\)

思路

對于括号比對問題，如果我們将左括号\('('\)看作\(1\)，将右括号\(')'\)看作\(-1\)，其餘所有字元看作\(0\)

對于整個字元串做字首和，得到字首和數組，能夠得到”括号比對“的充要條件為：

• 所有數字之和（數組最後一個位置）為\(0\)，否則左右括号數量不同
• 字首和數組中所有位置都不能出現負數，否則必定存在右括号左側沒有比對的左括号

對于光标的移動可以直接進行模拟，對于每次修改，可以使用線段樹來維護字首和數組

例如，如果位置\(p\)此時由空字元變成左括号，表示該位置數值由\(0\)變\(1\)，對于字首和數組而言，\([p,\infty]\)這一段區間内每個位置數值都需要\(+1\)

例如，如果位置\(p\)此時由右括号變成普通小寫字母，表示該位置數值由\(-1\)變\(0\)，對于字首和數組而言，\([p,\infty]\)這一段區間内每個位置數值都需要\(+1\)

例如，如果位置\(p\)此時由左括号變成右括号，表示該位置數值由\(1\)變\(-1\)，對于字首和數組而言，\([p,\infty]\)這一段區間内每個位置數值都需要\(-2\)

其餘情況進行類似的模拟即可

最後對于每次詢問，線段樹查找\(\sum[n,n]\)與\(\min[1,n]\)進行上述判斷

如果能夠得到”括号比對“，則”最深層次“就是字首和數組中的最大值，即\(\max[1,n]\)

代碼

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

namespace SegmentTree
{
    typedef int SegmentTreeType;
    const int MAXN=1e6+50;
    const SegmentTreeType SegmentTreeINF=0x3f3f3f3f;
    struct SegmentTreeNode
    {
        int l,r;
        SegmentTreeType sum,lazy,maxn,minn;
    }tree[MAXN*4];
    struct SegmentTreeResult
    {
        SegmentTreeType sum,minn,maxn;
    };
    void push_up(int id)
    {
        tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
        tree[id].maxn=max(tree[id<<1].maxn,tree[id<<1|1].maxn);
        tree[id].minn=min(tree[id<<1].minn,tree[id<<1|1].minn);
    }
    void push_down(int id)
    {
        if(!tree[id].lazy)
            return;
        int m=tree[id].r-tree[id].l+1;
        tree[id<<1].lazy+=tree[id].lazy;
        tree[id<<1|1].lazy+=tree[id].lazy;
        tree[id<<1].sum+=tree[id].lazy*(m-(m>>1));
        tree[id<<1|1].sum+=tree[id].lazy*(m>>1);
        tree[id<<1].minn+=tree[id].lazy;
        tree[id<<1|1].minn+=tree[id].lazy;
        tree[id<<1].maxn+=tree[id].lazy;
        tree[id<<1|1].maxn+=tree[id].lazy;
        tree[id].lazy=0;
    }
    void buildTree(int l,int r,int id=1)
    {
        tree[id].l=l;
        tree[id].r=r;
        tree[id].lazy=tree[id].sum=tree[id].minn=tree[id].maxn=0;
        if(l==r) return;
        int mid=(l+r)>>1;
        buildTree(l,mid,id<<1);
        buildTree(mid+1,r,id<<1|1);
        push_up(id);
    }
    void update(int l,int r,SegmentTreeType val,int id=1)
    {
        if(l<=tree[id].l&&r>=tree[id].r)
        {
            tree[id].sum+=val*(tree[id].r-tree[id].l+1);
            tree[id].minn+=val;
            tree[id].maxn+=val;
            tree[id].lazy+=val;
            return;
        }
        push_down(id);
        int mid=(tree[id].r+tree[id].l)>>1;
        if(l<=mid) update(l,r,val,id<<1);
        if(r>mid) update(l,r,val,id<<1|1);
        push_up(id);
    }
    SegmentTreeResult query(int l,int r,int id=1)
    {
        if(l<=tree[id].l&&r>=tree[id].r)
            return {tree[id].sum,tree[id].minn,tree[id].maxn};
        push_down(id);
        int mid=(tree[id].r+tree[id].l)>>1;
        SegmentTreeType sum=0,minn=SegmentTreeINF,maxn=-SegmentTreeINF;
        if(l<=mid)
        {
            SegmentTreeResult res=query(l,r,id<<1);
            sum+=res.sum;
            minn=min(minn,res.minn);
            maxn=max(maxn,res.maxn);
        }
        if(r>mid)
        {
            SegmentTreeResult res=query(l,r,id<<1|1);
            sum+=res.sum;
            minn=min(minn,res.minn);
            maxn=max(maxn,res.maxn);
        }
        return {sum,minn,maxn};
    }
    SegmentTreeType querySum(int l,int r,int id=1)
    {
        if(l<=tree[id].l&&r>=tree[id].r)
            return tree[id].sum;
        push_down(id);
        int mid=(tree[id].r+tree[id].l)>>1;
        SegmentTreeType ans=0;
        if(l<=mid) ans+=querySum(l,r,id<<1);
        if(r>mid) ans+=querySum(l,r,id<<1|1);
        return ans;
    }
    SegmentTreeType queryMin(int l,int r,int id=1)
    {
        if(l<=tree[id].l&&r>=tree[id].r)
            return tree[id].minn;
        push_down(id);
        int mid=(tree[id].r+tree[id].l)>>1;
        SegmentTreeType ans=SegmentTreeINF;
        if(l<=mid) ans=min(ans,queryMin(l,r,id<<1));
        if(r>mid) ans=min(ans,queryMin(l,r,id<<1|1));
        return ans;
    }
    SegmentTreeType queryMax(int l,int r,int id=1)
    {
        if(l<=tree[id].l&&r>=tree[id].r)
            return tree[id].maxn;
        push_down(id);
        int mid=(tree[id].r+tree[id].l)>>1;
        SegmentTreeType ans=-SegmentTreeINF;
        if(l<=mid) ans=max(ans,queryMax(l,r,id<<1));
        if(r>mid) ans=max(ans,queryMax(l,r,id<<1|1));
        return ans;
    }
};
using namespace SegmentTree;

int n;
char s[MAXN],t[MAXN];

int main()
{
    scanf("%d%s",&n,s);
    buildTree(1,n);
    int cur=1;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='(')
        {
            if(t[cur]==')')
                update(cur,n,2);
            else if(t[cur]!='(')
                update(cur,n,1);
            t[cur]=s[i];
        }
        else if(s[i]==')')
        {
            if(t[cur]=='(')
                update(cur,n,-2);
            else if(t[cur]!=')')
                update(cur,n,-1);
            t[cur]=s[i];
        }
        else if(s[i]=='L')
            cur=max(cur-1,1);
        else if(s[i]=='R')
            cur++;
        else
        {
            if(t[cur]=='(')
                update(cur,n,-1);
            else if(t[cur]==')')
                update(cur,n,1);
            t[cur]=s[i];
        }
        
        SegmentTreeResult res=query(1,n);
        if(querySum(n,n)!=0||res.minn<0)
            printf("-1 ");
        else
            printf("%d ",res.maxn);
    }
    return 0;
}