题解：P9986 [Ynoi2079] r2pspc

· · 题解

和另一篇题解的做法不一样，但本质上差不多。

首先可以离散化，使得值域是 O(n)，因为容易证明最多有 n 个位置可能存在一种情况使得该位置上是 1。

考虑暴力扫一遍数组维护进位，可以证明总进位次数是均摊 O(n) 的。但如果把这个暴力直接改成莫队，这个均摊的结构就会被破坏，因此我们考虑回滚莫队。

按照左端点所在块为第一关键字，右端点位置为第二关键字排序，移动右端点的部分直接暴力插入的均摊复杂度是对的，因此只需要考虑如何将左侧左端点所在的散块一并计入答案。

设块长是 B，我们可以先对块内的所有点再进行一次离散化，也容易证明此时可能为 1 的位置只有 O(B) 个，我们先将散块中所有数求和得到一个二进制数，然后我们考虑直接合并散块对应的数和原本的数。

我们需要维护两个二进制数（设为 a,b）加起来后 1 的个数。分类讨论一下（x_i 表示 x 的第 i 位）：

如果 a_i = b_i，代表如果这一位是 1，则前面要恰有一个进位，分析一下可以发现，这相当于满足 j<i 且 a_j = b_j 的最小的 j 有 a_j = b_j = 1。

如果 a_i \neq b_i，类似的，如果这一位是 1，则前面不能进位，相当于满足 j<i 且 a_j = b_j 的最小的 j 有 a_j = b_j = 0。

由于我们此时的 b 是由 O(B) 个数加起来得到的，因此其中 1 的数量一定不超过 O(B) 个，由此进行快速计算。

对于 a_i = b_i 的部分，容易发现这部分 =1 的个数实际上就是满足 a_j = b_j = 1 的 j 的个数，是容易的。

而对于 a_i\neq b_i 的部分，考虑所有 a_j = b_j 的 j 将序列划分成若干段，实际上相当于段内满足，段的左侧边界是 a_j = b_j = 0 的点的个数。

考虑其补集，其实就相当于对于每个 a_i = b_i = 1 的 i 求出最小的 j 满足 a_j = b_j，答案是 tot- \sum_{a_i = b_i = 1} j-i-1。

考虑所有此时可能成为 1 的位置，称这些位置是关键位置，实际上我们在求上面这个东西的时候，可以枚举所有关键位置，于是问题相当于，在每对相邻的关键位置之间找到最靠前 i 满足 a_i = 0（此时 i 不是关键位置，所以一定有 b_i = 0）。

由于我们的关键位置是固定的，问题类似于单点修改，查询序列上第一个 0，但这个问题直接做做不了。

考虑二进制操作的性质，此时给一个位置 +1 相当于，把一个 1 连续段的后缀全部改成 0 再在后面加上一个 1。

发现这个操作的形式很好，实际上我们可以在 O(1) 的时间内直接动态维护出所有的 1 连续段（只需要在段左端点处维护对应右端点，右端点同理），于是每一次查询都可以做到 O(B)。

复杂度 O(qB+\frac{n^2}{B})，取 B = \frac{n}{\sqrt q}，复杂度 O(n\sqrt m)。


#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(3)
const int inf = 1e9;
int n,m;
int B;
int a[100005],b[100005];
int l[1000005],r[1000005];
int id[1000005],ans[1000005];
int ll[100005],rr[100005];
int nxt[100005],lst[100005];
int len,S[100005];
int in[100005];
int be[100005];
void init(){
    //离散化
    basic_string<int>S;
    for(int i = 1;i<=n;i++)b[i] = a[i];
    sort(b+1,b+1+n);
    int v = 0,cnt = 0;
    for(int i = 1;i<=n;i++){
        while(v<b[i] and cnt>=2){
            S.push_back(v+1);
            ++v;
            cnt/=2;
        }
        if(v == b[i])++cnt;
        else{
            S.push_back(b[i]);
            v = b[i],cnt = 1;
        }
    }
    while(cnt>=2)S.push_back(v+1),++v,cnt/=2;
    sort(S.begin(),S.end());
    for(int i = 1;i<=n;i++)a[i] = lower_bound(S.begin(),S.end(),a[i])-S.begin()+1;
    B = n/sqrt(m);
    for(int i = 1;i<=n/B;i++)ll[i] = (i-1)*B+1,rr[i] = i*B;rr[n/B] = n;
    for(int i = 1;i<=n/B;i++)for(int j = ll[i];j<=rr[i];j++)be[j] = i;
}
bool cmp(int a,int b){
    if(be[l[a]]==be[l[b]]){return r[a]<r[b];}
    return be[l[a]]<be[l[b]];
}
int cc[100005];
int tot = 0;//没用的 1 的个数
void Add1(int l,int r){
    for(int i = l;i<=r;i++){
        ++tot;
        int now = a[i];
        cc[now]++;
        while(cc[now]==2)cc[now] = 0,cc[now+1]++,--tot,++now;
    }
}
void Del1(int l,int r){
    for(int i = l;i<=r;i++){
        --tot;
        int now = a[i];
        cc[now]--;
        while(cc[now]==-1)cc[now]=1,cc[now+1]--,++tot,++now;
    }
}
void work(int id){
    Add1(l[id],r[id]);
    ans[id] = tot;
    Del1(l[id],r[id]);
}
void Init(int id){
    for(int i = 1;i<len;i++)in[S[i]] = 0;len = 0;
    for(int i = ll[id];i<=rr[id];i++){
        ++tot;
        int now = a[i];
        cc[now]++;
        if(!in[now])S[++len] = now,in[now] = 1;
        while(cc[now]==2){
            cc[now] = 0,cc[now+1]++,--tot,++now;
            if(!in[now])S[++len] = now,in[now] = 1;
        }
    }
    sort(S+1,S+1+len);
    S[++len] = inf;
    Del1(ll[id],rr[id]);
}
int cnt[100005];
int TOT;//总共的 1 的数量
int cnt2 = 0;
void add(int x){
    int now = x;
    cnt[now]++;TOT++;
    int ll = -1;
    while(cnt[now]==2){
        if(in[now] and ll==-1)ll = now-1;
        cnt[now] = 0,cnt[++now]++,--TOT;
    }
    if(ll==-1)ll = now-1;
    ll = lst[ll];
    if(!in[x-1] and cnt[x-1])nxt[ll] = x-1,lst[x-1] = ll;
    ++cnt2;
    //原本 x 所在的段删掉一个后缀
    //now 从 0 变成 1
    if(in[now])return;//维护的连续段不能包括任何 in=1 的数，in=1 的数遍历时特判
    lst[now] = nxt[now] = now;
    if(cnt[now-1] and !in[now-1])nxt[lst[now-1]] = nxt[now],lst[nxt[now]] = lst[now-1];
    if(cnt[now+1] and !in[now+1])lst[nxt[now+1]] = lst[now],nxt[lst[now]] = nxt[now+1];
}
int lstp;
int cnt1 =0 ;
int slove(int l,int r){
    if(lstp<l)Del1(lstp,l-1);
    else Add1(l,lstp-1);
    lstp = l;
    //每个 11 都会贡献一个 1，每个 01/10 初始认为会贡献一个 1
    int ans = TOT;
    for(int i = 1;i<=len;i++)if(S[i]!=inf and cc[S[i]] and !cnt[S[i]])++ans;
    for(int i = 0;i<len;){
        //统计由于 11 导致的进位的部分
        if(!cc[S[i]] or !cnt[S[i]]){++i;continue;}
        int j = i,pos = 0;
        while(j<len){
            ++cnt1;
            if(j!=i and cc[S[j]] == cnt[S[j]]){pos = S[j];break;}//关键点上出现了 11/00
            if(S[j]+1 == S[j+1]){++j;continue;}//corner case，跳到下一段
            //否则查询 sj+1 所在 1 连续段的末尾
            if(cnt[S[j]+1] == 0){pos = S[j]+1;++j;break;}
            int to = nxt[S[j]+1]+1;
            if(to == S[j+1]){++j;continue;}//全是 1，没找到 0
            pos = to;++j;
            break;
        }
        ans -= (pos-S[i]-1);
        i = j;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i<=n;i++)cin >> a[i];
    for(int i = 1;i<=m;i++)cin >> l[i] >> r[i];
    init();
    for(int i = 1;i<=m;i++)id[i] = i;
    sort(id+1,id+1+m,cmp);
    int llst = 0,nowr;
    for(int ii = 1;ii<=m;ii++){
        int i = id[ii];

        if(llst!=be[l[i]]){
            if(llst)Del1(lstp,rr[llst]);
            TOT = 0;
            memset(cnt,0,sizeof(cnt));
            Init(be[l[i]]);
            nowr = rr[be[l[i]]];
            llst = be[l[i]];
            lstp = nowr+1;
        }
        if(be[l[i]]==be[r[i]]){
            work(i);
            continue;
        }
        while(nowr<r[i])add(a[++nowr]);
        ans[i] = slove(l[i],rr[be[l[i]]]);
    }
    for(int i = 1;i<=m;i++)cout << ans[i] << '\n';
    return 0;
}