题解
题目本身不难想
首先注意到所有查询的序列长度都是小于logn级别的
我们可以枚举序列长度len，然后用类似滑动窗口的方法，一次性预处理出每种字串的所有出现位置，也就是开N个set去维护所有的位置。预处理会进行O(logn)轮，每次需要O(n*logn)的时间复杂度初始化set并计算位置。总共复杂度O(nlog^2n)，看一下时间限制6s，感觉可以过23333。
删除操作可以直接暴力，直接从每种字串的位置集合中删除所有被影响到的位置，然后再把删除后字符串合并产生的新的子串加入到set中，过程中需要支持O(logn)的单点删除和单点查询。
在set中，删除起始点在L~R之间子串信息，再插入起始点在L到x-1的新构成的子串的信息
删除操作最多O(n/logn)次，每次直接暴力就是O(log^2n)，总共复杂度O(nlogn)
接下来就是一些小问题，如何维护单点删除、单点查询的序列呢？
首先我们肯定不会去真正的移动序列，保留原始的输入01序列
可以想到用set去维护当前存在的每个坐标，但是支持查询第k个坐标的话得手写平衡树
也可以想到用线段树或者树状数组维护每个位置的存在信息，在线段树或者树状数组上二分来查询删除后的序列中的第k个坐标的真实位置。
这里使用树状数组
树状数组二分类似于倍增查询LCA的思想，十分易懂。
然后我们迅速写完整个内容，交一发，发现TLE了
看一下复杂度，发现瓶颈在于预处理，于是我们把初始化中对每个位置都进行树状数组二分，替换为直接使用当前位置存在信息数组进行处理，这样预处理中计算坐标的部分就变成O(n)了
但是仍然TLE了
现在瓶颈仍然是预处理，如果C++支持对有序序列O(n)建立set就好了
后来看了洛谷上题解的方法，才知道可以用两个优先队列来模拟set
由于我们只需要维护集合中的最小值以及集合的元素个数
使用两个堆，一个维护插入的内容，另一个维护删除的内容
当查询个数时，两个堆的大小相减即可。当查询最小值时，如果“删除堆”中的最小值与“插入堆”中的最小值相等，就两个一起pop掉，直到找到第一个“插入堆”中存在，但“删除堆”中不存在的元素即可。
（其实也可以用两个vector来模拟，因为对于每种子串，查询的次数只有一次，所以可以大胆排序再查询，这样初始化时间复杂度也是O(nlogn)，查询删除子串的总时间复杂度是最坏O(nlog^2n)不过似乎也能过，因为sort在大部分都有序的情况下还是很快的）
改完之后，从6.18s变成了1.17s，发生了质的飞跃23333
有人可能会问，优先队列插入不也是O(logn)的吗，为什么会比set快这么多，因为预处理的过程中插入集合的内容是顺序的，根据小根堆的实现，只有当自己比父亲值小时，才会发生交换，所以在预处理建立小根堆的过程中是O(n)的，这样预处理的总复杂度就变成了O(nlogn)，删除方面在理论上最坏时间复杂度也是O(nlog^2n)（假设所有的位置都集中在一种子串上，并且“删除堆”和“插入堆”差不多大）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
#define N 1000005
#define LOG 20
int n, n_real, now;
char ss[N];
// 树状数组维护单点删除与单点查询的序列
// 实际坐标->逻辑坐标（删除后的坐标） getsum
// 逻辑坐标->实际坐标 query 树状数组二分
int tra[N];
int getsum(int x)
{
int ret=0;
for(;x;x-=x&-x) ret+=tra[x];
return ret;
}
void update(int x,int k)
{
for(;x<=n;x+=x&-x)
tra[x]+=k;
}
int query(int k)// 查询删除后序列的第k位置的实际坐标
{
int ans=0,sum=0;
for(int i=LOG;i>=0;i--){
if(ans+(1<<i)<=n && sum+tra[ans+(1<<i)]<k){
sum+=tra[ans+(1<<i)];
ans+=(1<<i);
}
}
return ans+1;
}
// a是原始数据，tmp是删除后的数组，b表示当前位是否存在(树状数组建立在b上)
bool a[N],tmp[N],b[N];
int pos[N];
void cal_tmp_all()
{
int cnt=0;
for(int i=1;i<=n;i++){
if(b[i]){
pos[++cnt]=i;
tmp[cnt]=a[i];
}
}
}
void cal_tmp(int l,int r)
{
l=max(1,l);r=min(r,n_real);
for(int i=l;i<=r;i++){
pos[i]=query(i);
tmp[i]=a[pos[i]];
}
}
priority_queue<int,vector<int>,greater<int> > S[N],D[N];
//set<int> S[N];
//set<int>::iterator it;
// 将起始点在l r之间，长度为len的数据加入到set或者从set中删除
void update_set(int l,int r,int len,bool flg)
{
r=min(n_real,r+len-1);
int lim_l= max(now,1<<(len-1)), lim_r= min(n,(1<<len)-1);
int mask=(1<<len)-1;
int tmp_value=0;
for(int i=l;i<=r;i++){
tmp_value=((tmp_value<<1)&mask)|tmp[i];
if(i-l+1 >= len && tmp_value>=lim_l && tmp_value<=lim_r){
if(flg)
S[tmp_value].push(pos[i-len+1]);
else
D[tmp_value].push(pos[i-len+1]);
}
}
}
int main()
{
scanf("%d",&n);n_real=n;
scanf("%s",ss+1);
for(int i=1;i<=n;i++){
a[i]=int(ss[i]-'0');
update(i,1);
b[i]=1;
}
now=1;
for(int len=1;n>>(len-1);len++){
cal_tmp_all();
update_set(1,n_real,len,1);
//printf("start len:%d\n",len);
for(;now<(1<<len);now++){
//printf("now:%d\n",now);
if(now>n)return 0;
int siz = (int)S[now].size()-(int)D[now].size();
if(!siz){
printf("-1 0\n");
continue;
}
while(!S[now].empty()&&!D[now].empty() && S[now].top()==D[now].top()){
S[now].pop();
D[now].pop();
}
int x=getsum(S[now].top());
printf("%d %d\n",x,siz);
int l=max(1,x-len+1),r=min(n_real,x+len-1);
// 删除受影响的结果
cal_tmp(l,r+len-1);
update_set(l,r,len,0);
// 删除对应的01序列
for(int i=x;i<=r;i++){
update(pos[i],-1);
b[pos[i]]=0;
}
n_real-=len;
// 添加新产生的序列结果
cal_tmp(l,x-1+len-1);
update_set(l,x-1,len,1);
while(!S[now].empty())S[now].pop();
while(!D[now].empty())D[now].pop();
}
}
}
