[THUPC 2024 初赛] 二进制 （树状数组单点删除+单点查询）（双堆模拟set）

题解

题目本身不难想

首先注意到所有查询的序列长度都是小于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]);elseD[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();}}
}