牛客第五场 H Interval —— 主席树

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $F(l,r)=A_l\&A_{l+1}\&...\&A_r$
     S ( l , r ) = { F ( a , b ) ∣ m i n ( l , r ) ≤ a ≤ b ≤ m a x ( l , r ) } S(l, r) = \{F(a, b) | min(l, r) ≤ a ≤ b ≤ max(l, r)\} S(l,r)={ F(a,b)∣min(l,r)≤a≤b≤max(l,r)}
    $Q$ 次查询 $l$ 和 $r$，求 $S(l,r)$

解题思路：

    一个数字连续作与操作，不同数字最多出现 $log$ 个
    因此对每个 $a_i$，记录它往左不停作与操作出现的不同数字
    这里我们要查询 $S(l,r)$，也就是以 $r$ 为右端点，做与操作的不同数字且产生过程都在 $l$ 右端
    联想到主席树求区间不同数字的操作
    这里就可以在记录 $a_i$ 往左不停作与操作出现的不同数字 的同时
    维护产生这些数字的左端点的最大值
    这个最大值 $max$ 就是我们查询 $S(l,r)$ 时，$l$ 必须要 $\le max$
    因为所有的不同数字最多 $nlogn$ 个，因此直接用 $map$ 维护最大值即可
    时间复杂度：$O(nlo{g}^{2}n+qlogn)$

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 1e5 + 5;
int T, n, q, lans, tot, root[maxn];
int t[maxn*300], ls[maxn*300], rs[maxn*300];
map <int, int> mp, tmp, las;void update(int &rt, int pre, int pos, int c, int l, int r) {if(l>pos || r<pos) return;rt = ++tot;t[rt] = t[pre] + c;ls[rt] = ls[pre], rs[rt] = rs[pre];if(l == r) return;int mid = l + r >> 1;update(ls[rt], ls[pre], pos, c, l, mid);update(rs[rt], rs[pre], pos, c, mid+1, r);
}int query(int rt, int L, int R, int l, int r) {if(l>R || r<L) return 0;if(l>=L && r<=R) return t[rt];int mid = l + r >> 1, ret = 0;ret += query(ls[rt], L, R, l, mid);ret += query(rs[rt], L, R, mid+1, r);return ret;
}signed main() {scanf("%d", &n);for(int i=1, x; i<=n; ++i) {scanf("%d", &x);root[i] = root[i-1];mp[x] = i; tmp.clear();for(auto j : mp) {int fi = j.first, se = j.second;tmp[fi & x] = max(tmp[fi & x], se);}for(auto j : tmp) {int fi = j.first, se = j.second;if(las[fi] == se) continue;update(root[i], root[i], las[fi], -1, 1, n);las[fi] = se;update(root[i], root[i], las[fi], 1, 1, n);}mp.swap(tmp);}scanf("%d", &q);while(q--) {int l, r;scanf("%d%d", &l, &r);l = (l ^ lans) % n + 1;r = (r ^ lans) % n + 1;if(l > r) swap(l, r);printf("%d\n", lans = query(root[r], l, r, 1, n));}
}