P9968 [THUPC 2024 初赛] 二进制 题解

· · 题解

Solution：

发现每个左端点总共出现次数是 \log n。

考虑暴力处理每次尝试时，字符串出现的位置的数组，具体地，对于 i 的答案数组，可以通过遍历 \left \lfloor \frac{i}{2} \right \rfloor 的答案数组，找到下一位为 i\bmod 2 的所有位置。

还有一个问题，就是每次找到后要把第一个串给删除。
删除后会有 \mathcal{O}(\log n) 个位置需要改变，也可以暴力重构。
还有就是要注意处理，删除串后，新串下标的改变，可以通过一个简单的树状数组解决。

时间复杂度 \mathcal{O}(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,nxt[N],pre[N],lg[N],s[N];
char S[N];
int t[N];
bool de[N];
int lowbit(int x){return x&-x;}
void add(int x,int k){for(;x<=n;x+=lowbit(x)) t[x]+=k;}
int ask(int x){int res=0;for(;x;x-=lowbit(x)) res+=t[x];return res;}
vector<pair<int,int> > pos[N],tmp;
int a[N];
void print(int id){
    if(pos[id].empty()) {puts("-1 0");return;}
    int x,xx=pos[id][0].first;
    for(auto I:pos[id]) xx=min(xx,I.first);
    x=xx;
    printf("%d %d\n",ask(x),pos[id].size());
    int tot=0;
    for(int i=1,nx=pre[xx];i<lg[id]&&nx;++i,nx=pre[nx]) a[++tot]=nx;
    reverse(a+1,a+tot+1);
    for(int i=0,nx;i<lg[id];++i){
        nx=nxt[x];
        nxt[pre[x]]=nxt[x];pre[nxt[x]]=pre[x];
        pre[x]=nxt[x]=0;add(x,-1);de[x]=1;
        x=nx;
    }
    for(int i=1;i<lg[id]&&x;++i,x=nxt[x]) a[++tot]=x;
    int val=0;
    if(tot<lg[id]) return;
    for(int i=1;i<lg[id];++i) val=(val<<1)|s[a[i]];
    for(int i=1,j;i+lg[id]-1<=tot;++i){
        j=i+lg[id]-1;
        if(s[a[i]]) pos[val].emplace_back(a[i],a[j-1]);
        val=(val<<1)|s[a[j]];
        if(s[a[i]]) pos[val].emplace_back(a[i],a[j]);
        val&=((1<<(lg[id]-1))-1);
    }
}
bool vis[N];
int main(){
    scanf("%d%s",&n,S+1);
    for(int i=1;i<n;++i) nxt[i]=i+1,pre[i+1]=i;
    lg[0]=0;    
    for(int i=1;i<=n;++i){
        lg[i]=lg[i>>1]+1;s[i]=S[i]-'0';
        add(i,1);
        if(s[i]) pos[1].emplace_back(i,i);
    }print(1);
    for(int i=2;i<=n;++i){
        tmp.clear();swap(pos[i],tmp);
        for(auto I:tmp) if(!de[I.first]&&!de[I.second]&&(!vis[I.first])) pos[i].push_back(I),vis[I.first]=1;
        for(auto I:pos[i>>1])
            if(!de[I.first]&&nxt[I.second]&&s[nxt[I.second]]==(i&1)&&(!vis[I.first]))
                pos[i].emplace_back(I.first,nxt[I.second]),vis[I.first]=1;
        for(auto I:pos[i]) vis[I.first]=0;
        print(i);
    }
    return 0;
}