QOJ15442循环移位题解如何为疑问？
摘要：给定一个长 (n) 的序列 (a)，求 (a) 的所有循环移位 (b_i)，所对应的前缀 (max) 序列 (c_i) 中，字典序最小的那个。 (1le n,Vle 5times 10^5) 首先为了方便
给定一个长 \(n\) 的序列 \(a\)，求 \(a\) 的所有循环移位 \(b_i\)，所对应的前缀 \(\max\) 序列 \(c_i\) 中，字典序最小的那个。
\(1\le n,V\le 5\times 10^5\)
首先为了方便循环，我们复制一下序列。
对于序列中的每一个元素，我们将其连接到它后面第一个严格比它大的元素，这相当于把每个元素连到前缀 \(\max\) 序列中的对应的下一个值。
可以发现你连出来就是一棵树，而且树上每条从底向上的路径，都不可能出现绕了一圈还多的情况。然后我们让每个点都映射一个三元组 \((fa,val,len)\)：
\(fa\)：这个结点对应的父亲；
\(val\)：这个结点本身的值；
\(len\)：这个点在序列上到其父亲的距离。
你会发现这个 \(len\) 刚好对应的就是这个值在前缀 \(\max\) 序列中的出现次数。
我们先将每个结点都作为起点，然后淘汰掉非最优的结点（最优的结点指以 \(val\) 为第一关键字最小，以 \(len\) 第二关键字最大），让它们往上走一步，再淘汰，可以知道这样每个结点最多被经过一次，复杂度是 \(O(n)\) 的。
代码：
const int N=1e6+10;
int n,a[N],dis[N],fa[N];
int stk[N],ans[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dis[i]=n,a[i+n]=a[i];
}
int top=0;
for(int i=1;i<=2*n;i++){
while(top&&a[stk[top]]<a[i]) fa[stk[top]]=i,dis[stk[top]]=i-stk[top],top--;
stk[++top]=i;
}
for(int i=1;i<=n;i++) if(fa[i]>n) fa[i]-=n;
vector<int> v1;
for(int i=1;i<=n;i++) v1.push_back(i);
int cur=0;
while(top>1){
pair<int,int> mn(INF,INF);
for(int u:v1) mn=min(mn,make_pair(a[u],-dis[u]));
for(int i=1;i<=-mn.second;i++) ans[++cur]=mn.first;
if(cur>=n) break;
vector<int> tmp;
for(int u:v1) if(mn.first==a[u]&&-mn.second==dis[u]) tmp.push_back(fa[u]);
v1.swap(tmp);
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<"\n";
}
小技巧：vector 的 swap 方法，只会交换首位指针和容量大小，时间复杂度为常数。