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\) 个位置最近的那个位置，并将之前的位置删去，这样就可以保证一个值只被算一次了，所以这道题就被转换成了主席树上单点修改，区间查询。

代码

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

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

#define int ll

struct president_segment_tree
{
    int cnt=0;
    int root[100005];
    struct node
    {
        int l,r,sum;
    }z[100005*600];
    int clone(int x)
    {
        cnt++;z[cnt]=z[x];
        return cnt;
    }
    void update(int id1,int &id2,int l,int r,int x,int w)
    {
        id2=clone(id1);
        z[id2].sum+=w;
        if(l==r)return;
        else
        {
            int mid=(l+r)>>1;
            if(x<=mid)update(z[id1].l,z[id2].l,l,mid,x,w);
            else update(z[id1].r,z[id2].r,mid+1,r,x,w);
        }
    }
    int query(int id,int l,int r,int x,int y)
    {
//        cout<<"query "<<id<<' '<<l<<' '<<r<<' '<<x<<' '<<y<<' '<<z[id].sum<<'\n';
        if(x<=l&&r<=y)return z[id].sum;
        else
        {
            int mid=(l+r)>>1;
            int ans=0;
            if(x<=mid)ans+=query(z[id].l,l,mid,x,y);
            if(mid<y)ans+=query(z[id].r,mid+1,r,x,y);
            return ans;
        }
    }
}pst;
int a[100005];
struct segment_tree
{
    int tree[100005<<2];
    void build(int p,int l,int r)
    {
        if(l==r)tree[p]=a[l];
        else
        {
            int mid=(l+r)>>1;
            build(p<<1,l,mid);
            build(p<<1|1,mid+1,r);
            tree[p]=tree[p<<1]&tree[p<<1|1];
        }
    }
    int query(int p,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y)return tree[p];
        else
        {
            int mid=(l+r)>>1;
            int ans=(1<<30)-1;
            if(x<=mid)ans&=query(p<<1,l,mid,x,y);
            if(mid<y)ans&=query(p<<1|1,mid+1,r,x,y);
            return ans;
        }
    }
}st;
map<int,int>last;

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    st.build(1,1,n);
    for(int i=1;i<=n;i++)
    {
//        cout<<i<<":\n";
        pst.root[i]=pst.root[i-1];
        if(last.count(a[i]))
            pst.update(pst.root[i],pst.root[i],1,n,last[a[i]],-1);
        last[a[i]]=i;
        pst.update(pst.root[i],pst.root[i],1,n,last[a[i]],1);
        int cur=a[i];
        while(true)
        {
            int l=0,r=i,res=0;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                int now=st.query(1,1,n,mid,i);
                if(now<cur)l=mid,res=mid;
                else r=mid-1;
            }
            if(!res)break;
            cur=st.query(1,1,n,res,i);
//            cout<<cur<<' '<<l<<' '<<i<<'\n';
            if(last.count(cur))
                pst.update(pst.root[i],pst.root[i],1,n,last[cur],-1);
            last[cur]=res;
            pst.update(pst.root[i],pst.root[i],1,n,last[cur],1);
        }
//        cout<<'\n';
    }
    int q;
    cin>>q;
    int lastans=0;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        l=(l^lastans)%n+1;
        r=(r^lastans)%n+1;
        if(l>r)swap(l,r);
        cout<<(lastans=pst.query(pst.root[r],1,n,l,n))<<'\n';
    }
}

/*

*/

#undef int

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
//    cout<<fixed<<setprecision(15);



//    int _;cin>>_;while(_--)
    {
        solve();
    }
    return 0;
}