splay初学者求助!!!
查看原帖
splay初学者求助!!!
91970
Turing丶楼主2022/10/22 16:52

只过了一个测试样例,实在不知道哪里出错了,求大佬帮看看

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)
#define lowbit(x) (-x & x)
#define sq(x) ((x) * (x))
#define INF 1e9
#define fi first
#define se second

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int, int, int> TUP;

const int mod = 998244353;
const int N = 3e6 + 7, M = 2 * N;
const double PI = acos(-1.0);
const double eps = 1e-8;

struct node
{
    int s[2], p; char v;
    int sz;
    void init(int _p, char _v)
    {
        p = _p, v = _v;
        sz = 1;
    }
}tr[N];
int root, idx, pos = 1;
int nodes[N], tt;
char str[N];
void pushup(int x)
{
    tr[x].sz = tr[tr[x].s[0]].sz + tr[tr[x].s[1]].sz + 1;
}
void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;  // k=0表示x是y的左儿子;k=1表示x是y的右儿子
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}
void splay(int x, int k)
{
    while (tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}
int build(int l, int r, int p)
{
    int mid = l + r >> 1;
    int u = ++ idx;
    tr[u].init(p, str[mid]);
    if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
    if (r > mid) tr[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}
int get_k(int k)
{
    int u = root;
    while (u)
    {
        if (tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].sz + 1 == k) return u;
        else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
    }
    return -1;
}
//内存回收
void dfs(int u)
{
    if (tr[u].s[0]) dfs(tr[u].s[0]);
    if (tr[u].s[1]) dfs(tr[u].s[1]);
    nodes[ ++ tt] = u;
}
void output(int u)
{
    if (tr[u].s[0]) output(tr[u].s[0]);
    putchar(tr[u].v);
    if (tr[u].s[1]) output(tr[u].s[1]);
}
void solve()
{
    char op[10]; scanf("%s", op);
    if (*op == 'I')
    {
        int n; scanf("%d", &n);
		for (int i = 0; i < n; i ++ )
		{
			char ch = getchar();
			if (ch >= 32 && ch <= 126)
				str[i] = ch;
			else i --;
		}
        int l = get_k(pos), r = get_k(pos + 1);
        splay(l, 0), splay(r, l);
        tr[r].s[0] = build(0, n - 1, r);
        pushup(r), pushup(l);
    }
    else if (*op == 'D')
    {
        int n; scanf("%d", &n);
        int l = get_k(pos), r = get_k(pos + n + 1);
        splay(l, 0), splay(r, l);
        // dfs(tr[r].s[0]);
        tr[r].s[0] = 0;
        pushup(r), pushup(l);
    }
    else if (*op == 'G')
    {
        int n; scanf("%d", &n);
        int l = get_k(pos), r = get_k(pos + n + 1);
        splay(l, 0), splay(r, l);
        output(tr[r].s[0]);
        puts("");
    }
    else if (*op == 'M')
    {
        int n; scanf("%d", &n);
        pos = n + 1;
    }
    else if (*op == 'P') pos --;
    else pos ++;
}
int main()
{
    // IOS; cin.tie(0); cout.tie(0);
    // for (int i = 1; i < N; i ++ ) nodes[ ++ tt] = i;
    str[0] = str[1] = '#';
    root = build(0, 1, 0);
    int T; scanf("%d", &T);
    while(T -- ) solve();
    // solve();
    return 0;
}
2022/10/22 16:52
加载中...