正解：$Treap/Splay/$各种$BST$
而且是裸题……
但是……
颓废蒟蒻如我连裸题都懒得不会打$qwq$
但是这道题有一个十分弱智妙的特点：每次更改工资下界是针对全员更改的，而非指定范围。
而$stl$中的$vector$容器可以利用内存块的移动实现$O(1)$在任意位置插入元素……
然后就可以使用$lower$_$bound$水$A$掉这道题啦$qwq$
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 vector<int> vec; 7 8 inline int read() { 9 int res = 0, flag = 1; 10 char c = getchar(); 11 for(; !isdigit(c); c = getchar()) if(c == ‘-‘) flag = -1; 12 for(; isdigit(c); c = getchar()) res = (res<<3) + (res<<1) + (c^48); 13 return res * flag; 14 } 15 16 int main() { 17 int n = read(), least = read(), ans = 0; 18 for(int i = 1; i <= n; i++) { 19 char opt = getchar(); 20 int k = read(); 21 if(opt == ‘I‘) { 22 if(k < least) continue; 23 vec.insert(lower_bound(vec.begin(), vec.end(), k), k); 24 } 25 else if(opt == ‘A‘) for(int i = 0; i < vec.size(); i++) vec[i] += k; 26 else if(opt == ‘S‘) { 27 int size = vec.size(); 28 for(int i = 0; i < size; i++) { 29 vec[i] -= k; 30 if(vec[i] < least) 31 vec.erase(lower_bound(vec.begin(), vec.end(), vec[i])), ans++, size--, i--; 32 } 33 } 34 else { 35 if(k > vec.size()) printf("-1\n"); 36 else printf("%d\n", vec[vec.size() - k]); 37 } 38 } 39 printf("%d\n", ans); 40 return 0; 41 }
原文：https://www.cnblogs.com/Zenurik/p/9931977.html