您是猛新吧，我比较菜，不过您可以参考一下我的Splay代码
```cpp
//this cochu is written by dd，please do not copy.
//被迫卡时间的方法
//(double)clock() / CLOCKS_PER_SEC <= 0.95
#include<bits/stdc++.h>
using namespace std;
#define MAX 0x7fffffff
#define RG register
const int mod = 1e9 + 7;
typedef long long ll;
//-----------------------------------------------------------------------------------------------------------------------
const int inf=6*200100;
int tot,Root;
int son[inf][2];// 0->left 1->right
int val[inf];// 节点的值
int cnt[inf];//有多少个这个值
int size[inf];// 所在子树元素个数
int fa[inf];// 父亲节点下标
inline bool Dir(int x){ return son[fa[x]][1]==x; }
inline void pushup(int x){ size[x]=size[son[x][0]]+size[son[x][1]]+cnt[x]; }
inline void rotate(int x){//旋转
int y=fa[x],z=fa[y],k=Dir(x),w=son[x][k^1];
son[y][k]=w; fa[w]=y;
son[z][Dir(y)]=x; fa[x]=z;
son[x][k^1]=y; fa[y]=x;
pushup(y);pushup(x);
}
inline void splay(int x,int goal=0){//没有填写伸展目标是默认为根节点
while (fa[x]!=goal){
int y=fa[x],z=fa[y];
if (z!=goal) {
if(Dir(x)==Dir(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if(!goal) Root=x;//当前节点伸展目标为根，更新根节点位置
}
void find(int x){//寻找x并将他伸展至根，如果x不存在，就会找到当前数的前驱或后继
int cur=Root;
while(son[cur][x>val[cur]]&&val[cur]!=x)
cur=son[cur][x>val[cur]];
splay(cur);
}
inline void Insert(int x){//插入
int cur=Root,p=0;
while(cur&&val[cur]!=x)
{
p=cur;
cur=son[cur][x>val[cur]];
}
if(cur) cnt[cur]++;
else {
cur=++tot;
if(p) son[p][x>val[p]]=cur;
son[cur][0]=son[cur][1]=0;
val[cur]=x;fa[cur]=p;
cnt[cur]=size[cur]=1;
}
splay(cur);
}
inline int Last(int x)//求前驱 (前驱定义为小于x，且最大的数)
{
find(x);
if(val[Root]<x) return Root;//x不存在，根就可能为前驱/后驱
int cur=son[Root][0];
while(son[cur][1]) cur=son[cur][1];
splay(cur);
return cur;
}
inline int Next(int x)//求后驱 (后继定义为大于x，且最小的数)
{
find(x);
if(val[Root]>x) return Root;
int cur=son[Root][1];
while(son[cur][0]) cur=son[cur][0];
splay(cur);
return cur;
}
void Delete(int x){
int L=Last(x),R=Next(x);
splay(L);splay(R,L);
int del=son[R][0];
if(cnt[del]>1) { cnt[del]--;splay(del);}
else son[R][0]=0;
pushup(R);pushup(Root);
}
int Kth(int k){
int cur=Root;
while(1){
if(k<=size[son[cur][0]]&&son[cur][0])
cur=son[cur][0];
else
if(k>size[son[cur][0]]+cnt[cur]){
k-=size[son[cur][0]]+cnt[cur];
cur=son[cur][1];
}
else{
splay(cur);
return cur;
}
}
}
int GetRank(int x)
{
find(x);
if(val[Root]<x) return size[son[Root][0]]+cnt[Root];
else return size[son[Root][0]];
}
int m,n,a[(int)2e5+5],u[(int)2e5+5];
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
scanf("%d",&u[i]);
int k=1,j=1;
for(int i=1;i<=m;++i)
{
Insert(a[i]);
while(u[j]==i)
{
++j;
printf("%d\n",val[Kth(k)]);
++k;
}
}
return 0;
}
by anonymous_letter @ 2022-03-23 20:40:01
借楼问一下：92分，已经是楼上的主程序了，请问该如何通过
```cpp
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <type_traits>
#include <random>
#define uint64_t unsigned
#define size_t int
#line 1 "read\\read.h"
#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;
}
};
}
#line 5 "random\\random.h"
template <class _UIntType,
size_t w, size_t n,
size_t m, size_t r,
_UIntType a, size_t u,
_UIntType d, size_t s,
_UIntType b, size_t t,
_UIntType c, size_t l, _UIntType f>
class my_mersenne_twister_engine
{
_UIntType MT[n];
size_t index = 0;
static_assert(std::is_unsigned<_UIntType>::value, "template argument "
"subsituting _UIntType not an unsigned integral type");
static_assert(1u <= m && m <= n,
"template arguments subsituting m out of bounds");
static_assert(r <= w, "template argument subsituting r out of bound");
static_assert(u <= w, "template argument subsituting u out of bound");
static_assert(s <= w, "template argument subsituting s out of bound");
static_assert(t <= w, "template argument subsituting t out of bound");
static_assert(l <= w, "template argument subsituting l out of bound");
static_assert(w <= std::numeric_limits<_UIntType>::digits,
"template argument subsituting w out of bound");
static_assert(a <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting a out of bound");
static_assert(d <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting d out of bound");
static_assert(b <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting b out of bound");
static_assert(c <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting c out of bound");
static_assert(d <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting d out of bound");
static_assert(f <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting f out of bound");
static inline constexpr size_t min() noexcept
{
return std::numeric_limits<_UIntType>::min();
}
static inline constexpr size_t max() noexcept
{
return std::numeric_limits<_UIntType>::max();
}
public:
static constexpr size_t word_size = w;
static constexpr size_t state_size = n;
static constexpr size_t shift_size = m;
static constexpr size_t mask_bits = r;
static constexpr _UIntType xor_mask = a;
static constexpr size_t tempering_u = u;
static constexpr _UIntType tempering_d = d;
static constexpr size_t tempering_s = s;
static constexpr _UIntType tempering_b = b;
static constexpr size_t tempering_t = t;
static constexpr _UIntType tempering_c = c;
static constexpr size_t tempering_l = l;
static constexpr _UIntType initialization_multiplier = f;
static constexpr _UIntType default_seed = (_UIntType)5489u;
public:
typedef _UIntType result_type;
explicit inline my_mersenne_twister_engine(result_type sd = default_seed)
{
seed(sd);
}
inline my_mersenne_twister_engine(const my_mersenne_twister_engine<_UIntType,
w, n, m, r, a, u, d, s, b, t, c, l, f> &mt) : index(mt.index)
{
std::memcpy(MT, mt.MT, sizeof(mt.MT));
}
public:
inline constexpr void seed(_UIntType seed)
{
MT[0] = seed;
index = 0;
for (size_t i = 1; i < n; i++)
{
_UIntType tt = f * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i;
MT[i] = tt & d;
}
}
template <class _Sseq, class = typename std::enable_if<std::is_class<_Sseq>::value>::type>
inline constexpr void seed(_Sseq &seq)
{
const _UIntType UMask = (~_UIntType()) << r;
const size_t k = (w + 31) >> 5;
unsigned int *arr = new unsigned int[n * k];
seq.generate(arr, arr + n * k);
bool zero = true;
for (size_t i = 0; i < n; i++)
{
_UIntType factor = 1u;
_UIntType sum = 0u;
for (size_t j = 0; j < k; j++)
{
sum += arr[k * i + j] * factor;
factor *= std::__detail::_Shift<_UIntType, 32>::value;
}
MT[i] = std::__detail::__mod<_UIntType,
std::__detail::_Shift<_UIntType, w>::__value>(sum);
if (zero)
{
if (!i)
{
if (MT[0] & UMask)
{
zero = false;
}
}
else if (MT[i])
{
zero = false;
}
}
}
if (zero)
{
MT[0] = std::__detail::_Shift<_UIntType, w - 1>::value;
}
}
private:
inline constexpr void gen()
{
for (size_t i = 0; i < n; i++)
{
_UIntType y = (MT[i] & 0x80000000) + (MT[(i + 1) % n] & 0x7fffffff);
MT[i] = MT[(i + m) % n] ^ (y >> 1);
(y & 1) && (MT[i] ^= a);
}
}
public:
inline constexpr _UIntType operator()()
{
(!index) && (gen(), true);
_UIntType y = MT[index];
y ^= y >> u;
y ^= ((y << s) & b);
y ^= ((y << t) & c);
y ^= y >> l;
index++;
(index == n) && (index = 0);
return y;
}
inline constexpr void discard(unsigned long long z)
{
for (unsigned long long x = 0; x < z; x++)
{
(!index) && (gen(), true);
index++;
(index == n) && (index = 0);
}
}
};
typedef my_mersenne_twister_engine<std::uint_fast32_t, 32, 624, 397, 31,
2567483615, 11,
4294967295, 7,
2636928640, 15,
4022730752, 18, 1812433253>
my_mt19937;
typedef my_mersenne_twister_engine<std::uint_fast64_t, 64, 312, 156, 31,
13043109905998158313ULL, 29,
6148914691236517205ULL, 17,
8202884508482404352ULL, 37,
18444473444759240704ULL, 43, 6364136223846793005ull>
my_mt19937_64;
typedef my_mersenne_twister_engine<std::uint_fast32_t, 32, 1018209, 647951, 31,
2911395111, 13,
3194869609, 11,
1332494548, 21,
3979777640, 25, 3434100851>
my_mt32582657;
typedef my_mersenne_twister_engine<std::uint_fast64_t, 64, 509103, 254611, 31,
13043109905998158313ULL, 29,
6148914691236517205ULL, 17,
8202884508482404352ULL, 37,
18444473444759240704ULL, 43, 12058422346942301925ull>
my_mt32582657_64;
template <class _UIntType,
_UIntType a, size_t u,
_UIntType d, size_t s,
_UIntType b, size_t t,
_UIntType c, size_t l, _UIntType f>
class my_xor_engine
{
_UIntType seed;
static constexpr _UIntType w = std::numeric_limits<_UIntType>::digits;
static_assert(std::is_unsigned<_UIntType>::value, "template argument "
"subsituting _UIntType not an unsigned integral type");
static_assert(u <= w, "template argument subsituting u out of bound");
static_assert(s <= w, "template argument subsituting s out of bound");
static_assert(t <= w, "template argument subsituting t out of bound");
static_assert(l <= w, "template argument subsituting l out of bound");
static_assert(a <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting a out of bound");
static_assert(d <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting d out of bound");
static_assert(b <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting b out of bound");
static_assert(c <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting c out of bound");
static_assert(f <= (std::__detail::_Shift<_UIntType, w>::__value - 1),
"template argument subsituting f out of bound");
public:
typedef _UIntType result_type;
my_xor_engine(_UIntType sd = (_UIntType)5489u) : seed(sd) {}
_UIntType operator()()
{
seed ^= seed >> u & a;
seed ^= seed << s & b;
seed ^= seed << t & c;
seed ^= seed >> l & d;
seed ^= f;
return seed;
}
};
typedef my_xor_engine<std::uint_fast64_t,
13043109905998158313ULL, 29,
6148914691236517205ULL, 17,
8202884508482404352ULL, 37,
18444473444759240704ULL, 43, 6364136223846793005ull>
my_xor64;
typedef my_xor_engine<std::uint_fast32_t,
2567483615, 11,
4294967295, 7,
2636928640, 15,
4022730752, 18, 1812433253>
my_xor32;
#line 1 "tree\\node_base.h"
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;
size_t cnt;
_UIntType priority;
Node *left, *right;
Node(size_t s = 0, const _Tp &v = _Tp(), size_t c = 0, const _UIntType &pro = _UIntType(), Node *l = nullptr, Node *r = nullptr)
: size(s), value(v), cnt(c), 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;
cnt = o.cnt;
return *this;
}
inline void update()
{
size = cnt;
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;
}
#line 1 "tree\\nrotate_treap.h"
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;
std::greater<_UIntType> priority_comp;
_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);
template <typename _Priority_comp>
static Node<_Tp, _UIntType> *merge(Node<_Tp, _UIntType> *l, Node<_Tp, _UIntType> *r, _Priority_comp comp);
public:
nrotate_treap() = default;
~nrotate_treap() = default;
inline bool 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 size_t Rank(const _Tp &v);
inline const _Tp operator[](size_t index) const;
inline std::pair<_Tp, _Tp> equal_range(const _Tp &v);
};
#line 1 "tree\\nrotate_treap.tcc"
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>
template <typename _Priority_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, _Priority_comp comp)
{
if (!l)
return r;
if (!r)
return l;
if (comp(l->priority, r->priority))
{
l->right = merge(l->right, r, comp);
l->update();
return l;
}
r->left = merge(l, r->left, comp);
r->update();
return r;
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline bool 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, 1, rd(), nullptr, nullptr);
}
else
{
root = merge(merge(l, tmp, priority_comp), r, priority_comp);
return false;
}
root = merge(merge(l, tmp, priority_comp), r, priority_comp);
return true;
}
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, 1, rd(), nullptr, nullptr);
}
else
{
++tmp->cnt;
++tmp->size;
}
root = merge(merge(l, tmp, priority_comp), r, priority_comp);
}
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, priority_comp);
root = merge(merge(l, tmp, priority_comp), r, priority_comp);
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) + u->cnt;
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 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) + x->cnt;
root = merge(x, y, priority_comp);
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));
}
#line 2 "P1801\\main.cpp"
nrotate_treap<int, my_xor32, std::_Identity<int>, std::less<int>> tree;
int m, n, a[200005], u[200005];
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> u[i];
int k = 1, j = 1;
for (int i = 1; i <= m; ++i)
{
tree.insert_equal(a[i]);
while (u[j] == i)
{
++j;
cout << tree[k] << endl;
++k;
}
}
return 0;
}
```
by Ruiqun2009 @ 2022-10-31 12:47:53