2020牛客多校第五场 H. Interval

2020牛客多校第五场 H. Interval

题意：

给定长度为 的数组 ，定义 ，。有 次询问，每次询问给定 和 ，取 ，求 ，其中 为上一次询问的答案，初始值为 。

链接：

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

解题思路：

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

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

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

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

参考代码：

#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;
}