Codeforces Round #350 (Div. 2) E - Correct Bracket Sequence Editor(并查集)

本文主要是介绍Codeforces Round #350 (Div. 2) E - Correct Bracket Sequence Editor(并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给你一个由’(”)’组成的字符串，现有要进行三种操作，第一种是将光标左移，第二种是光标右移，第三种是删除当前光标所指的括号及其对应括号的中间所有的值（题意保证括号都能匹配），光标删完后到下一个，后面没东西了就到前一个，问操作完字符串变成了什么

思路：

记录每个括号的前一个是谁，后一个是谁，自己对应的是谁，以及自己是否被删去了。
那么我们在进行第一，二个操作的时候，就可以直接找到上一个/下一个是谁。
进行第三个操作的时候，我们先删去要删除的括号区间，然后我们把删去后，区间左右的括号的前后关系处理一下即可

错误及反思：

边界处理和光标移动，一共多了四个特判，详见代码

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=500100;
char arr[maxn],oper[maxn];//arr是原字符串  oper是操作字符串
int lef[maxn],righ[maxn],dy[maxn];//lef是前一个 righ是后一个 dy是自己对应的另一个括号坐标
bool did[maxn];//有没有删去
int n,m,p;
int main(){scanf("%d%d%d",&n,&m,&p);p--;scanf("%s",arr);scanf("%s",oper);lef[0]=0;           //初始化前一个和后一个的位置for(int i=1;i<n;i++)lef[i]=i-1;righ[n-1]=n-1;for(int i=0;i<n-1;i++)righ[i]=i+1;stack<int> s;for(int i=0;i<n;i++)    //寻找对应的标号{if(arr[i]=='(')s.push(i);else{int temp=s.top();s.pop();dy[i]=temp;dy[temp]=i;}}for(int i=0;i<m;i++){if(oper[i]=='L')        //前移p=lef[p];else if(oper[i]=='R')   //后移p=righ[p];else{if(arr[p]=='('){for(int j=p;j<=dy[p];)//删除{did[j]=true;if(j==n-1&&righ[j]==n-1)break;j=righ[j];}int l=lef[p];   //把删去后的前后关系进行对应righ[l]=righ[dy[p]];lef[righ[dy[p]]]=l;if(!did[righ[dy[p]]])p=righ[dy[p]];else p=lef[p];}else{for(int j=p;j>=dy[p];){did[j]=true;if(j==0&&lef[j]==0)break;j=lef[j];}int r=righ[p];lef[r]=lef[dy[p]];righ[lef[dy[p]]]=r;if(!did[righ[p]])p=righ[p];else p=lef[dy[p]];}}}for(int k=0;k<n;k++){if(!did[k])printf("%c",arr[k]);}puts("");
}