萌 新 求 助 fhq Treap
  • 板块P2073 送花
  • 楼主Dreamweaver
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/6/9 23:14
  • 上次更新2023/11/4 22:04:46
查看原帖
萌 新 求 助 fhq Treap
91956
Dreamweaver楼主2021/6/9 23:14

救救孩子吧,孩子快调疯了

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define inf 0x3f3f3f3f
#define re register
#define maxn 100010
#define int long long
#define Orz cout<<"stO %王队% Orz<<'\n';
struct node
{
	int l,r,size,beauty,value,pri;
	#define ls(x)	t[x].l
	#define rs(x)	t[x].r
	#define p(x)	t[x].pri
	#define b(x)	t[x].beauty
	#define v(x)	t[x].value
	#define s(x)	t[x].size	
}t[maxn];
int tt,n,op;
int amo;
int x,y,z;
int cnt,root;
int ans,cost;
int rr()
{
	return rand();
} 
int newnode(int val,int bb)
{
	p(++cnt)=rr();
	ls(cnt)=rs(cnt)=0;
	v(cnt)=val;
	b(cnt)=bb;
	s(cnt)=1;
	return cnt;
}
void update(int k)
{
	s(k)=s(ls(k))+s(rs(k))+1;
	return ;
}
void split(int now,int val,int &x,int &y)
{
	if(!now)
	{
		x=y=0;
		return ;
	}
	if(v(now)<=val)
		x=now,split(rs(now),val,rs(now),y);
	else
		y=now,split(ls(now),val,x,ls(now));
	update(now);
	return ;
}
void split2(int now,int siz,int &x,int &y)
{
	if(!now)
	{
		x=y=0;
		return ;
	}
	if(s(ls(now))<siz)
		x=now,split(rs(now),siz-s(ls(now))-1,rs(now),y);
	else
		y=now,split(ls(now),siz,x,ls(now));
	update(now);
}
int merge(int x,int y)
{
	if(!x||!y)	return x+y;
	if(p(x)<p(y))
	{
		rs(x)=merge(rs(x),y);
		update(x);
		return x;
	}
	else
	{
		ls(y)=merge(x,ls(y));
		update(y);
		return y;
	}
}
void insert(int val,int bb)
{
	if(!root)
	{
		root=newnode(val,bb);
		return ;
	}
	split(root,val,x,y);
	split(x,val-1,x,z);
	if(s(z)){
		root=merge(merge(x,z),y);
		return ;
	}
	root=merge(merge(x,newnode(val,bb)),y);
	return ;
}
//int gettnum(int rank)
//{
//	int x=root;
//	while(x)
//	{
//		if(s(ls(x))>=rank)
//			x=ls(x);
//		else
//			if(rank<=s(ls(x))+1)
//				return v(x);
//			else
//				rank-=(s(ls(x))+1),x=rs(x);
//	}
//	return -inf;
//}
//inline int getnum(int rank)
//{
//    int now=root;
//    while(now)
//    {
//        if(s(ls(now))+1==rank)
//            break;
//        else if(s(ls(now))>=rank)
//            now=ls(now);
//        else 
//        {
//            rank-=s(ls(now))+1;
//            now=rs(now);
//        }
//    }
//    return v(now);
//}
//void del(int val)
//{
//	split(root,val,x,z);
//	split(x,val-1,x,y);
//	y=merge(ls(y),rs(y));
//	root=merge(merge(x,y),z);
//	return ;
//}
void d1()
{
//	int x=root;
//	while(ls(ls(x)))	x=ls(x);
//	ls(x)=0;
//	return ;
//	del(getnum(1));
	split2(root,1,x,root);
//	root=y;
}
//bool find(int val)
//{
//	int x=root;
//	while(x)
//	{
//		if(v(x)==val)	return true;
//		if(v(x)<val)
//			x=rs(x);
//		else
//			x=ls(x);
//	}
//	return false;
//}
void d2()
{
//	int x=root;
//	while(rs(rs(x)))	x=rs(x);
//	rs(x)=0;
//	return ;
//	del(getnum(amo));
	split2(root,s(root)-1,root,y);
//	root=x;
}
void get(int x)
{
	if(!x)	return ;

	ans+=b(x);
	cost+=v(x);
	get(rs(x));
	get(ls(x));
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0'; ch=getchar();}
    return x*f;
}
signed main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
//	printf("%dM\n",(sizeof(dp) >> 20));
	srand((int)time(0));
	int a,b;
	while(op=read())
	{
		if(op==-1)	break;
		if(op==1)
		{
			a=read(),b=read();
			insert(b,a);
		}
			if(op==2)
				d1();
			if(op==3)
				d2();
	}
	get(root);
	cout<<ans<<' '<<cost;
	return 0;
}

2021/6/9 23:14
加载中...