Interval（20年牛客多校5）

题意#

有一个数列 $A(0\leqslant A_i\lt2^{30})$ 长度为 $N(1\leqslant N\leqslant10^5)$ ，

$F(l,r):=A_l\&A_{l+1}\&\cdots\&A_r$ ，

$S(l,r):=\left\{F(a,b)|\min(l,r)\leqslant a\leqslant b\leqslant\max(l,r)\right\}$ ，

有 $Q(1\leqslant Q\leqslant10^5)$ 组询问，对于给定的 $L,R(1\leqslant L',R'\leqslant N)$ ，求 $S(L,R)$ 的大小，强制在线。

思路#

考虑到固定一个右端点，左端点向左拓展的时候， $F(l,r)$ 的个数不会很多，最多只有 $\log$ 个，于是我们就可以用二分预处理出所有的值。由于需要保留上一个版本的答案，所以我们需要拿一颗主席树来维护，第 $i$ 个版本的线段树中第 $j$ 个位置记录的是 $F(j,i)$ 是否对答案有贡献，这样就涉及了去重的这个问题。一个常见的技巧是对于一个值，只记录离第 $i$ 个位置最近的那个位置，并将之前的位置删去，这样就可以保证一个值只被算一次了，所以这道题就被转换成了主席树上单点修改，区间查询。

代码#

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
}