1 #include<bits/stdc++.h>
 2 #define RT(l,r) (l+r|l!=r)
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 using namespace std;
 5 
 6 const int N=1e6+7;
 7 int n,now,f[N],cnt,x,sum[N*2];
 8 struct node
 9 {
10     int x,idx;
11     bool operator <(const node &b)const{return x!=b.x?x<b.x:idx<b.idx;}
12 };
13 set<node>st;
14 set<node>::iterator it;
15 
16 int find(int x){return f[x]!=x?f[x]=find(f[x]):x;}
17 
18 int getnxt()
19 {
20     int X=st.begin()->x;
21     it=st.lower_bound({X,now});
22     if(it==st.end()||it->x > X)
23         it=st.lower_bound({X,1});
24     int tmp=it->idx;
25     st.erase(it);
26     return tmp;
27 }
28 
29 void update(int pos,int v,int l=1,int r=n)
30 {
31     int rt=RT(l,r),m=l+r>>1;
32     if(l==r){sum[rt]+=v;return;}
33     if(pos<=m)update(pos,v,l,m);
34     else update(pos,v,m+1,r);
35     sum[rt]=sum[RT(l,m)]+sum[RT(m+1,r)];
36 }
37 
38 int query(int L,int R,int l=1,int r=n)
39 {
40     int rt=RT(l,r),m=l+r>>1,an=0;
41     if(L<=l&&r<=R)return sum[rt];
42     if(L<=m)an+=query(L,R,l,m);
43     if(R>m)an+=query(L,R,m+1,r);
44     return an;
45 }
46 
47 
48 int ask(int a,int b)
49 {
50     if(a<=b)return query(a,b);
51     else return query(a,n)+query(1,b);
52 }
53 
54 int main()
55 {
56     scanf("%d",&n);
57     F(i,1,n)
58     {
59         scanf("%d",&x),f[i]=i;
60         st.insert({x,i}),update(i,1);
61     }
62     now=1,cnt=1;
63     long long ans=0;
64     while(cnt<=n)
65     {
66         int nxt=getnxt();
67         ans+=ask(now,nxt);
68         if(nxt<n)f[nxt]=nxt+1;else f[nxt]=1;
69         if(cnt<n)now=find(nxt);
70         update(nxt,-1);
71         cnt++;
72     }
73     printf("%lld\n",ans);
74     return 0;
75 }

  1 #include<bits/stdc++.h>
  2 #define F(i,a,b) for(int i=a;i<=b;++i)
  3 using namespace std;
  4 const int N=1e6+7;
  5 int _t;
  6 struct Splay_tree
  7 {
  8     int root,q[N];
  9     int key[N],sz[N],f[N],ch[N][2],add[N];
 10     void init(){root=_t=0;}//初始化为一棵空树
 11     inline void nw(int &x,int val,int fa)
 12     {
 13         x=++_t,key[x]=val,f[x]=fa,sz[x]=1;
 14         ch[x][0]=ch[x][1]=0;
 15     }
 16     inline void pd(int x){}
 17     inline void up(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}
 18     void rotate(int x){
 19         int y=f[x],w=ch[y][1]==x;
 20         ch[y][w]=ch[x][w^1];
 21         if(ch[x][w^1])f[ch[x][w^1]]=y;
 22         if(f[y]){
 23             int z=f[y];
 24             if(ch[z][0]==y)ch[z][0]=x;
 25             if(ch[z][1]==y)ch[z][1]=x;
 26         }
 27         f[x]=f[y],ch[x][w^1]=y,f[y]=x,up(y);
 28     }
 29 
 30     void splay(int x,int w){
 31         int s=1,i=x,y;q[1]=x;
 32         while(f[i])q[++s]=i=f[i];
 33         while(s)pd(q[s--]);
 34         while(f[x]!=w){
 35             y=f[x];
 36             if(f[y]!=w){if((ch[f[y]][0]==y)^(ch[y][0]==x))rotate(x);else rotate(y);}
 37             rotate(x);
 38         }
 39         if(!w)root=x;
 40         up(x);
 41     }
 42     void build(int &x,int l,int r,int fa=0)//按照数组下标建树
 43     {
 44         if(l>r)return;
 45         int mid=l+r>>1;
 46         nw(x,mid,fa);
 47         build(ch[x][0],l,mid-1,x);
 48         build(ch[x][1],mid+1,r,x);
 49         up(x);
 50     }
 51     inline int find(int _key) //返回值为key的节点 若无返回0 若有将其转移到根处
 52     {
 53         if(!root)return 0;
 54         int x=root;
 55         for(pd(x);x&&key[x]!=_key;)x=ch[x][key[x]<_key];
 56         if(x)splay(x,0);
 57         return x;
 58     }
 59     inline void Delete(int r)//删除下标为r的节点
 60     {  
 61         splay(r,0);
 62         int pos=sz[ch[r][0]];
 63         splay(kth(pos),0);
 64         splay(kth(pos+2),root);
 65         ch[ch[root][1]][0]=0;  
 66         up(ch[root][1]),up(root);
 67     } 
 68     inline int kth(int k)//获得第k小
 69     {
 70         if(k>sz[root]||k<=0)return 0;
 71         int x=root,tmp;
 72         while(1)
 73         {
 74             pd(x),tmp=sz[ch[x][0]]+1;
 75             if(k==tmp)break;
 76             if(k<tmp)x=ch[x][0];else k-=tmp,x=ch[x][1];
 77         }
 78         return x;
 79     }
 80 }spt;
 81 //--------------------------------
 82 
 83 int n,now,f[N],ed;
 84 struct node
 85 {
 86     int x,idx;
 87     bool operator <(const node &b)const{return x!=b.x?x<b.x:idx<b.idx;}
 88 }a[N];
 89 set<node>st;
 90 set<node>::iterator it;
 91 int find(int x){return f[x]!=x?f[x]=find(f[x]):x;}
 92 
 93 int getkth(int x)
 94 {
 95     int rt=spt.find(x);
 96     return spt.sz[spt.ch[rt][0]]+1;
 97 }
 98 
 99 int del()
100 {
101     it=st.lower_bound({a[ed].x,now});
102     if(it==st.end()||it->x > a[ed].x)
103     {
104         it=st.lower_bound({a[ed].x,1});
105     }
106     int tmp=it->idx;
107     st.erase(it);
108     return tmp;
109 }
110 
111 int main()
112 {
113     scanf("%d",&n);
114     F(i,1,n)scanf("%d",&a[i].x),a[i].idx=i,f[i]=i,st.insert(a[i]);
115     sort(a+1,a+1+n);
116     spt.build(spt.root,1,n+2);
117     now=1,ed=1;
118     long long ans=0;
119     while(ed<=n)
120     {
121         int cur=getkth(now+1),tp=del();
122         int tmp=getkth(tp+1);
123         if(tmp>=cur)ans+=tmp-cur+1;
124         else ans+=spt.sz[spt.root]-cur+tmp-1;
125         int rt=spt.find(tp+1);
126         spt.Delete(rt);
127         if(tp<n)f[tp]=tp+1;
128         else f[tp]=1;
129         if(ed<n)now=find(f[tp]);
130         ed++;
131     }
132     printf("%lld\n",ans);
133     return 0;
134 }