題意
https://vjudge.net/problem/CodeForces-1263E
您要設計一個只有一行的打字機，這一行的長度是無限大，一開始可以認為每個字符都是空，您的打字機有一個游標只指向一個字符，一開始指向最左側的字符，
使用者有三種操作：
-
L 將游標向左移一格（當游標已經在最左側時，忽略這次操作）
-
R 將游標向右移一格
-
一個小寫字符或者'(',')' 將當前字符替換為給定字符
您需要在每次操作后，判斷這一行是否是合法括號序列（例如 (ahakioi) 就是合法的，(ige))(tscore 就是非法的），不是輸出 -1，否則輸出最多嵌套數（例如 ()(())()() 的最多嵌套數是 2，(()(()())())(()) 的最多嵌套數是 3），
思路
看上去是個大模擬，實則是個線段樹的技巧題，
用一個pos記錄游標的位置，
記'('為1，')'為-1，其他字符為0，這樣如果有某個前綴和<0（只用判斷前綴和最小值<0即可），那么就不合法，或者所有加起來不等于0，也不合法，
單點更新，維護區間和sum，前綴和最小值mn，前綴和最大值mx，區間前綴和最小值和左右子樹有關，比較左子樹的前綴和最小值、右子樹的前綴和最小值+左子樹的區間和，用小的那個更新mn[rt]，前綴和最大值同理，
那么在合法的情況下，前綴和的最大值即為最多嵌套數，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=1e6+5;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int sum[N<<2],mn[N<<2],mx[N<<2],n;
void pushUp(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]+sum[rt<<1]);
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]+sum[rt<<1]);
}
void update(int L,int C,int l,int r,int rt)
{
if(l==r)
{
sum[rt]=mn[rt]=mx[rt]=C;
return;
}
int m=(l+r)>>1;
if(L <= m) update(L,C,l,m,rt<<1);
else update(L,C,m+1,r,rt<<1|1);
pushUp(rt);
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n;
string s;
cin>>s;
int pos=1,r=1,ans=0;
for(int i=0; i<n; i++)
{
char c=s[i];
if(c=='R') pos++;
else if(c=='L')
{
if(pos>1) pos--;
}
else
{
if(c=='(')
update(pos,1,1,n,1);
else if(c==')')
update(pos,-1,1,n,1);
else
update(pos,0,1,n,1);
}
if(sum[1]!=0||mn[1]<0)
{
cout<<-1<<" ";
}
else
cout<<mx[1]<<" ";
}
cout<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119221.html
標籤：其他
下一篇：Kibana的使用