P1486 [NOI2004] 郁闷的出纳员

思路讲解

需要注意是工资第k多，而不是第k少。

AC代码

https://www.luogu.com.cn/problem/P1486

源代码

// 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……）