```cpp
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <type_traits>
#include <random>
#define uint64_t unsigned long long
#if __cplusplus < 201703L
namespace std
{
template <typename _Tp>
constexpr bool is_integral_v = is_integral<_Tp>::value;
template <typename _Tp>
constexpr bool is_signed_v = is_signed<_Tp>::value;
}
#endif
inline namespace __my_detail
{
#define cin __my_detail::inputHelper<65536, 128>::getInstance()
#define getchar() ({char c = cin.getChar_Checked(); cin.next(); c; })
#define cout __my_detail::outputHelper<65536>::getInstance()
#define putchar cout.putChar
#define endl '\n'
#define putlog(...) __my_detail::printLog(", ", __VA_ARGS__)
template <uint64_t _BufferSize = 65536, uint64_t _BlockSize = 128>
class inputHelper
{
FILE *m_filePtr;
char m_buf[_BufferSize], *m_end, *m_cursor;
bool m_ok;
void flush()
{
uint64_t a = m_end - m_cursor;
if (a >= _BlockSize)
return;
memmove(m_buf, m_cursor, a);
uint64_t b = fread(m_buf + a, 1, _BufferSize - a, m_filePtr);
m_cursor = m_buf;
if (a + b < _BufferSize)
{
m_end = m_buf + a + b;
*m_end = EOF;
}
}
public:
explicit inputHelper(const char *inputFileName) : m_ok(true)
{
if (!*inputFileName)
m_filePtr = stdin;
else
m_filePtr = fopen(inputFileName, "rt");
m_end = m_cursor = m_buf + _BufferSize;
}
~inputHelper() { fclose(m_filePtr); }
static inputHelper<_BufferSize, _BlockSize> &getInstance()
{
#ifdef OY_LOCAL
static inputHelper<_BufferSize, _BlockSize> s_obj("in.txt");
#else
static inputHelper<_BufferSize, _BlockSize> s_obj("");
#endif
return s_obj;
}
static constexpr bool isBlank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
static constexpr bool isEndline(char c) { return c == '\n' || c == EOF; }
const char &getChar_Checked()
{
if (m_cursor < m_end)
return *m_cursor;
uint64_t b = fread(m_buf, 1, _BufferSize, m_filePtr);
m_cursor = m_buf;
if (b < _BufferSize)
{
m_end = m_buf + b;
*m_end = EOF;
}
return *m_cursor;
}
const char &getChar_Unchecked() const { return *m_cursor; }
void next() { ++m_cursor; }
void setState(bool _ok) { m_ok = _ok; }
template <typename _Tp, std::enable_if_t<std::is_signed_v<_Tp> & std::is_integral_v<_Tp>> * = nullptr>
inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret)
{
while (isBlank(getChar_Checked()))
next();
flush();
if (getChar_Unchecked() == '-')
{
next();
if (isdigit(getChar_Unchecked()))
{
ret = -(getChar_Unchecked() - '0');
while (next(), isdigit(getChar_Unchecked()))
ret = ret * 10 - (getChar_Unchecked() - '0');
}
else
m_ok = false;
}
else
{
if (isdigit(getChar_Unchecked()))
{
ret = getChar_Unchecked() - '0';
while (next(), isdigit(getChar_Unchecked()))
ret = ret * 10 + (getChar_Unchecked() - '0');
}
else
m_ok = false;
}
return *this;
}
explicit operator bool() { return m_ok; }
};
template <uint64_t _BufferSize = 65536>
class outputHelper
{
FILE *m_filePtr = nullptr;
char m_buf[_BufferSize], *m_end, *m_cursor;
char m_tempBuf[50], *m_tempBufCursor, *m_tempBufDot;
public:
outputHelper(const char *outputFileName) : m_end(m_buf + _BufferSize)
{
if (!*outputFileName)
m_filePtr = stdout;
else
m_filePtr = fopen(outputFileName, "wt");
m_cursor = m_buf;
m_tempBufCursor = m_tempBuf;
}
static outputHelper<_BufferSize> &getInstance()
{
#ifdef OY_LOCAL
static outputHelper<_BufferSize> s_obj("out.txt");
#else
static outputHelper<_BufferSize> s_obj("");
#endif
return s_obj;
}
~outputHelper()
{
flush();
fclose(m_filePtr);
}
outputHelper<_BufferSize> &flush()
{
fwrite(m_buf, 1, m_cursor - m_buf, m_filePtr);
fflush(m_filePtr);
m_cursor = m_buf;
return *this;
}
void putChar(const char &c)
{
if (m_cursor == m_end)
flush();
*m_cursor++ = c;
}
template <typename _Tp, std::enable_if_t<std::is_signed_v<_Tp> & std::is_integral_v<_Tp>> * = nullptr>
outputHelper<_BufferSize> &operator<<(const _Tp &ret)
{
_Tp _ret = _Tp(ret);
if (_ret >= 0)
{
do
{
*m_tempBufCursor++ = '0' + _ret % 10;
_ret /= 10;
} while (_ret);
do
putChar(*--m_tempBufCursor);
while (m_tempBufCursor > m_tempBuf);
}
else
{
putChar('-');
do
{
*m_tempBufCursor++ = '0' - _ret % 10;
_ret /= 10;
} while (_ret);
do
putChar(*--m_tempBufCursor);
while (m_tempBufCursor > m_tempBuf);
}
return *this;
}
outputHelper<_BufferSize> &operator<<(const char &ret)
{
putChar(ret);
return *this;
}
};
}
inline bool my_is_nullptr(void* ptr) {
return (long long)ptr >= 0x200000000ll || (long long)ptr <= 0ll;
}
template <typename _Tp, typename _UIntType>
class Node {
public:
size_t size;
_Tp value;
_UIntType priority;
Node *left, *right;
Node(size_t s = 0, const _Tp &v = _Tp(), const _UIntType &pro = _UIntType(), Node *l = nullptr, Node *r = nullptr)
: size(s), value(v), priority(pro), left(l), right(r) {}
~Node() = default;
Node<_Tp, _UIntType> &operator=(const Node<_Tp, _UIntType>& o) {
size = o.size;
value = o.value;
priority = o.priority;
left = o.left;
right = o.right;
return *this;
}
inline void update() {
size = 1;
if (!my_is_nullptr(left)) size += left->size;
if (!my_is_nullptr(right)) size += right->size;
}
};
template <typename _Tp, typename _UIntType>
inline void zig(Node<_Tp, _UIntType> *& cur) {
Node<_Tp, _UIntType> * tmp = cur->left;
cur->left = tmp->right;
tmp->right = cur;
tmp->update();
cur->update();
cur = tmp;
}
template <typename _Tp, typename _UIntType>
inline void zag(Node<_Tp, _UIntType> *& cur) {
Node<_Tp, _UIntType> * tmp = cur->right;
cur->right = tmp->left;
tmp->left = cur;
tmp->update();
cur->update();
cur = tmp;
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp = std::less<_Tp> >
class nrotate_treap {
typedef typename _Rand::result_type _UIntType;
Node<_Tp, _UIntType>* root;
_KeyOfValue _key_of_value;
_Comp comp;
_Rand rd;
static void split(Node<_Tp, _UIntType> * cur, _Tp v, Node<_Tp, _UIntType> *& l, Node<_Tp, _UIntType> *& r, _KeyOfValue key_of_value, _Comp comp);
static Node<_Tp, _UIntType> * merge(Node<_Tp, _UIntType> * l, Node<_Tp, _UIntType> * r);
public:
nrotate_treap() = default;
~nrotate_treap() = default;
inline void insert_unique(const _Tp& v);
inline void insert_equal(const _Tp& v);
inline void erase(const _Tp& v);
inline _Tp lower_bound(const _Tp& v);
inline _Tp upper_bound(const _Tp& v);
inline std::size_t Rank(const _Tp& v);
inline const _Tp operator[](std::size_t index) const;
inline std::pair<_Tp, _Tp> equal_range(const _Tp& v);
};
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
void nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
split(Node<_Tp, typename _Rand::result_type> * cur, _Tp v,
Node<_Tp, typename _Rand::result_type> *& l, Node<_Tp, typename _Rand::result_type> *& r,
_KeyOfValue key_of_value, _Comp comp) {
if (!cur) {
l = r = nullptr;
return;
}
if (comp(key_of_value(v), key_of_value(cur->value))) {
split(cur->left, v, l, cur->left, key_of_value, comp);
cur->update();
r = cur;
}
else {
split(cur->right, v, cur->right, r, key_of_value, comp);
cur->update();
l = cur;
}
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
Node<_Tp, typename _Rand::result_type> * nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
merge(Node<_Tp, typename _Rand::result_type> * l, Node<_Tp, typename _Rand::result_type> * r) {
if (!l) return r;
if (!r) return l;
if (l->priority < r->priority) {
l->right = merge(l->right, r);
l->update();
return l;
}
r->left = merge(l, r->left);
r->update();
return r;
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline void nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
insert_unique(const _Tp& v) {
Node<_Tp, typename _Rand::result_type> * l, * tmp, * r;
split(root, v, l, r);
split(l, v - 1, l, tmp);
if (my_is_nullptr(tmp)) {
tmp = new Node<_Tp, typename _Rand::result_type>(1, v, rd(), nullptr, nullptr);
}
root = merge(merge(l, tmp), r);
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline void nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
insert_equal(const _Tp& v) {
Node<_Tp, typename _Rand::result_type> * l, * tmp, * r;
split(root, v, l, r, _key_of_value, comp);
split(l, v - 1, l, tmp, _key_of_value, comp);
if (my_is_nullptr(tmp)) {
tmp = new Node<_Tp, typename _Rand::result_type>(1, v, rd(), nullptr, nullptr);
}
else {
++tmp->size;
}
root = merge(merge(l, tmp), r);
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline void nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
erase(const _Tp& v) {
Node<_Tp, typename _Rand::result_type> * l, * tmp, * r;
split(root, v, l, r, _key_of_value, comp);
split(l, v - 1, l, tmp, _key_of_value, comp);
if (my_is_nullptr(tmp)) {
root = merge(l, r);
return;
}
tmp = merge(tmp->left, tmp->right);
root = merge(merge(l, tmp), r);
return;
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline const _Tp nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
operator[](size_t index) const {
Node<_Tp, typename _Rand::result_type> * u = root;
while (!my_is_nullptr(u)) {
size_t left_siz = (my_is_nullptr(u->left) ? 0 : u->left->size) + 1;
if (left_siz == index) break;
if (left_siz < index) {
index -= left_siz;
if (my_is_nullptr(u->right)) return u->value;
u = u->right;
}
else {
if (my_is_nullptr(u->left)) return u->value;
u = u->left;
}
}
return my_is_nullptr(u) ? std::numeric_limits<_Tp>::max() : u->value;
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline size_t nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
Rank(const _Tp& v) {
Node<_Tp, typename _Rand::result_type> * x, * y;
split(root, v - 1, x, y, _key_of_value, comp);
size_t res = (my_is_nullptr(x) ? 0 : x->size) + 1;
root = merge(x, y);
return res;
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline _Tp nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
lower_bound(const _Tp& v) {
return this->operator[](Rank(v));
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline _Tp nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
upper_bound(const _Tp& v) {
return this->operator[](Rank(v) + 1);
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline std::pair<_Tp, _Tp> nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::
equal_range(const _Tp& v) {
return std::make_pair(lower_bound(v), upper_bound(v));
}
nrotate_treap<long long, std::mt19937, std::_Identity<long long>, std::less<long long> > tree;
long long arr[200005];
int main()
{
int cur = 1, n, m, val, pos = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 1; i <= m; i++)
{
cin >> val;
while (cur <= val) {
tree.insert_equal(arr[cur]);
++cur;
}
++pos;
cout << tree[pos] << endl;
}
}
```
by Ruiqun2009 @ 2022-10-31 11:32:45
并且好像有内存泄漏
by Ruiqun2009 @ 2022-10-31 11:35:57
84分了！[record](https://www.luogu.com.cn/record/92319044)
by Ruiqun2009 @ 2022-10-31 11:44:13
我不知道为什么 WA 的地方和随机数生成器有关系。
例如第二个点，使用我手写的 `mt19937` 就会[在 $\color{#E74C3C}11544$ 行 WA](https://www.luogu.com.cn/record/92321103)，但是使用我手写的 `xor32` 就会在[在 $\color{#E74C3C}24834$ 行 WA](https://www.luogu.com.cn/record/92321418)。
谁能告诉我这是为什么吗？
by Ruiqun2009 @ 2022-10-31 12:31:04
[拿了一个没法通过模板题的 FHQ-Treap 通过了](https://www.luogu.com.cn/record/92325600)
**此贴终结**
by Ruiqun2009 @ 2022-10-31 13:14:10