splay过样例但是0pt求调
查看原帖
splay过样例但是0pt求调
326254
LonginusMonkey楼主2023/8/23 01:30

我怀疑是push_down搞错了,除了wa还有一个tle

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define maxn 300010
using namespace std;
struct node{
	int s[2], p, v, size, lazy;
	void init(int _p, int _v) {
		p = _p; v = _v;
	}
}tree[maxn];
int idx;
void push_down(int index) {
	tree[index].v += tree[index].lazy;
	tree[tree[index].s[0]].lazy += tree[index].lazy;
	tree[tree[index].s[1]].lazy += tree[index].lazy;
	tree[index].lazy = 0;
}
void push_up(int index) {
	tree[index].size = tree[tree[index].s[0]].size + tree[tree[index].s[1]].size + 1;
}
int root;
int ws(int index) {
	return tree[tree[index].p].s[1] == index;
}
int setson(int son, int father, int whichson) {
	if(father) tree[father].s[whichson] = son;
	if(son) tree[son].p = father;
}
void rotate(int index) {
	int f = tree[index].p, ff = tree[f].p, w = ws(index), wf = ws(f);
	int son = tree[index].s[!w];
	setson(son, f, w); setson(index, ff, wf); setson(f, index, !w);
	push_up(f); push_up(index);
}

void splay(int index, int rt = 0) {
	while(tree[index].p != rt) {
		int f = tree[index].p, ff = tree[f].p;
		if(ff != rt) {
			if(ws(index) == ws(f)) {
				rotate(f);
			} else {
				rotate(index);
			}
		}
		rotate(index);
	}
	if(!rt) root = index;
}

void insert(int index) {
	int u = root, p = 0;
	while(u) {
		push_down(u);
		p = u;
		u = tree[u].s[index > tree[u].v];
	}
	u = ++idx;
	tree[u].size = 1;
	tree[u].p = p;
	tree[u].v = index;
	tree[p].s[index > tree[p].v] =  u;
	splay(u);
}

int n, minn;
int ans = 0;
int ask_v(int index) {
	int u = root, p = 0;
	while(u) {
		push_down(u);
		p = u;
		if(tree[tree[u].s[0]].size+1 == index) {
			int anstemp = tree[u].v;splay(u);
			return anstemp;
		} else if(tree[tree[u].s[0]].size+1 > index) {
			u = tree[u].s[0];
		} else {
			u = tree[u].s[1];
			index = index-tree[tree[u].s[0]].size-1;
		}
	}
	return 0;
}
int ask_index(int index) {
	int u = root, p=0;
	while(u) {
		push_down(u);
		p = u;
		u = tree[u].s[index > tree[u].v];
	}
	return p;
}
int idxminn;
void del() {
	int temp1 = ask_index(minn);
	temp1++;
	if(temp1 == idxminn) {
		return;
	}
	splay(temp1); splay(idxminn, temp1);
	ans += tree[tree[idxminn].s[1]].size;
	tree[idxminn].s[1] = 0;
	push_up(idxminn); push_up(temp1);
}
signed main() {
//	freopen("a.in","r",stdin);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> minn; int sum = 0;
	insert(inf); insert(-inf);
	idxminn = idx;
	for(int i=1; i<=n; ++i) {
		char ch; cin >> ch;
		if(ch == 'I') {
			int k; cin >> k;
			if(k>minn) insert(k);
		} else if(ch == 'A') {
			int k; cin >> k;
			tree[root].lazy += k;
		} else if(ch == 'S') {
			int k; cin >> k;
			tree[root].lazy -= k;
			del();
			//
		} else if(ch == 'F') {
			int k; cin >> k;
			if(k > tree[root].size-2) {
				cout << -1 << endl;
			} else {
				cout << ask_v(tree[root].size-k) << endl;
			}
		} 
	}
	cout << ans;
	return 0;
}
/*
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
*/
2023/8/23 01:30
加载中...