题目链接：Codeforces Round #424 (Div. 2) E. Cards Sorting
题意：
将n个数放进一个队列，每次检查队首，看看是不是队列中最小的数，如果是就扔掉，如果不是就放到队尾。
这样直到队列为空，为需要操作多少次。
题解：
考虑用两个指针模拟，最开始now指针指向第一个数，然后nxt指针指向下一个将要被删除的数。
然后我们要算出这里需要移动多少步，然后删掉这个数，一直重复操作，直到将全部的数删完。
nxt指针可以用set来维护，now指针可以用并查集来维护。
计算now指针到nxt指针需要移动多少步，可以用线段树或者splay来维护。
线段树版本：
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 ",ans); 74 return 0; 75 }
splay版本：
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 ",ans); 133 return 0; 134 }