经验总结

  1. 首页 > 生活 > >

Div. 2 Codeforces Round #832 A-D( 二 )

生活百科

map 记录到 \(i\) 之前所有出现的异或和最后一次出现的位置，分奇数下标偶数下标分别记录 。那么对于一个位置 \(i\)，我们就能找到左侧最近的一个不同奇偶性的位置 \(last[i]\)，使得 \([1,i]\) 和 \([1, last[i] ]\) 的异或和相同，且 \((last[i],i]\) 区间长度为奇数，于是我们就找到了一个划分点 。如果划分点小于 \(l\) 则不可划分 。
时间复杂度 \(O(n \log n + q)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[200007], xsum[200007], last[200007];ll sum[200007];bool solve() {int n, q;cin >> n >> q;for (int i = 1;i <= n;i++) {cin >> a[i];sum[i] = sum[i - 1] + a[i];xsum[i] = a[i] ^ xsum[i - 1];}map<int, int> mp[2];for (int i = 1;i <= n;i++) {if (mp[!(i & 1)].count(xsum[i])) last[i] = mp[!(i & 1)][xsum[i]];mp[i & 1][xsum[i]] = i;}while (q--) {int L, R;cin >> L >> R;if ((xsum[R] ^ xsum[L - 1]) == 0) {if (sum[R] - sum[L - 1] == 0) cout << 0 << '\n';else if ((R - L + 1) & 1 || !a[L] || !a[R]) cout << 1 << '\n';else if (last[R] >= L) cout << 2 << '\n';else cout << -1 << '\n';}else cout << -1 << '\n';}return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;//cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}

经验总结扩展阅读


上一篇：ThreadLocal的使用及原理解析

下一篇：2023年10月4日适不适合搬家 2023年10月4日搬家吉利吗