被卡精度了
查看原帖
被卡精度了
157585
zach0914楼主2020/12/20 10:57
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
using namespace std;

const int MAXN = 1e5 + 5, INF = 1 << 30;

struct splay_tree
{
	int ch[2], val, cnt, siz, Fa;	
} tr[2][MAXN];
bool del[MAXN] = {};
int n, root[2] = {}, tot[2] = {}, a[MAXN], b[MAXN], c[MAXN], d[MAXN];
void Update(int p, int t)
{
	tr[t][p].siz = tr[t][p].cnt + tr[t][tr[t][p].ch[0]].siz + tr[t][tr[t][p].ch[1]].siz;
}
void Connect(int p, int fa, bool pos, int t)
{
	tr[t][p].Fa = fa, tr[t][fa].ch[pos] = p;
}
bool Identity(int p, int t)
{
	return tr[t][tr[t][p].Fa].ch[1] == p;
}
void Rotate(int p, int t)
{
	int q = tr[t][p].Fa, r = tr[t][q].Fa, q_dir = Identity(p, t), r_dir = Identity(q, t);
	Connect(tr[t][p].ch[q_dir ^ 1], q, q_dir, t), Connect(p, r, r_dir, t), Connect(q, p, q_dir ^ 1, t);
	Update(q, t), Update(p, t);
}
void Splay(int p, int to, int t)
{
	int q, r;
	while(tr[t][p].Fa != to)
	{
		q = tr[t][p].Fa, r = tr[t][q].Fa;
		if(r != to) 
			Identity(p, t) ^ Identity(q, t) ? Rotate(p, t) : Rotate(q, t);
		Rotate(p, t);
	}
	if(!to) root[t] = p;
}
void Find(int val, int t)
{
	int p = root[t];
	while(tr[t][p].ch[val > tr[t][p].val] && tr[t][p].val != val) p = tr[t][p].ch[val > tr[t][p].val];
	Splay(p, 0, t);
}
void Insert(int val, int t)
{
	int p = root[t], fa = 0;
	while(p && tr[t][p].val != val) fa = p, p = tr[t][p].ch[val > tr[t][p].val];
	if(p) ++ tr[t][p].cnt;
	else
	{
		p = ++ tot[t];
		if(fa) tr[t][fa].ch[val > tr[t][fa].val] = p;
		tr[t][p].ch[0] = tr[t][p].ch[1] = 0, tr[t][p].val = val, tr[t][p].Fa = fa, tr[t][p].cnt = tr[t][p].siz = 1;
	}
	Splay(p, 0, t);
}
int Query(int val, int opt, int t)
{
	Find(val, t);
	int p = root[t];
	if((tr[t][p].val > val && opt) || (tr[t][p].val < val && !opt)) return p;
	p = tr[t][p].ch[opt];
	while(tr[t][p].ch[opt ^ 1]) p = tr[t][p].ch[opt ^ 1];
	return p;
}
void Remove(int val, int t)
{
	int pre = Query(val, 0, t), nxt = Query(val, 1, t), p;//找节点的	前驱和 后继 
	Splay(pre, 0, t), Splay(nxt, pre, t);
	p = tr[t][nxt].ch[0];
	if(tr[t][p].cnt > 1) -- tr[t][p].cnt, Splay(p, 0, t);
	else tr[t][nxt].ch[0] = 0;
}
int main()
{
//	freopen("data.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	scanf("%d", &n);
	Insert(INF, 0), Insert(-INF, 0);
	Insert(INF, 1), Insert(-INF, 1);
	char opt[10];
	int x, y, z, i, k, cnt = 0, num = 0;
	while(n --)
	{
		cin >> opt;
		if(opt[0] == 'A')
		{
			++ num;
			cin >> a[num] >> b[num] >> c[num];
			if(!a[num]) 
			{
				if(c[num] - b[num] < 0) ++ cnt;
			}
			else
			{
				if(a[num] > 0) 
				{
					d[num] = (int)floor(1.0 * (c[num] - b[num]) / a[num]);	
					Insert(d[num], 0);
				}
				else 
				{
					d[num] = (int)ceil(1.0 * (c[num] - b[num]) / a[num]); 
					Insert(d[num], 1);
				}
			}
		} 
		else if(opt[0] == 'D')
		{
			cin >> i;
			if(!del[i])
			{
				del[i] = true;
				if((!a[i]) && c[i] < b[i]) -- cnt;
				else 
				{
					if(a[i] > 0) Remove(d[i], 0);
					if(a[i] < 0) Remove(d[i], 1);
				}
			}
		}
		else 
		{
			cin >> k;
			Insert(k, 0), Insert(k, 1);
			Find(k, 0), Find(k, 1);
			printf("%d\n", tr[0][tr[0][root[0]].ch[0]].siz - 1 + tr[1][tr[1][root[1]].ch[1]].siz - 1 + cnt);
			Remove(k, 0), Remove(k, 1);
		}
	}
	return 0;
} 
2020/12/20 10:57
加载中...