题目链接：http://uoj.ac/problem/239
题目大意：
这是一道交互题，交互库维护了一个数据结构，可以存储n为二进制串，一开始你可以向空的数据结构中插入若干二进制串，
接下来这个数据结构会将其中存储的二进制串进行改变。
改变的方法是生成一个0到n-1的排列pi，将原来的二进制串a0a1a2..an-1变成ap0ap1..apn-1。
接着你可以进行询问，每次询问一个串是否在这个数据结构当中，要求你在不超过w次插入和r次询问中求出排列p
分析：读完题后看看数据范围，w=r=896=128*7=nlog^2(n)，提示我们用分治算法
加数：
我们需要在开始一次性把所有数加完。
考虑加哪些数?结合分治，我们把l，r分为(l,mid)(mid+1,r)如果我们把左边的数加入库中，分治时如果我们找到一个数在出现
就说明他是在(l,mid)范围内，否则在(mid+1,r)中，可以完成分治。
对于这个操作我们具体讲讲：根据上面所说，我们只对(l,mid)进行操作，枚举i(l<=i<=mid)我们使(l,i-1)(i+1,mid)为0，其他位置
都为1，把他们都加入库中，这样我们每一层1的个数都不同，所以所有数加入过后不会影响最后分治。
查找 :
我们对(0,n-1)进行分治，每次可以判断一个位置上的数在哪个区间，一直递归到底层可得最后答案。
附上交互代码 :
#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
const int N=;
int ans[N],used[N],len;
inline void add(int l,int r)
{
if(l>=r) return ;
string str="";
for(int i=;i<len;i++) str+='';
for(int i=;i<l;i++) str[i]='';
for(int i=r+;i<len;i++) str[i]=''; int mid=(l+r)>>;
for(int i=l;i<=mid;i++)
{
str[i]='';
add_element(str);
str[i]='';
}
add(l,mid);add(mid+,r);
} int temp[N]; inline void solve(int l,int r)
{
if(l>=r) return ;
string str="";
for(int i=;i<len;i++) str+='';
for(int i=;i<l;i++) str[ans[i]]='';
for(int i=r+;i<len;i++) str[ans[i]]='';
int cnt1=,cnt2=,mid=(l+r)>>;
for(int i=l;i<=r;i++)
{
int o=ans[i];
str[o]='';
if(check_element(str))
{
cnt1++;
temp[l+cnt1-]=ans[i];
}
else
{
cnt2++;
temp[mid+cnt2]=ans[i];
}
str[o]='';
}
for(int i=l;i<=r;i++) ans[i]=temp[i];
solve(l,mid);solve(mid+,r);
} vector<int> cnt;
vector<int> restore_permutation(int n, int w, int r)
{
len=n; memset(used,,sizeof(used));
add(,len-);
compile_set();
for(int i=;i<len;i++) ans[i]=i; solve(,len-);
for(int i=;i<len;i++) temp[ans[i]]=i;
for(int i=;i<len;i++) cnt.push_back(temp[i]);
return cnt;
}
转载请声明！！！