并查集做法

esay/hard版本,easy版本只取前两个if就可以过了

#include <bits/stdc++.h>
using namespace std;
#define N 200005
int T, n, k, pos = 0, f[N] = {0};
string s, c;
int find(int x)
{
    if (x <= 0)
        return 0;
    if (x > n)
        return n + 1;
    if (f[x] == x)
        return x;
    return f[x] = find(f[x]);
}
int main()
{
    cin >> n >> k;
    cin >> s;
    s = "?" + s;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 1; i <= n; i++)
        if (s[i] == 'I')
        {
            pos = i;
            break;
        }
    for (int i = 1; i <= k; i++)
    {
        cin >> c;
        if (c == "backspace")
        {
            int x = find(pos - 1);
            if (x > 0)
            {
                if (s[x] == '(')
                {
                    int y = find(pos + 1);
                    if (y <= n)
                    {
                        if (s[y] == ')')
                        {
                            s[y] = '0';
                            f[y] = y + 1;
                        }
                    }
                }
                s[x] = '0';
                f[x] = x - 1;
            }
        }
        else if (c == "delete")
        {
            int x = find(pos + 1);
            if (x <= n)
            {
                s[x] = '0';
                f[x] = x + 1;
            }
        }
        else if (c == "<-")
        {
            if (pos > 1)
            {
                int x = find(pos - 1);
                if (x >= 1)
                {
                    swap(s[pos], s[x]);
                    f[x + 1] = pos;
                    pos = x;
                }
            }
        }
        else
        {
            if (pos < n)
            {
                int x = find(pos + 1);
                if (x <= n)
                {
                    swap(s[pos], s[x]);
                    f[x - 1] = pos;
                    pos = x;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (s[i] != '0')
            cout << s[i];
    return 0;
}