# 2020牛客多校第五场 H. Interval 给定长度为 $n$ 的数组 ，定义 $F(l,r)=A_l\&A_{l+1}\&\ldots\&A_r$，集合 $S(l,r)=\{F(a,b)|l\leq a\leq b\leq r\}$。有 $Q$ 次询问，每次询问给定 $L'$ 和 $R'$，强制在线 考虑单次询问的暴力做法，对询问 $[L,R]$，枚举子区间右端点，扩展左端点，将所有位与出来的值去重后的个数就是答案，这样复杂度起码是单次 $O(n^2)$ 的。 进一步分析可以得到，对于 $A_i$，向左扩展的出的不同数是严格递减的（更进一步，二进制位的 $1$ 的个数的递减的），一个 $A_i$ 只会扩展出 $O(logA_i)$ 个不同的数，此时优化了暴力做法，但预处理之后每次询问需要去重，复杂度仍是 $O(nlogA_i)$ 的。 现在问题变成如何快速进行去重操作，可以用主席树维护 $n$ 个版本（版本 $i$ 代表区间 $[1,i]$），对每个版本 $i$，相同的数字 $x$ 只保留最靠近 $i$ 的那一个（具体做法：维护每个数的最右端位置，当插入 $x$ 时，先在该版本删除上一次出现的 $x$，再插入），那么询问 $[L,R]$ 时，查询版本 $R$，数字 $x$ 对询问区间有贡献当且仅当 $last[x]\geq L$，且所有相同的 $x$ 仅有这个最右端的一个，贡献非 $1$ 即 $0$，故可以直接求和。 综上，先用各种方法预处理出所有可能的位与值，逐一去重插入到主席树中，询问就是一次区间求和操作。时间复杂度是 $O(nlognloga)$。 ```c++ //2381ms 182392kb #include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define mid (l+r>>1) #define N 100010 #define NN 41500010 unordered_map<int, int> last; int rt[N], ls[NN], rs[NN], sum[NN], tot = 0, a[N]; int n, m; inline int cpy(int o) { ++tot; ls[tot] = ls[o]; rs[tot] = rs[o]; sum[tot] = sum[o]; return tot; } int upd(int p, int l, int r, int x, int k) { int np = cpy(p); sum[np] += k; if (l == r) return np; if (x <= mid) ls[np] = upd(ls[np], l, mid, x, k); else rs[np] = upd(rs[np], mid + 1, r, x, k); return np; } int inq(int p, int l, int r, int x, int y) { if (!p) return 0; if (x <= l && r <= y) { return sum[p]; } int res = 0; if (x <= mid) res += inq(ls[p], l, mid, x, y); if (mid < y) res += inq(rs[p], mid + 1, r, x, y); return res; } struct segtr { #define ls p<<1 #define rs p<<1|1 int val[N << 2]; void build(int p, int l, int r) { if (l == r) { val[p] = a[l]; return; } build(ls, l, mid), build(rs, mid + 1, r); val[p] = val[ls] & val[rs]; } int inq(int p, int l, int r, int x, int y) { if (x <= l && r <= y) { return val[p]; } int res = -1; if (x <= mid) res &= inq(ls, l, mid, x, y); if (mid < y) res &= inq(rs, mid + 1, r, x, y); return res; } #undef ls #undef rs } tr; signed main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; tr.build(1, 1, n); for (int i = 1; i <= n; ++i) { rt[i] = rt[i - 1]; if (last.count(a[i])) rt[i] = upd(rt[i], 1, n, last[a[i]], -1); last[a[i]] = i; rt[i] = upd(rt[i], 1, n, i, 1); int cur = a[i]; while (true) { //固定右端点向左&时显然结果从a[r]递减，我们可以用二分查找区间与的结过在什么位置首次下降 int l = 1, r = i - 1, ret = 0; while (l <= r) { if (tr.inq(1, 1, n, mid, i) < cur) ret = mid, l = mid + 1; else r = mid - 1; } if (!ret) break; cur = tr.inq(1, 1, n, ret, i); if (last.count(cur)) rt[i] = upd(rt[i], 1, n, last[cur], -1); last[cur] = ret; // 可以证明新出现的数字下标一定比之前所有该数字下标大，直接更新即可 rt[i] = upd(rt[i], 1, n, ret, 1); } } cin >> m; int ans = 0, x, y; while (m--) { cin >> x >> y; x = (x ^ ans) % n + 1; y = (y ^ ans) % n + 1; if (x > y) swap(x, y); ans = inq(rt[y], 1, n, x, n); cout << ans << endl; } } ``` 可以发现这个程序空间用了 $182392KB$ 虽然对于题目的 $512MB$ 绰绰有余，但鄙人作为 $崩^3$ 老玩家，不凹点什么东西实在难受 观察代码可以发现主席树对同一版本内的修改依旧会每次都创建一整条新链，但实际上因为属于同一版本有很多结点可以重复利用，所以增加每个结点所属的版本号 $tag[i]$，只有当前版本与结点版本不同是才创建新结点 ```c++ int upd(int p, int l, int r, int x, int k, int blo) { int np = tag[p] != blo ? cpy(p) : p; tag[np]=blo; sum[np] += k; if (l == r) return np; if (x <= mid) ls[np] = upd(ls[np], l, mid, x, k, blo); else rs[np] = upd(rs[np], mid + 1, r, x, k, blo); return np; } ``` 经过优化后使用空间为 $80728KB$，现在主席树只需要开到 $sum[N*45]$，但是具体空间复杂度我并不会证，所以说要开多大才够用我也不知道。同时只有对同一版本有多次修改时，这种优化才有效果，否则因为每个结点需要额为记录版本号可能增加爆空间的概率(edu:to the moon) 但是当我将提交按空间大小排序时发现我只排到第二！这我怎么能忍？于是学了学人家代码 原本我们通过二分加线段树处理出 $A_i$ 向左与时会出现哪些数，但仔细分析可以知道只有向左拓展到某数时其某一位上为 $0$ 时区间与的值才有可能改变，所以用 $tg[31]$ 记录每位上最后一次为 $0$ 时的位置。每次处理 $A_i$ 时更新 $tg[j]$，并临时开个vector最后一次为 $0$ 时的位置（如果存在），并排序去重就可以快速判断区间与的结果将在那些位置改变 最后火车头，快读快写优化。 **空间$75868K$,时间$585 ms$双榜首**。 ```c++ #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define mid (l+r>>1) #define N 100010 #define NN 4500010 unordered_map<int, int> last; int rt[N], ls[NN], rs[NN], sum[NN], tot = 0, a[N], tag[NN], tg[31]; int n, m; inline int read() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); } return x; } inline void wr(int x) { if (x >= 10) wr(x / 10); putchar('0' + x % 10); } inline int cpy(int o) { ++tot; ls[tot] = ls[o]; rs[tot] = rs[o]; sum[tot] = sum[o]; return tot; } int upd(int p, int l, int r, int x, int k, int blo) { int np = tag[p] != blo ? cpy(p) : p; tag[np] = blo; sum[np] += k; if (l == r) return np; if (x <= mid) ls[np] = upd(ls[np], l, mid, x, k, blo); else rs[np] = upd(rs[np], mid + 1, r, x, k, blo); return np; } int inq(int p, int l, int r, int x, int y) { if (!p) return 0; if (x <= l && r <= y) { return sum[p]; } int res = 0; if (x <= mid) res += inq(ls[p], l, mid, x, y); if (mid < y) res += inq(rs[p], mid + 1, r, x, y); return res; } signed main() { n = read(); for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = 1; i <= n; ++i) { for (int j = 0; j < 31; ++j) { if (!(a[i] >> j & 1)) { tg[j] = i; } } vector<int> v; for (int j = 0; j < 31; ++j) { if (tg[j]) v.emplace_back(tg[j]); } v.emplace_back(i); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int s = a[i]; rt[i] = rt[i - 1]; for (int j = v.size() - 1; j >= 0; --j) { if (j != v.size() - 1 && (s & a[v[j]]) == s)continue; s &= a[v[j]]; if (last.count(s)) { if (last[s] < v[j]) { rt[i] = upd(rt[i], 1, n, last[s], -1, i); rt[i] = upd(rt[i], 1, n, v[j], 1, i); last[s] = v[j]; } } else { rt[i] = upd(rt[i], 1, n, v[j], 1, i); last[s] = v[j]; } } } m = read(); int ans = 0, x, y; while (m--) { x = read(), y = read(); x = (x ^ ans) % n + 1; y = (y ^ ans) % n + 1; if (x > y) swap(x, y); ans = inq(rt[y], 1, n, x, n); wr(ans); putchar('\n'); } } ```