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