大佬們幫幫這個蒟蒻啊QAQ
by zhoukangyang @ 2020-06-25 11:30:00
神仙帮帮我(逃 @[Froggy](/user/100285)
by zhoukangyang @ 2020-06-25 12:54:09
还是挂/kk
```
#include<bits/stdc++.h>
#define N 210000
using namespace std;
int n,root;
struct node{
int key,siz,val,minn,lazy,son[2];
} q[N];
int new_root(int id,int val) {
q[id].key = rand() , q[id].siz = 1 , q[id].minn = q[id].val = val;
return id;
}
void upd(int now) {
q[now].minn = min(q[now].val,min(q[q[now].son[0]].minn,q[q[now].son[1]].minn));
q[now].siz = q[q[now].son[0]].siz+q[q[now].son[1]].siz+1;
}
void flip(int now) {
q[now].lazy^=1;
swap(q[now].son[0],q[now].son[1]);
}
void pushdown(int now) {
if(!q[now].lazy) return;
if(q[now].son[0]) flip(q[now].son[0]);
if(q[now].son[1]) flip(q[now].son[1]);
q[now].lazy = 0;
}
void split(int now,int &x,int &y){
if(!now) x=y=0;
else {
pushdown(now);
if(q[now].minn == q[now].val)
x=now,y=q[now].son[1],q[now].son[1]=0;
else if(q[now].minn == q[q[now].son[0]].minn)
y=now,split(q[now].son[0],x,q[y].son[0]);
else
x=now,split(q[now].son[1],q[x].son[1],y);
upd(now);
}
}
int merge(int x,int y) {
if(!x||!y) return x+y;
else {
if(q[x].key>q[y].key) {
pushdown(x),q[x].son[1]=merge(q[x].son[1],y),upd(x);
return x;
}
else {
pushdown(y),q[y].son[0]=merge(x,q[y].son[0]),upd(y);
return y;
}
}
}
int main() {
int x;
srand('F'+'R'+'O'+'G'+'G'+'Y'+'A'+'K'+'I'+'O'+'I');
q[0].minn=1e9;
scanf("%d",&n);
for(int i = 1; i <= n; i++) {
scanf("%d",&x);
root=merge(root,new_root(i,x));
}
for(int i = 1; i <= n; i++) {
int splx,sply,splz;
split(root,splx,sply);
printf("%d ",q[splx].siz+i-1);
flip(splx);
split(splx,splz,splx);
root=merge(splx,sply);
}
return 0;
}
```
by zhoukangyang @ 2020-06-25 17:58:20
zhoukangyang
by peterwuyihong @ 2021-09-25 21:25:15