求助FHQTreap 0pts
查看原帖
求助FHQTreap 0pts
939837
Ehundategh楼主2023/7/30 14:49

本地测样例是过的 下载数据也是对的 实在不知道怎么改了 不知道是不是读入的问题

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 300010
using namespace std;
const int INF=1<<30;
int Total=0,Root,Lazy=0,Tag=0,Now=0;
struct N{
   int Left,Right;
   int Value,Key;
   int Size;
}Node[MAXN];
int New(int Key){
   Total++;
   Node[Total].Left=Node[Total].Right=0;
   Node[Total].Key=Key;
   Node[Total].Value=rand();
   Node[Total].Size=1;
   return Total;
}
void Update(int Position){
   Node[Position].Size=Node[Node[Position].Left].Size+Node[Node[Position].Right].Size+1;
}
void Split(int Position,int Key,int &L,int &R){
   if(!Position){
   	L=R=0;
   	return;
   }
   if(Node[Position].Key<=Key){
   	L=Position;
   	Split(Node[Position].Right,Key,Node[Position].Right,R);
   }
   else{
   	R=Position;
   	Split(Node[Position].Left,Key,L,Node[Position].Left);
   }
   Update(Position);
}
int Merge(int L,int R){
   if(!L||!R) return L|R;
   if(Node[L].Value<=Node[R].Value){
   	Node[L].Right=Merge(Node[L].Right,R);
   	Update(L);
   	return L;
   }
   else{
   	Node[R].Left=Merge(L,Node[R].Left);
   	Update(R);
   	return R;
   }
}
int Get_Num(int Position,int Rank){
   if(Rank==Node[Node[Position].Left].Size+1) return Node[Position].Key;
   if(Node[Node[Position].Left].Size>=Rank){
   	return Get_Num(Node[Position].Left,Rank);
   }
   else{
   	return Get_Num(Node[Position].Right,Rank-Node[Node[Position].Left].Size-1);
   }
}
void Insert(int Key){
   int L,R,Now;
   Split(Root,Key-1,L,R);
   Now=New(Key);
   Root=Merge(Merge(L,Now),R);
}
void Delete(int Key){
   int L,R,Temp;
   Split(Root,Key,L,R);
   Split(L,Key-1,L,Temp);
   Temp=Merge(Node[Temp].Left,Node[Temp].Right);
   Root=Merge(Merge(L,Temp),R);
}

int main(){
   Root=0;
   Insert(INF);
   Insert(-INF);
   char Option;
   int n,In1,Min;
   scanf("%d%d",&n,&Min);
   for(int i=1;i<=n;i++){
       getchar();
       scanf("%c %d",&Option,&In1);
       if(Option=='I'){
           if(In1<Min) continue;
           else{Insert(In1-Lazy);Now++;}
       }
       if(Option=='A'){
           Lazy+=In1;
       }
       if(Option=='S'){
           Lazy-=In1;
           while(Get_Num(Root,2)+Lazy<Min){
               Delete(Get_Num(Root,2));
               Tag++;
               Now--;
           }
       }
       if(Option=='F'){
           if(Now>=In1) printf("%d\n",Get_Num(Root,Now-In1+2)+Lazy);
           else printf("-1\n");
       }
   }
   printf("%d",Tag);
   return 0;
}

2023/7/30 14:49
加载中...