求调,样例过不了
查看原帖
求调,样例过不了
167697
BartAllen楼主2024/8/18 09:53
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 5;

int n, root, tot;

struct FHQ {
	int l, r;
	char val;
	int key, size, lazy;
} t[N];

int New(char x) {
	tot++;
	t[tot].l = t[tot].r = 0, t[tot].size = 1;
	t[tot].val = x, t[tot].key = rand();
	return tot;
}

void update(int p) {
	t[p].size = t[t[p].l].size + t[t[p].r].size + 1; 
}

void spread(int p) {
	if (t[p].lazy) {
		swap(t[p].l, t[p].r);
		t[t[p].l].lazy ^= 1, t[t[p].r].lazy ^= 1;
		t[p].lazy = 0;
	}
}

void split(int p, int k, int &l, int &r) {
	if (p == 0) {
		l = r = 0;
		return;
	}
	spread(p);
	if (t[t[p].l].size + 1 <= k) {
		l = p;
		split(t[p].r, k - t[t[p].l].size - 1, t[p].r, r);
	}
	else {
		r = p;
		split(t[p].l, k, l, t[p].l);
	}
	update(p);
}

int merge(int l, int r) {
	if (l == 0 || r == 0) return l + r;
	if (t[l].key > t[r].key) {
		spread(l);
		t[l].r = merge(t[l].r, r);
		update(l);
		return l;
	}
	else {
		spread(r);
		t[r].l = merge(l, t[r].l);
		update(r);
		return r;
	}
}

void inorder(int p) {
	if (p == 0) return;
	inorder(t[p].l);
	cout << t[p].val;
	inorder(t[p].r);
}

int main() {
	srand(time(0));
	int len, L, R, pos = 0, p;
	cin >> n;
	while (n--) {
		string opt;
		cin >> opt;
		if (opt == "Move") cin >> pos;
		if (opt == "Insert") {
			cin >> len;
			split(root, pos, L, R);
			for (int i = 1; i <= len; i++) {
				char ch = getchar();
				while (ch < 32 || ch > 126 || ch == '\n') ch = getchar();
				L = merge(L, New(ch));
			}
			root = merge(L, R);
		}
		if (opt == "Delete") {
			cin >> len;
			split(root, pos + len, L, R);
			split(L, pos, L, p);
			root = merge(L, R);
		}
		if (opt == "Rotate") {
			cin >> len;
			int x = pos, y = pos + len;
			split(root, y, L, R);
			split(L, x - 1, L, p);
			t[p].lazy ^= 1;
			root = merge(merge(L, p), R);
		}
		if (opt == "Get") {
			split(root, pos + 1, L, R);
			split(L, pos, L, p);
			if (t[p].val != '\n') cout << t[p].val;
			cout << endl;
			root = merge(merge(L, p), R);
		}
		if (opt == "Prev") pos--;
		if (opt == "Next") pos++;
	}
//	inorder(root);
	return 0;
} 
2024/8/18 09:53
加载中...