社区讨论

样例过,但全wa

P1486[NOI2004] 郁闷的出纳员参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo2pieb2
此快照首次捕获于
2023/10/23 17:40
2 年前
此快照最后确认于
2023/10/23 17:40
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define N 300010
const int INF=2e9;
using namespace std;
//#define getchar() (strto1==strto2&&(strto2=(strto1=fsr)+fread(fsr,1,1<<15,stdin),strto1==strto2)?EOF:*strto1++)
//char fsr[1<<15],*strto1=fsr,*strto2=fsr;
inline int read()
{
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return s*w;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,m;
struct Balance_Splay_tree 
{
    struct node
    {
    	int s[2];
    	int size,p,v;
    	void init(int _,int __)
    	{
    		v=_,p=__,size=1;
    	}
    }tree[N];
    int root,idx,delta,ans;
    void pushup(int x)
    {
    	tree[x].size=tree[tree[x].s[0]].size+tree[tree[x].s[1]].size+1;
    }
    void rotate(int x)
    {
    	int y=tree[x].p,z=tree[y].p;
    	int k=(tree[y].s[1]==x);
    	tree[x].p=z,tree[z].s[tree[z].s[1]==y]=x;
    	tree[y].s[k]=tree[x].s[k^1],tree[tree[x].s[k^1]].p=y;
    	tree[y].p=x,tree[x].s[k^1]=y;
    	pushup(y);
    	pushup(x);
    }
    void splay(int x,int k)
    {
    	while(tree[x].p!=k)
    	{
    		int y=tree[x].p,z=tree[y].p;
    		if(z!=k)
    		{
    			if((tree[z].s[1]==y)^(tree[y].s[1]==x))rotate(x);
    			else rotate(y);
    		}
    		rotate(x);
    	}
    	if(k==0)root=x;
    }
    int insert(int v)
    {
    	int fa=root,p=0;
    	while(fa)p=fa,fa=tree[fa].s[tree[fa].v<v];
    	idx++;
    	fa=idx;
    	tree[fa].init(v,p);
    	if(p)tree[p].s[tree[p].v<v]=fa,tree[fa].p=p;
    	splay(fa,0);
    	return fa;
    }
    int Kth(int k)
    {
    	int fa=root;
    	while(fa)
    	{
    		if(tree[tree[fa].s[0]].size+1==k)return tree[fa].v;
    		else if(tree[tree[fa].s[0]].size+1<k)k-=tree[tree[fa].s[0]].size+1,fa=tree[fa].s[1];
    		else fa=tree[fa].s[0];
    	}
    }
    int get(int k)
    {
    	int fa=root,ans;
    	while(fa)
    	{
    		if(k<=tree[fa].v)ans=fa,fa=tree[fa].s[0];
    		else fa=tree[fa].s[1];
    	}
    	return ans;
    }
}Tree;
signed main()
{
	n=read(),m=read();
	int L=Tree.insert(-INF),R=Tree.insert(INF);
	while(n--)
	{
		char op=getchar();int x=read();
		if(op=='I')if(x>=m)Tree.ans++,Tree.insert(x-Tree.delta);
		if(op=='A')Tree.delta+=x;
		if(op=='S')
		{
			Tree.delta-=x;
			R=Tree.get(m-Tree.delta);
			Tree.splay(R,0);
			Tree.splay(L,R);
			Tree.tree[L].s[1]=0;
			Tree.pushup(L),Tree.pushup(R); 
		}
		if(op=='F')
		{
			if(Tree.tree[Tree.root].size-2<x)write(-1),puts("");
			else write(Tree.Kth(Tree.tree[Tree.root].size-x)+Tree.delta),puts("");
		}
	}
	write(Tree.ans-Tree.tree[Tree.root].size+2),puts("");
    return 0;
} 

回复

3 条回复,欢迎继续交流。

正在加载回复...