P1486 [NOI2004] 郁闷的出纳员 · znzryb
## 思路讲解
需要注意是工资第k多，而不是第k少。
## AC代码
[https://www.luogu.com.cn/problem/P1486](https://www.luogu.com.cn/problem/P1486)
::: 源代码
```cpp
// Problem: P1486 [NOI2004] 郁闷的出纳员
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1486
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
#define uniVec(var) do { sort(var.begin(),var.end());var.resize(unique(var.begin(),var.end())-var.begin());} while (0)
#define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } std::cerr<<"\n"; }while(0)
#define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto& pair : variable) { std::cerr << " " << pair.first << " => " << pair.second << "\n"; } std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x)) // vec中大于x的数有几个
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,A[MAXN];
/*
*/
int lik=0;
namespace FHQ{
const int maxn=static_cast<int>(3e5)+10;
int size[maxn],key[maxn],ls[maxn],rs[maxn],pri[maxn];
int root=0,cnt=0;
mt19937 rng(23341);
inline void pushup(int node){
size[node]=size[ls[node]]+size[rs[node]]+1;
}
inline void makeN(int val){
++cnt;
size[cnt]=1;ls[cnt]=0;rs[cnt]=0;key[cnt]=val;pri[cnt]=rng();
}
void split(int node,int val,int &x,int &y){
if(!node) {x=0,y=0;return;}
if(val>=key[node]){ // node 及其左树被保留了
x=node;
split(rs[node],val,rs[node],y);
}else{
y=node;
split(ls[node],val,x,ls[node]);
}
pushup(node);
}
int merge(int x,int y){
if(!x || !y) return x+y;
if(pri[x]>=pri[y]){ // 大根堆
rs[x]=merge(rs[x],y);
pushup(x);
return x;
}else{
ls[y]=merge(x,ls[y]);
pushup(y);
return y;
}
}
inline void insert(int val){
int x,y;
split(root,val,x,y);
makeN(val);
root=merge(x,cnt);
root=merge(root,y);
}
inline void delUd(int val){ // 将小于等于工资val的全部删除
int x,y;
split(root,val,x,y);
root=y;
lik+=size[x];
}
int kth(int node,int rank){
if(!node) return -1;
if(size[ls[node]]>=rank){
return kth(ls[node],rank);
}else{
if(size[ls[node]]+1>=rank) return key[node];
else return kth(rs[node],rank-size[ls[node]]-1);
}
}
int kth(int rank){
if(rank>size[root]) return -1;
else return kth(root,size[root]-rank+1);
}
void Debug(int node){
if(!node) return;
debug(node);
debug(ls[node]);
debug(rs[node]);
debug(key[node]);
debug(size[node]);
Debug(ls[node]);
Debug(rs[node]);
}
void add(int node,int k){
if(!node) return;
key[node]+=k;
add(ls[node],k);
add(rs[node],k);
}
}
inline void solve(){
int mn=0;
scanf("%lld%d",&N,&mn);
namespace F=FHQ;
FOR(_,1,N){
char op;int k;
// 注意 " %c" 前面的空格，它会告诉 scanf 跳过所有空白字符（包括空格、制表符、换行符等）
scanf(" %c%d",&op,&k);
if(op=='I'){ // input
if(k>=mn){
F::insert(k);
// #ifdef LOCAL
// F::Debug(F::root);
// cerr<<"----------------\n";
// #endif
}
}else if(op=='S'){ // slide
F::add(F::root,-k);
// #ifdef LOCAL
// debug(mn-1);
// #endif
F::delUd(mn-1);
// #ifdef LOCAL
// F::Debug(F::root);
// cerr<<"----------------\n";
// #endif
}else if(op=='F'){ // kth
printf("%d\n",F::kth(k));
}else if(op=='A'){ // add
F::add(F::root,k);
}
}
printf("%d\n",lik);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
// scanf("%lld",&lT);
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
AC
https://www.luogu.com.cn/record/219083893
*/
```
:::
## 心路历程（WA，TLE，MLE……）