平衡树求调
查看原帖
平衡树求调
326254
LonginusMonkey楼主2023/11/8 23:34
#include<bits/stdc++.h>
const int N = 100000 + 100;
using namespace std;
const double dirta = 0.000001;
struct node{
	int val; int key;
	int size;
	int lson, rson;
}tree[N][2];
int tot[2], root[2];
// ax + b > c
int init(int xx, int type) {
	tree[++tot[type]][type].key = xx;
	tree[tot[type]][type].val = rand();
	tree[tot[type]][type].size = 1;
	return tot[type];
}
int push_up(int xx, int type) {
	int left = tree[xx][type].lson;
	int right = tree[xx][type].rson;
	tree[xx][type].size = tree[left][type].size + tree[right][type].size + 1;
}
int merge(int a, int b, int type) {
	if(!a || !b) {
		return a | b;
	}
	if(tree[a][type].val <= tree[b][type].val) {
		tree[a][type].rson = merge(tree[a][type].rson, b, type);
		push_up(a, type);
		return a;
	} else {
		tree[b][type].lson = merge(a, tree[b][type].lson, type);
		push_up(b, type);
		return b;
	}
}
void split(int index, int xx, int &a, int &b, int type) {
	if(!index) {
		a = 0, b = 0;
		return;
	}
	if(tree[index][type].key <= xx) {
		a = index;
		push_up(a, type);
		split(tree[index][type].rson, xx, tree[index][type].rson, b, type);
	} else {
		b = index;
		push_up(b, type);
		split(tree[index][type].lson, xx, a, tree[index][type].lson, type);
	}
}
struct que{
	int a, b, c;
	int type;
	int is;
	int idx;
}ques[N];
int sum2 = 0;
int cnt;
void Add(int index) {
	int x = 0, y = 0;
	int tp = ques[index].type; 
	split(root[tp], ques[index].idx, x, y, tp);
	merge(x, merge(init(ques[index].idx, tp), y, tp), tp);
}
void Del(int index) {
	if(ques[index].is == 1) {
		return;
	}
	ques[index].is = 1;
	if(ques[index].type == 2) {
		sum2 --;
		return;
	}
	int tp = ques[index].type;
	int x = 0, y = 0;
	int a;
	split(root[tp], ques[index].idx-1, x, y, tp);
	split(y, ques[index].idx, a, y, tp);
	a=merge(tree[a][tp].lson, tree[a][tp].rson, ques[index].type);
	root[tp] = merge(x, merge(a, y, tp), tp);
}
int Query(int index) {
	int x, y;
	int sum = 0, sz = tree[root[1]][1].size;
	split(root[0], index, x, y, 0);
	sum += tree[x][0].size;
	split(root[1], index-1, x, y, 1);
	sum += tree[y][1].size;
	return sum;
}
int main() {
	srand(sizeof("LonginusMonkey"));
	int n; cin >> n; while(n--) {
		string str; cin >> str;
		if(str == "Add") {
			++cnt; cin >> ques[cnt].a >> ques[cnt].b >> ques[cnt].c;
			#define a ques[cnt].a
			#define b ques[cnt].b
			#define c ques[cnt].c
			if(a > 0) {
				ques[cnt].type = 0;
			} else if(a < 0){
				ques[cnt].type = 1;
			} else {
				ques[cnt].type = 2;
				sum2++;
			}
			if(ques[cnt].type == 2) break;
			double tmp = double(c-b) / double(a);
			if(ques[cnt].type == 0) {
				ques[cnt].idx = floor(tmp) + 1;
			} else {
				ques[cnt].idx = ceil(tmp) - 1;
			}
			#undef a
			#undef b
			#undef c
		} else if(str == "Del") {
			int i; cin >> i;
			Del(i);
		} else if(str == "Query") {
			int k; cin >> k;
			cout << Query(k) + sum2 << endl;
		}
	}
	return 0;
} 
2023/11/8 23:34
加载中...