P7906 [Ynoi2005] rpxleqxq

solutions

给你一个长为 $n$ 的序列 $a$ 和一个常数 $x$。

$m$ 次询问，每次询问给出区间 $[l,r]$，查询区间中满足 $i < j \wedge (a_i \oplus a_j) \le x$ 的 $(i,j)$ 个数。

$1 \le n,a_i,x \le 2 \times 10^5,1 \le m \le 10^6$。

莫队二次离线

需要会莫队二次离线，于是学一下，看 板子。

给你长为 $n$ 的序列 $a$ 和一个常数 $k$。

$m$ 次询问，每次询问给出区间 $[l,r]$，查询区间中满足 $i < j \wedge \texttt{popcount}(a_i \oplus a_j) = k$ 的 $(i,j)$ 个数。

$1 \le n,m \le 10^5$，$0 \le a_i,k < 2^{14}$。

莫队，但直接做移动端点复杂度过高，不可接受。

考虑端点移动对当前答案造成的影响，记 $f(j,[l,r])$ 为 $i \in [l,r]$ 的合法 $(i,j)$ 数量，那么 $[l,r] \to [l,r+\Delta]$ 时，当前答案增加

同理，$[l,r-\Delta],[l+\Delta,r],[l-\Delta,r]$ 答案分别增加

有两个和式组成，前者直接预处理即可，时空复杂度均为 $O(n)$。对于后者，可以直接记录所有需计算的 $f$，扫描线计算，时空复杂度均为 $O(n\sqrt{n})$。发现只需记录 $i$ 的区间，这样空间复杂度就是 $O(n)$ 了。

时间复杂度 $O(\binom{14}{k}n+n\sqrt{m})$，空间复杂度 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
#define ar(x) array<int,x>
#define pb push_back
const int N=1e5+10,B=316,INF=1e9;
#define gc getchar()
#define rd read()
inline int read(){
    int x=0,f=0; char c=gc;
    for(;c<'0'||c>'9';c=gc) f|=(c=='-');
    for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

int n,m,k,a[N],idx[N],cnt[N],pre[N];
vector<int> buc; vector<ar(3)> vc[N];

struct QRY{ int l,r,id; }Q[N]; ll ans[N],_ans[N];
inline bool operator<(const QRY &x,const QRY &y){ return idx[x.l]!=idx[y.l]?x.l<y.l:x.r<y.r; }

int main(){

    n=rd,m=rd,k=rd;
    if(k>14){ for(int i=1;i<=m;++i) puts("0"); return 0; }
    for(int i=0;i<(1<<14);++i) if(__builtin_popcount(i)==k) buc.pb(i);
    for(int i=1;i<=n;++i) a[i]=rd,idx[i]=(i-1)/B+1;
    for(int i=1;i<=m;++i) Q[i]={rd,rd,i};
    sort(Q+1,Q+m+1);

    for(int i=1;i<=n;++i){ pre[i]=cnt[a[i]]; for(int v:buc) ++cnt[a[i]^v]; }
    
    for(int i=1,L=1,R=0;i<=m;++i){
        auto [l,r,id]=Q[i];
        if(L>l) vc[R].pb({l,L-1,i});
        for(;L>l;--L) ans[i]-=pre[L-1];
        if(R<r) vc[L-1].pb({R+1,r,-i});
        for(;R<r;++R) ans[i]+=pre[R+1];
        if(L<l) vc[R].pb({L,l-1,-i});
        for(;L<l;++L) ans[i]+=pre[L]; 
        if(R>r) vc[L-1].pb({r+1,R,i});
        for(;R>r;--R) ans[i]-=pre[R];
    }

    memset(cnt,0,sizeof(cnt));
    for (int i=1;i<=n;++i){
        for(int v:buc) ++cnt[a[i]^v];
        for(auto [l,r,id]:vc[i]){
            for(int j=l,cur=0;j<=r;++j){
                cur=cnt[a[j]]-(j<=i&&k==0);
                if(id<0) ans[-id]-=cur;
                else ans[id]+=cur;
            }
        }
    }

    for(int i=1;i<=m;++i) ans[i]+=ans[i-1];
    for(int i=1;i<=m;++i) _ans[Q[i].id]=ans[i];
    for(int i=1;i<=m;++i) printf("%lld\n", _ans[i]);

    return 0;
}

回到本题

先莫队二次离线。需要维护一个集合 $S$，对于数 $v$，快速查询 $i \in S,i \oplus v \le x$ 的 $i$ 的个数。

考虑维护一个桶 buc，插入 $v$ 时，令 $\forall 0 \le i \le x, buc_{i \oplus v} \gets buc_{i \oplus v}+1$。

若 $x$ 形如 $2^k - 1$，可以简单处理，否则可以从高到低按位考虑，需要进行区间加，按 $2^9$ 分块即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
#define ar(x) array<int,x>
#define pb push_back
const int N=2e5+10,B=447,M=1e6+10,INF=1e9;
inline int in(int S,int i){ return (S>>i)&1; }
#define gc getchar()
#define rd read()
inline int read(){
    int x=0,f=0; char c=gc;
    for(;c<'0'||c>'9';c=gc) f|=(c=='-');
    for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

int n,m,k,a[N],idx[N],pre[N];
vector<ar(3)> vc[N];
struct QRY{ int l,r,id; }Q[M]; ll ans[M],_ans[M];
inline bool cmp(const QRY &x,const QRY &y){ return idx[x.l]!=idx[y.l]?x.l<y.l:x.r<y.r; }

int tag1[N],tag2[N];
inline int ask(int v){ return tag1[v]+tag2[v>>9]; }
void ins(int v){
    for(int i=17,l,r;i>=9;--i) if(in(k+1,i)){
        l=(v>>i)<<i,r=l+(1<<i),l>>=9,r>>=9;
        for(int j=l;j<r;++j) ++tag2[j];
        v^=(1<<i);
    }
    for(int i=8,l,r;i>=0;--i) if(in(k+1,i)){
        l=(v>>i)<<i,r=l+(1<<i);
        for(int j=l;j<r;++j) ++tag1[j];
        v^=(1<<i);
    }
}

int main(){

    n=rd,k=rd;
    for(int i=1;i<=n;++i) a[i]=rd,idx[i]=(i-1)/B+1;
    m=rd; for(int i=1;i<=m;++i) Q[i]={rd,rd,i};
    sort(Q+1,Q+m+1,cmp);

    for(int i=1;i<=n;++i) pre[i]=ask(a[i]),ins(a[i]);
    memset(tag1,0,sizeof(tag1)),memset(tag2,0,sizeof(tag2));

    for(int i=1,L=1,R=0;i<=m;++i){
        auto [l,r,id]=Q[i];
        if(L>l) vc[R].pb({l,L-1,i});
        for(;L>l;--L) ans[i]-=pre[L-1];
        if(R<r) vc[L-1].pb({R+1,r,-i});
        for(;R<r;++R) ans[i]+=pre[R+1];
        if(L<l) vc[R].pb({L,l-1,-i});
        for(;L<l;++L) ans[i]+=pre[L]; 
        if(R>r) vc[L-1].pb({r+1,R,i});
        for(;R>r;--R) ans[i]-=pre[R];
    }

    for(int i=1;i<=n;++i){
        ins(a[i]);
        for(auto [l,r,id]:vc[i]){
            for(int j=l,cur;j<=r;++j){
                cur=ask(a[j])-(j<=i);
                if(id<0) ans[-id]-=cur;
                else ans[id]+=cur;
            }
        }
    }

    for(int i=1;i<=m;++i) ans[i]+=ans[i-1];
    for(int i=1;i<=m;++i) _ans[Q[i].id]=ans[i];
    for(int i=1;i<=m;++i) printf("%lld\n", _ans[i]);

    return 0;
}