AT1183题解
Griseo_nya
2021-03-25 18:31:02
其实这道题可以用平衡树来过，但蒟蒻不太会写平衡树，于是想到了一种可以在某种程度上替代平衡树的方法——维护一个有序的数组。
下面介绍一下用到的 STL 函数：
`deque` : 同 `vector` ,可以理解为动态长度数组。下标从 $0$ 开始。
`lower_bound` : 在有序序列里找到大于等于所给项的第一个数，返回这个数的迭代器（可以理解为指针）。
`vec.erase(vec.begin()+i)` : 删除第 $i+1$ 个数。
`deque::insert()` : 在指定迭代器处添加给定的数。
然后关于代码的讲解就在代码注释里了。
还不懂可以看[这个](https://www.luogu.com.cn/blog/specialflag/solution-p3369)。
```cpp
#include<bits/stdc++.h>
using namespace std;
deque<int> qwq;
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int op,x;
scanf("%d%d",&op,&x);
switch(op){
case(1):
qwq.insert((lower_bound(qwq.begin(),qwq.end(),x)),x); //从 qwq 开头到结尾查询第一个大于等于 x 的数的位置，并把 x 插入到该位置（其余数后移）
break;
case(2):
printf("%d\n",qwq[x-1]); //输出第 x 小的数
qwq.erase(qwq.begin()+x-1); //删掉第x 小的数
break;
}
}
return 0;
}
```