题解：AT_joisc2016_b 神経衰弱

· · 题解

提供一个思路比较简单的做法。

考虑如果我们能找出 \max P_{A_i} 所在的 i 那么整个题直接被灭了。因为我们查询它和另外一个位置总是返回另外一个位置的颜色，所以我们只需要花费 2N 的代价扫一遍数组，把同色的放在一起就做完了。

考虑怎么找出这个位置。

考虑这样一个事实：我们随便选一个位置 s，然后问一圈所有位置，将产生 2N-1 个返回值。这些返回值中，有一些满足 P_{A_i}<P_s 的位置将返回 A_i，剩下的位置将返回 P_s。

据此我们可以划分出 P_{A_i}\ge P_s 的位置 i 们：也就是那些返回值为 P_s 的位置。虽然我们无法得知 P_s，但是可以发现，只要我们划分的时候保证每个颜色的两个位置都同时保留下来（这是应该做到且容易做到的），那么 2N-1 个返回值中唯一那个出现次数为奇数的颜色其实就是 P_s，并且剩下的 P_{A_i}<P_s 的颜色的两个位置是清楚的，因为它们的出现次数都是恰好为 2。

于是我们可以不断划分，直到剩下两个位置，这两个位置就是 \max P_{A_i} 所在的 i。

随机选择一个位置开始划分，每次期望可以把候选集缩小一半。于是总询问次数是 2N+N+\frac{N}{2}+\cdots=4N，考虑到最后还要用找出的位置扫一遍整个数组就是 6N。由于随机有常数，所以无法通过。

显然我们根本没有必要重新扫一遍。回顾我们的过程，那些 P_{A_i}<P_s 的位置是清楚的，所以我们可以在随机折半计算 \max P_{A_i} 的同时就把确定的位置给处理掉。当我们的候选集内只剩下 \max 时，显然所有位置都顺便处理好了。

这样做总询问次数就是 2N+N+\frac{N}{2}+\cdots=4N 级别的，算上随机的常数可以通过。

vector <int> p;
int maxid;
mt19937 rnd(time(0));
vector <int> bol[55];
bool vis[110];
vector <int> col[55];
void Solve(int tc, int n){
    fr1(i,0,2*n-1) p.pb(i);
    while(p.size()>2){
        int id=p[rnd()%p.size()];
        for(auto i:p){
            if(id==i) continue;
            int val=Flip(i,id);
            bol[val].pb(i); 
        }
        p.clear();
        fr1(i,0,n-1){
            if(bol[i].size()==2){
                for(auto j:bol[i]) vis[j]=1;
                col[i]=bol[i];
                continue;
            }
            for(auto j:bol[i]) p.pb(j);
        }
        p.pb(id);
        fr1(i,0,n-1) bol[i].clear();
    }
    maxid=p[0];
    fr1(i,0,2*n-1){
        if(vis[i]) continue;
        if(maxid!=i) col[Flip(i,maxid)].pb(i);
    }
    fr1(i,0,n-1){
        if(col[i].size()==2) Answer(col[i][0],col[i][1],i);
        else Answer(col[i][0],maxid,i);
    }
}