那个MLE有点像爆栈
by Register @ 2020-03-31 09:43:27
估计split还是merge有锅，就死循环了？？？
by Register @ 2020-03-31 09:45:15
把```split(c[x][0],k,x,c[y][0]);```改成了```split(c[y][0],k,x,c[y][0])```，还是有锅
https://www.luogu.com.cn/record/32332267
by Register @ 2020-03-31 09:50:08
草，我发现这个东西是随机炸的，运气好不会有锅
by Register @ 2020-03-31 09:59:06
主席树赛高！
虽然我没试过，但说不定~~colazcy帮我~~卡卡常就过了
by zmx_wzx_JY @ 2020-03-31 09:59:26
我写的是结构体FHQ Treap，借鉴一下？
by twelveZ @ 2020-03-31 10:00:46
略臭
```cpp
#include<cstdio>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
int n;
int cnt;
int x,y,z;
int seed=54250;
const int INF=2147483647;
struct tree{
int l,r;
int val;
int key;
int rank;
int size;
}fhq[25000005];
int rt[25000005];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0'; ch=getchar();
}
return x*f;
}
inline void print(int x){
if(x<0){
putchar('-'); x=-x;
}
if(x>9)
print(x/10);
putchar(x%10+'0');
}
inline int rand() {
return seed=int(seed*114514ll%19260817);
}
inline void update(int now){
fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
inline int new_node(int val){
fhq[++cnt].val=val;
fhq[cnt].key=rand();
fhq[cnt].size=1;
return cnt;
}
inline void split(int now,int val,int &x,int &y){
if(!now) x=y=0;
else{
if(fhq[now].val<=val){
fhq[x=++cnt]=fhq[now];
split(fhq[now].r,val,fhq[x].r,y);
update(x);
}
else{
fhq[y=++cnt]=fhq[now];
split(fhq[now].l,val,x,fhq[y].l);
update(y);
}
update(now);
}
}
inline int merge(int x,int y){
if(!x||!y) return x+y;
if(fhq[x].key<fhq[y].key){
int q=++cnt;
fhq[q]=fhq[x];
fhq[q].r=merge(fhq[q].r,y);
update(q);
return q;
}
else{
int q=++cnt;
fhq[q]=fhq[y];
fhq[q].l=merge(x,fhq[q].l);
update(q);
return q;
}
}
inline int get_rank(int now,int k){
while(19260817) {
if(k==fhq[fhq[now].l].size+1) return now;
if(k<=fhq[fhq[now].l].size) now=fhq[now].l;
else k-=fhq[fhq[now].l].size+1,now=fhq[now].r;
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
int tm,opt,a;
tm=read();
opt=read();
a=read();
rt[i]=rt[tm];
if(opt==1){
split(rt[i],a,x,y);
rt[i]=merge(merge(x,new_node(a)),y);
}
else
if(opt==2){
split(rt[i],a,x,z);
split(x,a-1,x,y);
y=merge(fhq[y].l,fhq[y].r);
rt[i]=merge(merge(x,y),z);
}
else
if(opt==3){
split(rt[i],a-1,x,y);
printf("%d\n",fhq[x].size+1);
rt[i]=merge(x,y);
}
else
if(opt==4)
printf("%d\n",fhq[get_rank(rt[i],a)].val);
else
if(opt==5){
split(rt[i],a-1,x,y);
if(fhq[x].size) {
printf("%d\n",fhq[get_rank(x,fhq[x].size)].val);
rt[i]=merge(x,y);
}
else printf("%d\n",-INF);
}
else
if(opt==6){
split(rt[i],a,x,y);
if(fhq[y].size) {
printf("%d\n",fhq[get_rank(y,1)].val);
rt[i]=merge(x,y);
}
else printf("%d\n",INF);
}
}
}
```
by twelveZ @ 2020-03-31 10:02:49
调不出来，zbl
by Register @ 2020-03-31 10:03:52
@[zmx_wzx_JY](/user/86579) 虽然是能用主席树，不过FHQ Treap显然要好写一点
by Register @ 2020-03-31 10:06:03
极限压行
by Yukinoshita_Yukino @ 2020-03-31 10:06:31