记$a_{i}$为第$i$个展馆的艺术价值，问题即求排列$id_{1},id_{2},...,id_{n}$使得$\forall 1\le i\le n,a_{id_{i}}$单调递增

定义操作$swap(i,j)$表示调用$schedule(id_{i},id_{j})$，并在其返回0时（即$a_{id_{i}}>a_{id_{j}}$）交换$id_{i}$和$id_{j}$

双调序列：可以通过旋转若干次使得其前半部分递增、后半部分递减的序列

Batcher定理：将双调序列$a_{1},a_{2},...,a_{2n}$对$\forall 1\le i\le n$且$a_{i}>a_{i+n}$交换$a_{i}$和$a_{i+n}$，则交换后$a_{1},a_{2},...,a_{n}$和$a_{n+1},a_{n+2},...,a_{2n}$均是双调序列且前者最大值$<$后者最小值

不妨假设$n=2^{m}$（在$a_{(n,2^{m}]}$上补$\infty$），并考虑实现以下两个函数：

1.$solve(l,r)$表示将$id_{l},id_{l+1},...,id_{r}$重排，使得$\forall l\le i\le r,a_{id_{i}}$单调递增

2.$solve_{B}(l,r)$与$solve(l,r)$目的相同，但保证初始该序列（指最终单调递增的序列）是双调序列

关于前者，具体过程如下：
$$
solve(l,mid),solve(mid+1,r)\rightarrow reverse(id_{mid+1},id_{mid+2},...,id_{r})\rightarrow solve_{B}(l,r)
$$
关于后者，具体过程如下：
$$
\forall l\le i\le mid,swap(i,i+mid-l)\rightarrow solve_{B}(l,mid),solve_{B}(mid+1,r)
$$
（前者正确性显然，后者正确性根据Batcher定理也显然）

通过这两个函数，初始令$id_{i}=i$并调用$solve(1,n)$即可

考虑利用并行对$swap$操作的次数优化：

1.对于$solve_{B}(l,r)$而言，即从大到小$swap$所有以$2^{m_{0}}$为间隔的两数，那么仅需要使用$o(\log n)$次$visit$操作

2.对于$solve(l,r)$而言，即将整个序列从小到大划分为长为$2^{m_{0}}$的若干段，每一段内做$solve_{B}$操作

综上，共计$o(\log^{2}n)$次$visit$操作，可以通过

 1 #include<bits/stdc++.h>
 2 #include "swaps.h"
 3 using namespace std;
 4 #define N 512
 5 int n,m,id[N];
 6 vector<int>v,ans;
 7 vector<pair<int,int> >v0;
 8 void Swap(int x,int y){
 9     if ((!id[x])&&(id[y]))swap(id[x],id[y]);
10     if ((id[x])&&(id[y])){
11         schedule(id[x],id[y]);
12         v0.push_back(make_pair(x,y));
13     }
14 }
15 void get_visit(){
16     v=visit();
17     for(int i=0;i<v.size();i++)
18         if (!v[i])swap(id[v0[i].first],id[v0[i].second]);
19     v0.clear();
20 }
21 void solve(int nn,int lim){
22     n=nn,m=1;
23     while (m<n)m<<=1;
24     for(int i=0;i<n;i++)id[i]=i+1;
25     for(int i=2;i<=m;i<<=1){
26         for(int j=0;j<m;j+=i)reverse(id+j+(i>>1),id+j+i);
27         for(int j=(i>>1);j;j>>=1){
28             for(int k=0;k<m;k++)
29                 if (k&j)Swap((k^j),k);
30             get_visit();
31         }
32     }
33     for(int i=0;i<n;i++)ans.push_back(id[i]);
34     answer(ans);
35 }

View Code