Homework Introduction

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, Inf = 1e9;

struct node {
	int ch[2], fa, val, cnt;
	int size;
} tree[N];
int n, m, root, tot;

void pushup(int x) {
	if (!x)
		return;
	tree[x].size = tree[tree[x].ch[0]].size + tree[tree[x].ch[1]].size + tree[x].cnt;
}

int Get(int x) {
	return x == tree[tree[x].fa].ch[1];
}

void rotate(int x) {
	//将x旋转至父亲之上
	int y = tree[x].fa, z = tree[y].fa;
	int chk = Get(x);

	tree[y].ch[chk] = tree[x].ch[chk ^ 1];
	if (tree[x].ch[chk ^ 1])
		tree[tree[x].ch[chk ^ 1]].fa = y;

	tree[x].ch[chk ^ 1] = y;
	tree[y].fa = x;

	if (z)
		tree[z].ch[y == tree[z].ch[1]] = x;
	tree[x].fa = z;

	pushup(y);
	pushup(x);
}

void splay(int x, int k) {
	//将x旋转至k的儿子，如果k=0，旋转至根
	while (tree[x].fa != k) {
		int y = tree[x].fa, z = tree[y].fa;
		if (z != k) {
			if (Get(x) == Get(y))
				rotate(y);
			else
				rotate(x);
		}
		rotate(x);
	}
	if (k == 0)
		root = x;
}

void insert(int x) {
	int cur = root;
	int fa = 0;
	while (cur) {
		if (tree[cur].val == x) {
			tree[cur].cnt++;
			pushup(cur);
			pushup(fa);
			splay(cur, 0);
			return;
		}
		fa = cur;
		cur = tree[cur].ch[x > tree[cur].val];
	}
	cur = ++tot;
	tree[cur].val = x;
	tree[cur].fa = fa;
	tree[cur].cnt = 1;
	tree[fa].ch[x > tree[fa].val] = cur;
	pushup(cur);
	pushup(fa);
	splay(cur, 0);
}

int rnk(int x) {
	int cur = root;
	int res = 0;
	while (cur) {
		if (x < tree[cur].val) {
			cur = tree[cur].ch[0];
		} else {
			res += tree[tree[cur].ch[0]].size;
			if (x == tree[cur].val) {
				splay(cur, 0);
				return res + 1;
			} else {
				res += tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return res + 1;
}

int kth(int x) {
	int cur = root;
	while (cur) {
		if (x <= tree[tree[cur].ch[0]].size) {
			cur = tree[cur].ch[0];
		} else {
			x -= tree[tree[cur].ch[0]].size;
			if (x <= tree[cur].cnt) {
				splay(cur, 0);
				return cur;
			} else {
				x -= tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}

int pre(int x) {
	int cur = root;
	int res = -Inf;
	while (cur) {
		if (x <= tree[cur].val) {
			cur = tree[cur].ch[0];
		} else {
			res = max(res, tree[cur].val);
			cur = tree[cur].ch[1];
		}
	}
	return res;
}

int nxt(int x) {
	int cur = root;
	int res = Inf;
	while (cur) {
		if (x >= tree[cur].val) {
			cur = tree[cur].ch[1];
		} else {
			res = min(res, tree[cur].val);
			cur = tree[cur].ch[0];
		}
	}
	return res;
}

void find(int x) {
	int cur = root;
	while (cur) {
		if (tree[cur].val == x) {
			splay(cur, 0);
			return;
		} else
			cur = tree[cur].ch[x > tree[cur].val];
	}
}

void del(int x) {
	find(x);
	int L = tree[root].ch[0], R = tree[root].ch[1];
	while (tree[L].ch[1])
		L = tree[L].ch[1];
	while (tree[R].ch[0])
		R = tree[R].ch[0];
	splay(L, 0);
	splay(R, L);
	if (tree[tree[R].ch[0]].cnt == 1) {
		tree[R].ch[0] = 0;
	} else {
		tree[tree[R].ch[0]].cnt--;
	}
	pushup(tree[R].ch[0]);
	pushup(R);
	pushup(L);
}

int main() {
	cin >> n;
	insert(-Inf);
	insert(Inf);
	while (n--) {
		int opt, x, y, z;
		cin >> opt >> x;
		if (opt == 1) {
			insert(x);
		} else if (opt == 2) {
			del(x);
		} else if (opt == 3) {
			cout << rnk(x) - 1 << endl;
		} else if (opt == 4) {
			cout << tree[kth(x + 1)].val << endl;
		} else if (opt == 5) {
			cout << pre(x) << endl;
		} else
			cout << nxt(x) << endl;
	}
	return 0;
}

void rev(int x, int y) {
	int l = kth(x);
	int r = kth(y + 2);
	splay(l, 0);
	splay(r, l);
	tree[tree[r].ch[0]].tag ^= 1;
	swap(tree[tree[r].ch[0]].ch[0], tree[tree[r].ch[0]].ch[1]);
}

void print(int x) {
	pushdown(x);
	if (tree[x].ch[0])
		print(tree[x].ch[0]);
	if (tree[x].val >= 1 && tree[x].val <= n)
		cout << tree[x].val << " ";
	if (tree[x].ch[1])
		print(tree[x].ch[1]);
}

int build(int l, int r, int fa) {
	int cur = ++tot;
	int mid = (l + r) >> 1;
	tree[cur].val = name[mid];
	tree[cur].fa = fa;
	if (mid > l)
		tree[cur].ch[0] = build(l, mid - 1, cur);
	if (r > mid)
		tree[cur].ch[1] = build(mid + 1, r, cur);
	pushup(cur);
	return cur;
}


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, Inf = 1e12;

struct node {
	int ch[2], fa, val, size, cnt;
} tree[N];
int n, m, q, root, tot;
int delta;

void pushup(int x) {
	if (!x)
		return;
	tree[x].size = tree[tree[x].ch[0]].size + tree[tree[x].ch[1]].size + tree[x].cnt;
}

int Get(int x) {
	return x == tree[tree[x].fa].ch[1];
}

void rotate(int x) {
	int y = tree[x].fa, z = tree[y].fa;
	int chk = Get(x);
	tree[y].ch[chk] = tree[x].ch[chk ^ 1];
	if (tree[x].ch[chk ^ 1])
		tree[tree[x].ch[chk ^ 1]].fa = y;
	tree[x].ch[chk ^ 1] = y;
	tree[y].fa = x;
	if (z)
		tree[z].ch[y == tree[z].ch[1]] = x;
	tree[x].fa = z;
	pushup(y);
	pushup(x);
}

void splay(int x, int k) {
	while (tree[x].fa != k) {
		int y = tree[x].fa, z = tree[y].fa;
		if (z != k) {
			if (Get(x) == Get(y))
				rotate(y);
			else
				rotate(x);
		}
		rotate(x);
	}
	if (k == 0)
		root = x;
}

void insert(int x) {
	int cur = root;
	int fa = 0;
	while (cur) {
		if (tree[cur].val == x) {
			tree[cur].cnt++;
			pushup(cur);
			pushup(fa);
			splay(cur, 0);
			return;
		}
		fa = cur;
		cur = tree[cur].ch[x > tree[cur].val];
	}
	cur = ++tot;
	tree[cur].val = x;
	tree[cur].fa = fa;
	tree[cur].cnt = 1;
	tree[fa].ch[x > tree[fa].val] = cur;
	pushup(cur);
	pushup(fa);
	splay(cur, 0);
}

int kth(int x) {
	int cur = root;
	while (cur) {
		if (x <= tree[tree[cur].ch[0]].size)
			cur = tree[cur].ch[0];
		else {
			x -= tree[tree[cur].ch[0]].size;
			if (x <= tree[cur].cnt) {
				splay(cur, 0);
				return cur;
			} else {
				x -= tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}

int nxt(int x) {
	int cur = root;
	int res = Inf + 1, id = -1;
	while (cur) {
		//	cout << cur << endl;
		if (tree[cur].val > x) {
			if (tree[cur].val < res) {
				id = cur;
				res = tree[cur].val;
			}
			cur = tree[cur].ch[0];
		} else
			cur = tree[cur].ch[1];
	}
	return id;
}

void print(int x) {
	cout << x << ' ' << tree[x].val << " " << tree[x].ch[0] << " " << tree[x].ch[1] << endl;
	if (tree[x].ch[0])
		print(tree[x].ch[0]);
	if (tree[x].ch[1])
		print(tree[x].ch[1]);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int res = 0;
	insert(-Inf);
	insert(Inf);
	for (int i = 1; i <= n; i++) {
		char pos;
		int x;
		cin >> pos >> x;
		if (pos == 'I') {
			if (x >= m) {
				insert(x - delta);
			}
		} else if (pos == 'A') {
			delta += x;
		} else if (pos == 'S') {
			delta -= x;
			//有多少个工资+delta<m
			//找工资<m-delta的
			//	print(root);
			int L = 1, R = nxt(m - delta - 1);
			splay(L, 0);
			splay(R, L);
			res += tree[tree[R].ch[0]].size;
			tree[R].ch[0] = 0;
			pushup(R);
			pushup(L);
		} else {
			if (x > tree[root].size - 2)
				cout << -1 << endl;
			else
				cout << tree[kth(tree[root].size - x)].val + delta << endl;
		}
	}
	cout << res << endl;
	return 0;
}


void inserttree(int x, int y) {
	//将编号为x的节点插入y树
	int cur = root[y];
	int fa = 0;
	while (cur) {
		fa = cur;
		cur = tree[cur].ch[tree[x].val > tree[cur].val];
	}
	if (tree[x].val > tree[fa].val) {
		tree[fa].ch[1] = x;
		tree[x].fa = fa;
	} else {
		tree[fa].ch[0] = x;
		tree[x].fa = fa;
	}
	tree[x].ch[0] = tree[x].ch[1] = 0;
	pushup(x);
	pushup(fa);
	splay(x, 0, y);
}

void mergetree(int x, int y) {
	//x树中的每一个节点合并进y
	if (tree[x].ch[0])
		mergetree(tree[x].ch[0], y);
	if (tree[x].ch[1])
		mergetree(tree[x].ch[1], y);
	inserttree(x, y);
}

void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx != fy) {
		if (tree[root[fx]].size < tree[root[fy]].size) {
			mergetree(fx, fy);
			fa[fx] = fy;
		} else {
			mergetree(fy, fx);
			fa[fy] = fx;
		}
	}
}

Problem

Please claim the assignment to see the problems.
Status
Live...
Problem
14
Open Since
2025-8-19 0:00
Deadline
2025-11-30 23:59
Extension
24 hour(s)
  1. Judging Queue
  2. Service Status
  3. Legacy mode
  4. Theme
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 19ms
  4. Powered by Hydro v5.0.0-beta.9 Community