[TIOJ]1172. 握手症候群

題目連結：http://tioj.infor.org/problems/1172

nth_element() 可以將第n個放在陣列第n個位置而他的左方是比他的，右方是比他大的。
而d陣列具有單調性，所以我們可以用二分的方法去做。
d[i]在左邊就用左邊的陣列去做，右邊亦然。

#include "lib1172.h"
#include <algorithm>
using namespace std;
int aa[1000005],b[105],r[105];
void find(int l,int r,int ll,int rr){
    if(l == r || rr == ll)return;
    nth_element(aa+l,aa+b[(ll+rr)/2],aa+r,[](int x,int y){return comp(x,y);});
    find(l,b[(ll+rr)/2],ll,(ll+rr)/2);
    find(b[(ll+rr)/2]+1,r,(ll+rr)/2+1,rr);
}
void query(int n,int d[],int l,int ans[]){
    for(int i = 0 ; i < n ; i++)aa[i] = i;
    for(int j = 0 ; j < l ; j++)b[j] = d[j];
    find(0,n,0,l);
    for(int i = 0; i < l; i ++)ans[i] = aa[d[i]];
}