直接multiset码量不到0.5k不香吗
by lndjy @ 2020-08-12 10:40:16
掩盖不了`vector`可过的事实（
by yummy @ 2020-08-12 10:40:54
写个堆他不好吗
by RainsAFO @ 2020-08-12 10:41:27
写个堆他不好吗
by JRzyh @ 2020-08-12 10:43:06
怎么用 可持久化动态仙人掌 做这题啊
by Qiuly @ 2020-08-12 10:44:38
这不都用对顶堆做？/xyx
by 白鲟 @ 2020-08-12 10:45:26
我卡的吧
https://www.luogu.com.cn/discuss/show/202137
by critnos @ 2020-08-12 10:47:26
@[yummy](/user/101694) 我也卡了 vector/xyx
by critnos @ 2020-08-12 10:47:43
优先队列它不香吗
by Eason_AC @ 2020-08-12 10:48:27
@[mcyl35](/user/203623) 草草草....../kk/kk
顺便我刚写的 Splay 好像挂掉了，能帮忙看看嘛/kel
```cpp
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cctype>
#define MAXN 200005
#define int long long
using namespace std;
struct Node{
int ch[2],val,size,num,father;
Node(int l,int r,int v,int s,int n,int f){
ch[0]=l,ch[1]=r,val=v,size=s,num=n,father=f;
}
Node(){}
};
int rt,cnt;
int a[MAXN],u[MAXN];
struct Splay{
Node t[MAXN];
inline void pushup(int o){
t[o].size=t[t[o].ch[0]].size+t[t[o].ch[1]].size+t[o].num;
}
inline void clear(int o){
t[o]=Node(0,0,0,0,0,0);
}
inline bool get(int o){
return o==t[t[o].father].ch[1];
}
inline void rotate(int o){
int x=t[o].father,y=t[x].father;
int r=get(o);
t[x].ch[r]=t[o].ch[r^1];
t[t[o].ch[r^1]].father=x;
t[o].ch[r^1]=x;
t[x].father=o;
t[o].father=y;
if(y)t[y].ch[x==t[y].ch[1]]=o;
pushup(o);
pushup(x);
}
inline void splay(int o){
for(int f=t[o].father;f=t[o].father,f;rotate(o)){
if(t[f].father)rotate(get(o)==get(f)?f:o);
}
rt=o;
}
inline void insert(int x){
if(!rt){
t[rt=++cnt].val=x;
t[cnt].num++;
pushup(rt);
return ;
}
int cur=rt,f=0;
while(1){
if(t[cur].val==x){
t[cur].num++;
pushup(cur);
pushup(f);
splay(cur);
break;
}
f=cur;
cur=t[cur].ch[t[cur].val<x];
if(!cur){
t[rt=++cnt].val=x;
t[cnt].num++;
t[cnt].father=f;
t[f].ch[t[f].val<x]=cnt;
pushup(cnt);
pushup(f);
splay(cnt);
break;
}
}
}
inline int kth(int x){
int cur=rt;
while(1){
if(t[cur].ch[0]&&x<=t[t[cur].ch[0]].size){
cur=t[cur].ch[0];
}
else{
x-=t[t[cur].ch[0]].size+t[cur].num;
if(x<=0){
splay(cur);
return t[cur].val;
}
cur=t[cur].ch[1];
}
}
}
};
Splay tree;
signed main(void){
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%lld",&u[i]);
}
int now=1,tmp=0;
for(int i=1;i<=m;i++){
tree.insert(a[i]);
while(u[now]==i){
now++;
tmp++;
printf("%lld\n",tree.kth(tmp));
}
}
return 0;
}
```
by 云浅知处 @ 2020-08-12 10:48:41