Interval (2020 Nowcoder Multi-School #5)

Problem#

You are given an array $A$ of length $N$ with $0 \le A_i < 2^{30}$ and $1 \le N \le 10^5$ .

Define $F(l, r) := A_l \,\&\, A_{l+1} \,\&\, \cdots \,\&\, A_r$ (bitwise AND over the range).

Define $S(l, r) := \{\, F(a, b) \mid \min(l, r) \le a \le b \le \max(l, r) \,\}$ .

There are $Q$ queries with $1 \le Q \le 10^5$ . For each query $(L, R)$ with $1 \le L, R \le N$ , output $|S(L, R)|$ — the number of distinct values that appear as an AND of any subarray inside $[L, R]$ . Queries are forced-online.

Approach#

Fix the right endpoint and slide the left endpoint leftward. Because a bitwise AND only ever loses bits, $F(l, r)$ takes at most $O(\log V)$ distinct values, and each transition can be found via binary search on a segment tree that supports range AND.

Since queries are online, we need every historical state, so we maintain a persistent segment tree: version $i$ ‘s tree records, at position $j$ , whether $F(j, i)$ contributes to the answer. Deduplication uses a classic trick — for each value only keep the latest position that produces it, deleting the previous occurrence. This ensures each distinct AND value is counted exactly once.

The problem then reduces to: point update, range sum query on the persistent segment tree.

Code#

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define ll long long
5
#define fi first
6
#define se second
7
const double eps=1e-12;
8
const int inf=0x3f3f3f3f;
9
const ll INF=0x3f3f3f3f3f3f3f3f;
10
const double pi=acos(-1.0);
11
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}
12

13
#define int ll
14

15
struct president_segment_tree
16
{
17
    int cnt=0;
18
    int root[100005];
19
    struct node
20
    {
21
        int l,r,sum;
22
    }z[100005*600];
23
    int clone(int x)
24
    {
25
        cnt++;z[cnt]=z[x];
26
        return cnt;
27
    }
28
    void update(int id1,int &id2,int l,int r,int x,int w)
29
    {
30
        id2=clone(id1);
31
        z[id2].sum+=w;
32
        if(l==r)return;
33
        else
34
        {
35
            int mid=(l+r)>>1;
36
            if(x<=mid)update(z[id1].l,z[id2].l,l,mid,x,w);
37
            else update(z[id1].r,z[id2].r,mid+1,r,x,w);
38
        }
39
    }
40
    int query(int id,int l,int r,int x,int y)
41
    {
42
        if(x<=l&&r<=y)return z[id].sum;
43
        else
44
        {
45
            int mid=(l+r)>>1;
46
            int ans=0;
47
            if(x<=mid)ans+=query(z[id].l,l,mid,x,y);
48
            if(mid<y)ans+=query(z[id].r,mid+1,r,x,y);
49
            return ans;
50
        }
51
    }
52
}pst;
53
int a[100005];
54
struct segment_tree
55
{
56
    int tree[100005<<2];
57
    void build(int p,int l,int r)
58
    {
59
        if(l==r)tree[p]=a[l];
60
        else
61
        {
62
            int mid=(l+r)>>1;
63
            build(p<<1,l,mid);
64
            build(p<<1|1,mid+1,r);
65
            tree[p]=tree[p<<1]&tree[p<<1|1];
66
        }
67
    }
68
    int query(int p,int l,int r,int x,int y)
69
    {
70
        if(x<=l&&r<=y)return tree[p];
71
        else
72
        {
73
            int mid=(l+r)>>1;
74
            int ans=(1<<30)-1;
75
            if(x<=mid)ans&=query(p<<1,l,mid,x,y);
76
            if(mid<y)ans&=query(p<<1|1,mid+1,r,x,y);
77
            return ans;
78
        }
79
    }
80
}st;
81
map<int,int>last;
82

83
void solve()
84
{
85
    int n;
86
    cin>>n;
87
    for(int i=1;i<=n;i++)cin>>a[i];
88
    st.build(1,1,n);
89
    for(int i=1;i<=n;i++)
90
    {
91
        pst.root[i]=pst.root[i-1];
92
        if(last.count(a[i]))
93
            pst.update(pst.root[i],pst.root[i],1,n,last[a[i]],-1);
94
        last[a[i]]=i;
95
        pst.update(pst.root[i],pst.root[i],1,n,last[a[i]],1);
96
        int cur=a[i];
97
        while(true)
98
        {
99
            int l=0,r=i,res=0;
100
            while(l<r)
101
            {
102
                int mid=(l+r+1)>>1;
103
                int now=st.query(1,1,n,mid,i);
104
                if(now<cur)l=mid,res=mid;
105
                else r=mid-1;
106
            }
107
            if(!res)break;
108
            cur=st.query(1,1,n,res,i);
109
            if(last.count(cur))
110
                pst.update(pst.root[i],pst.root[i],1,n,last[cur],-1);
111
            last[cur]=res;
112
            pst.update(pst.root[i],pst.root[i],1,n,last[cur],1);
113
        }
114
    }
115
    int q;
116
    cin>>q;
117
    int lastans=0;
118
    while(q--)
119
    {
120
        int l,r;
121
        cin>>l>>r;
122
        l=(l^lastans)%n+1;
123
        r=(r^lastans)%n+1;
124
        if(l>r)swap(l,r);
125
        cout<<(lastans=pst.query(pst.root[r],1,n,l,n))<<'\n';
126
    }
127
}
128

129
#undef int
130

131
int main()
132
{
133
    ios::sync_with_stdio(false);cin.tie(nullptr);
134
    {
135
        solve();
136
    }
137
    return 0;
138
}