诡异的错误
查看原帖
诡异的错误
523541
Onana_in_XMFLS楼主2021/10/9 15:57
#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
struct Treap{int l,r,val,dat,cnt,size;}a[100005];
int tot,root,n,Min,sum,s,e;
inline int read()
{
	int x=0,f=1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
	return f*x;
}
inline int New(int val)
{
	a[++tot].val = val;
	a[tot].dat = rand();
	a[tot].cnt = a[tot].size = 1;
	return tot;	
}
inline void Update(int p){a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;}
inline int Get1(int p,int val)
{
	if(!p) return 0;
	if(val == a[p].val) return a[a[p].l].size + 1;
	if(val < a[p].val) return Get1(a[p].l,val);
	return Get1(a[p].r,val) + a[a[p].l].size + a[p].cnt; 	
}
inline int Get2(int p,int rank)
{
	if(!p) return INF;
	if(a[a[p].l].size >= rank) return Get2(a[p].l,rank);
	if(a[a[p].l].size + a[p].cnt >= rank) return a[p].val;
	return Get2(a[p].r,rank - a[a[p].l].size - a[p].cnt);	
}
inline void zig(int &p)
{
	int q = a[p].l;
	a[p].l = a[q].r,a[q].r = p,p = q;
	Update(a[p].r),Update(p);
}
inline void zag(int &p)
{
	int q = a[p].r;
	a[p].r = a[q].l,a[q].l = p,p = q;
	Update(a[p].l),Update(p);
}
inline void Insert(int &p,int val)
{
	if(!p)
	{
		p = New(val);
		return;		
	}	
	if(val == a[p].val)
	{
		a[p].cnt++,Update(p);
		return;
	}
	if(val < a[p].val)
	{
		Insert(a[p].l,val);
		if(a[p].dat < a[a[p].l].dat) zig(p);
	}
	else
	{
		Insert(a[p].r,val);
		if(a[p].dat < a[a[p].r].dat) zag(p);		
	}
	Update(p);	
}
inline int Getpre(int val)
{
	int ans = 1,p = root;
	while(p)
	{
		if(val == a[p].val)
		{
			if(a[p].l > 0)
			{
				p = a[p].l;
				while(a[p].r > 0) p = a[p].r;
				ans = p;
			}
			break;
		}
		if(a[p].val < val && a[p].val > a[ans].val) ans = p;
		p = val<a[p].val?a[p].l:a[p].r;
	}
	return a[ans].val;
}
inline int Getnext(int val)
{
	int ans = 2,p = root;
	while(p)
	{
		if(val == a[p].val)
		{
			if(a[p].r > 0)
			{
				p = a[p].r;
				while(a[p].l > 0) p = a[p].l;
				ans = p;
			}
			break;
		}
		if(a[p].val > val && a[p].val < a[ans].val) ans = p;
		p = val<a[p].val?a[p].l:a[p].r;
	}
	return a[ans].val;	
}
inline void Remove(int &p,int val)
{
	if(!p) return;
	if(val == a[p].val)
	{
		if(a[p].cnt > 1)
		{
			--a[p].cnt;
			Update(p);
			return;
		}
		if(a[p].l || a[p].r)
		{
			if(!a[p].r || a[a[p].l].dat > a[a[p].r].dat) zig(p),Remove(a[p].r,val);
			else zag(p),Remove(a[p].l,val);
			Update(p);
		}
		else p = 0;
		return;
	}
	val < a[p].val?Remove(a[p].l,val):Remove(a[p].r,val);
	Update(p);	
}
int main(int argc,char *argv[])
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	New(-INF),New(INF);
	root = 1;a[1].r = 2;
	Update(root);
	n = read(),Min = read();
	while(n--)
	{
		char ch;
		scanf("%c",&ch);
		int k = read();
		if(ch == 'I' && k-sum >= Min) Insert(root,k-sum),++s,++e;
		else if(ch == 'A') Min -= k,sum += k;
		else if(ch == 'S')
		{
			Min += k,sum -= k;
			int tmp = Min-1,tmp2;
			while(Getpre(tmp) != -INF)
			{
				tmp2 = tmp,tmp = Getpre(tmp);
				Remove(root,Getpre(tmp2));
				--e;
			}
		}
		else if(ch == 'F')
		{
			if(e < k) puts("-1");
			else printf("%d\n",Get2(root,e-k+2)+sum);
		}
	}
	printf("%d",s-e+1);
	return 0;
}

就这个很丑的代码,全WA,我把测试点1的数据下载了下来,本机vsc跑了一遍,结果一模一样,结果我上IDE一测,不管是样例还是测试点1,只会输出个‘1’?这是为什么?

附数据点1:

20 0
I 4
F 1
I 6
S 9
F 14
I 6
I 7
A 8
I 3
F 2
I 9
I 6
I 6
S 3
S 5
I 6
F 1
I 3
A 2
F 5

2021/10/9 15:57
加载中...