P17723 [SCP-S 2026] 函数 / func
赛时做法：不观察任何性质，求出 mex 矩形，拆位套扫描线历史和愣做可以得到 \(O(n \log n \log V)\) 做法，获得 \(45 \sim 55\) 分。
考虑一些人类的做法。我们有下述性质
性质 \(\text{mex}(S)\) 对 \(\text{or}(S)\) 有贡献，当且仅当 \(\text{mex}(S)=2^k\)。
大概就是，贡献位 \(k\) 要求 \(k\) 位为 \(1\) 的数在 \(S\) 中不出现，然后 \(\text{mex}(S)\) 具有 \(k\) 位 \(1\)。可以容易地反证法说明。
仍然拆位枚举 \(k\)。取固定的 \(l\)，我们可以说明 \(\text{or}(S) \lor \text{mex}(S)\) 的 \(k\) 位为 \(1\) 的 \(r\) 是一段后缀，且 \(r_{\min}\) 关于 \(l\) 单增。
指示函数满足区间包含单调性。考虑双指针，那么需要维护一个队列，判掉以下两个条件：
- \(\forall i \in [l,r], a_i\) 的 \(k\) 位为 \(1\)。记录合法的 \(a_i\) 的数目即可。
- \(\forall i \in [0,2^k), i\in S\) 且 \(2^k \notin S\)。维护 \(\left[\min\limits_{i \in [0,2^k)} \text{cnt}_i\ne 0\right]\) 和 \([2^k \notin S]\) 即可。
复杂度 \(O(n \log V)\) 小常数。
const int N = 2e6 + 5;
int n, a[N], mp[N];void _main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];u64 res = 0;for (int k = 0; k < 30; k++) {bool mex = (1< void {if (x < 1 || x > n) return;if (a[x] >> k & 1) ++cnt;if (mex) {if (a[x] == (1< void {if (x < 1 || x > n) return;if (a[x] >> k & 1) --cnt;if (mex) {if (a[x] == (1< bool {if (cnt) return true;if (col == (1< n) break;res += (1ULL<