2020牛客多校第五场 H. Interval

题意：

给定长度为 $N$ 的数组 $A$ ，定义 $F(l, r) = A_l \& A_{l+1} \& \cdots \& A_r$ ， $S(l, r) = \{ F(a, b) \mid min(l, r) \leq a \leq b \leq max(l, r) \}$ 。有 $Q$ 次询问，每次询问给定 $L'$ 和 $R'$ ，取 $L = (L' \oplus lastans) \% N + 1, R = (R' \oplus lastans) \% N + 1$ ，求 $\mid S(L, R)\mid$ ，其中 $lastans$ 为上一次询问的答案，初始值为 $0$ 。 $(1 \leq N, Q \leq 10^5, 0 \leq A_i, L', R' \lt 2^{30})$

链接：

https://ac.nowcoder.com/acm/contest/5670/H

解题思路：

考虑单次询问的暴力做法，对询问 $[L, R]$ ，枚举子区间右端点，扩展左端点，将所有位与出来的值去重后的个数就是答案，这样复杂度起码是单次 $O(n^2)$ 的。

进一步分析可以得到，对于 $A_i$ ，向左扩展的出的不同数是严格递减的（更进一步，二进制位的 $1$ 的个数的递减的），一个 $A_i$ 只会扩展出 $O(log A_i)$ 个不同的数，此时优化了暴力做法，但预处理之后每次询问需要去重，复杂度仍是 $O(nlogA_i)$ 的。

现在问题变成如何快速进行去重操作，先推荐一道题：http://acm.hdu.edu.cn/showproblem.php?pid=5919 ,大致题意是求强制在线求区间数字去重排序后的中位数。回到本题，可以用主席树维护 $n$ 个版本（版本 $i$ 代表区间 $[1, i]$ ），对每个版本 $i$ ，相同的数字 $x$ 只保留最靠近 $i$ 的那一个（具体做法：维护每个数的最右端位置，当插入 $x$ 时，先在该版本删除上一次出现的 $x$ ，再插入），那么询问 $[L, R]$ 时，查询版本 $R$ ，数字 $x$ 对询问区间有贡献当且仅当 $Rightmost(x) \geq L$ ，且所有相同的 $x$ 仅有这个最右端的一个，贡献非 $0$ 即 $1$ ，故可以直接求和。

综上，先用各种方法预处理出所有可能的位与值，逐一去重插入到主席树中，询问就是一次区间求和操作。时间复杂度是 $O(nlognloga)$ 。

参考代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define sz(a) ((int)a.size())
#define pb push_back
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

map<int, int> last;
int rt[maxn], ls[maxn * 415], rs[maxn * 415], sum[maxn * 415];
int a[maxn];
int n, q, tot;

void update(int l, int r, int &rt, int pre, int pos, int val){

    rt = ++tot, sum[rt] = sum[pre] + val, ls[rt] = ls[pre], rs[rt] = rs[pre];
    if(l == r) return;
    int mid = gmid;
    if(pos <= mid) update(l, mid, ls[rt], ls[pre], pos, val);
    else update(mid + 1, r, rs[rt], rs[pre], pos, val);
}

int query(int l, int r, int rt, int L, int R){

    if(l >= L && r <= R) return sum[rt];
    int mid = gmid, ret = 0;
    if(L <= mid) ret += query(l, mid, ls[rt], L, R);
    if(R > mid) ret += query(mid + 1, r, rs[rt], L, R);
    return ret;
}

struct SegTree{

    int dt[maxn << 2];
    void build(int l, int r, int rt){

        if(l == r){

            dt[rt] = a[l];
            return;
        }
        int mid = gmid;
        build(l, mid, lson);
        build(mid + 1, r, rson);
        dt[rt] = dt[lson] & dt[rson];
    }
    int query(int l, int r, int rt, int L, int R){

        if(l >= L && r <= R) return dt[rt];
        int mid = gmid, ret = (1 << 30) - 1;
        if(L <= mid) ret &= query(l, mid, lson, L, R);
        if(R > mid) ret &= query(mid + 1, r, rson, L, R);
        return ret;
    }
} tr;

int main(){

    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){

        cin >> a[i];
    }
    tr.build(1, n, 1);
    for(int i = 1; i <= n; ++i){

        rt[i] = rt[i - 1];
        if(last.count(a[i])) update(1, n, rt[i], rt[i], last[a[i]], -1);
        last[a[i]] = i;
        update(1, n, rt[i], rt[i], i, 1);
        int cur = a[i];
        while(1){

            int l = 1, r = i - 1, mid, ret = 0;
            while(l <= r){

                mid = gmid;
                if(tr.query(1, n, 1, mid, i) < cur) ret = mid, l = mid + 1;
                else r = mid - 1;
            }
            if(!ret) break;
            cur = tr.query(1, n, 1, ret, i);
            if(last.count(cur)) update(1, n, rt[i], rt[i], last[cur], -1);
            last[cur] = ret; // 可以证明新出现的数字下标一定比之前所有该数字下标大，直接更新即可
            update(1, n, rt[i], rt[i], ret, 1);
            // cout << i << " ? " << ret << " " << cur << endl;
        }
    }
    cin >> q;
    int ans = 0;
    while(q--){

        int l, r; cin >> l >> r;
        l = (l ^ ans) % n + 1;
        r = (r ^ ans) % n + 1;
        if(l > r) swap(l, r);
        ans = query(1, n, rt[r], l, n);
        cout << ans << "\n";
    }
    return 0;
}