Splay要支持找最左侧的最小值所在的位置。类似线段树一样处理一下，如果左子树最小值等于全局最小值，就查左子树；否则如果当前节点等于全局最小值，就查当前节点；否则查右子树。
为了统计答案，当然还得维护子树大小的函数。
找到位置以后，直接将左右子树交换即可。不需要打标记。
删除节点时，直接将其前驱（是指序列下标的前驱，就是将待删除节点Splay到根后，左子树的最右节点）Splay到根，将其后继（类似）Splay到根的儿子。
然后将后继的左儿子删除即可。
别忘了及时Maintain();
这份代码的Maintain()时机都很合理，以后不要怀疑了。
但是如果插入是单调的，我这个代码好像有点问题……被卡掉了。于是我就在插入的过程中加入了随机Splay结点到根的操作。就过了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define maxn 100010
#define INF 2147483647
int fa[maxn],val[maxn],c[maxn][2],root,tot,siz[maxn],cnt[maxn],val2[maxn];
int minv[maxn];
void Maintain(int x)
{
siz[x]=siz[c[x][0]]+siz[c[x][1]]+cnt[x];
minv[x]=val2[x];
if(c[x][0]){
minv[x]=min(minv[x],minv[c[x][0]]);
}
if(c[x][1]){
minv[x]=min(minv[x],minv[c[x][1]]);
}
}
int Findminp(int x=root){
while(1){
if(c[x][0] && minv[c[x][0]]==minv[root]){
x=c[x][0];
}
else if(val2[x]==minv[root]){
return x;
}
else{
x=c[x][1];
}
}
}
void NewNode(int &x,int Fa,int key,int key2)
{
x=++tot;
fa[x]=Fa;
c[x][0]=c[x][1]=0;
val[x]=key;
val2[x]=minv[x]=key2;
siz[x]=cnt[x]=1;
}
void Rotate(int x,bool flag)
{
int y=fa[x];
// pushdown(y);
// pushdown(x);
c[y][!flag]=c[x][flag];
fa[c[x][flag]]=y;
if(fa[y]){
c[fa[y]][c[fa[y]][1]==y]=x;
}
fa[x]=fa[y];
c[x][flag]=y;
fa[y]=x;
Maintain(y);
Maintain(x);
}
void Splay(int x,int goal)
{
if(!x || x==goal){
return;
}
// pushdown(x);
int y;
while((y=fa[x])!=goal){
if(fa[y]==goal){
Rotate(x,c[y][0]==x);
}
else{
if((c[y][0]==x)==(c[fa[y]][0]==y)){
Rotate(y,c[fa[y]][0]==y);
}
else{
Rotate(x,c[y][0]==x);
y=fa[x];
}
Rotate(x,c[y][0]==x);
}
}
Maintain(x);
if(!goal){
root=x;
}
}
int Find(int key,int x=root)
{
while(c[x][val[x]<key]){
if(val[x]==key){
return x;
}
x=c[x][val[x]<key];
}
return x;
}
void Insert(int key,int key2)
{
if(!root){
NewNode(root,0,key,key2);
return;
}
int x=Find(key);
if(val[x]==key){
++cnt[x];
Splay(x,0);
return;
}
NewNode(c[x][val[x]<key],x,key,key2);
Splay(c[x][val[x]<key],0);
}
int Findmax(int x=root)
{
while(c[x][1]){
x=c[x][1];
}
return x;
}
int Findmin(int x=root)
{
while(c[x][0]){
x=c[x][0];
}
return x;
}
//int GetPre(int x)
//{
// Splay(x,0);
// return Findmax(c[x][0]);
//}
//int GetNex(int x){
// Splay(x,0);
// return Findmin(c[x][1]);
//}
int n,m;
typedef long long ll;
ll ans;
int main(){
scanf("%d",&n);
int x;
srand(233);
for(int i=1;i<=n;++i){
scanf("%d",&x);
Insert(i,x);
Splay(rand()%i+1,0);
}
for(int i=1;i<=n;++i){
int p=Findminp();
Splay(p,0);
ans+=(ll)(siz[c[p][0]]+1);
swap(c[p][0],c[p][1]);
int pPre=Findmax(c[p][0]);
int pNex=Findmin(c[p][1]);
if(!pPre && pNex){
root=c[p][1];
fa[root]=0;
}
else if(pPre && !pNex){
root=c[p][0];
fa[root]=0;
}
else if(pPre && pNex){
Splay(pPre,0);
Splay(pNex,pPre);
c[pNex][0]=0;
Maintain(pNex);
Maintain(pPre);
}
}
printf("%I64d
",ans);
return 0;
}