相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf
解题报告
这题又是一道多算法互补的题目
通过分类处理使复杂度达到$O((n+m)\sqrt{n})$
具体来讲是将以下两个算法结合:
1. 枚举右端点的值,若左端点的合法位置超过$\sqrt{n}$个
考虑每一个左右端点应该加减多少,使用前缀和技巧将复杂度优化到$O(n + m)$
具体细节不想写了,有点麻烦_(:з」∠)_
然后因为合法位置超过了$\sqrt{n}$个,所以这种情况至多出现$\sqrt{n}$个,复杂度符合要求2. 其他情况
因为左端点不超过$\sqrt{n}$个,所以可以排序之后依次处理
使用分块来维护左端点的值,单次修改是$\sqrt{n}$的,单次查询是$O(1)$的
Code
#include<bits/stdc++.h> #define LL long long #define UI unsigned int using namespace std; const int N = 150009; const int MOD = 1073741824; const int blk_sz = 800; int n, m, k, a[N]; UI a1[N], ans[N], blk_tag[N], tag[N]; vector<int> num, pos_list[N]; vector<pair<int, int> > left_list[N], right_list[N]; struct Query{ int l, r, w; inline bool operator < (const Query &QQQ) const { return r > QQQ.r; } }q[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { ret = ret * 10 + c - '0'; c = getchar(); } return ret * f; } inline int find(int x) { int l = 0, r = num.size() - 1, mid; while (l <= r) { mid = l + r >> 1; if (num[mid] == x) { return mid; } else if (num[mid] < x) { l = mid + 1; } else { r = mid - 1; } } return -1; } inline void solve(int A, int B) { static UI a2[N], cur; memset(a2, 0, sizeof(a2)); for (int i = 1; i <= n; i++) { a2[i] = a2[i - 1] + (a[i] == num[B]); } cur = 0; for (int i = n; i; i--) { if (a[i] == num[B]) { cur += a1[i]; } if (a[i - 1] == num[A]) { ans[i] += cur; } for (int j = 0; j < (int)left_list[i].size(); ++j) { cur -= (UI)left_list[i][j].second * (a2[left_list[i][j].first] - a2[i - 1]); } } memset(a2, 0, sizeof(a2)); for (int i = 1; i <= n; ++i) { a2[i] = a2[i - 1] + (a[i - 1] == num[A]); } cur = 0; for (int i = 1; i <= n; i++) { if (a[i - 1] == num[A]) { cur -= a1[i]; } if (a[i] == num[B]) { ans[i + 1] += cur; } for (int j = 0; j < (int)right_list[i].size(); ++j) { cur += (UI)right_list[i][j].second * (a2[i] - a2[right_list[i][j].first - 1]); } } } int main() { freopen("xor.in", "r", stdin); freopen("xor.out", "w", stdout); n = read(); m = read(); k = read(); num.push_back(0); for (int i = 1; i <= n; ++i) { a[i] = a[i - 1] ^ read(); num.push_back(a[i]); } sort(num.begin(), num.end()); num.resize(unique(num.begin(), num.end()) - num.begin()); for (int i = 0; i <= n; i++) { int pp = find(a[i]); pos_list[pp].push_back(i); } for (int i = 1, l, r, w; i <= m; ++i) { l = q[i].l = read(); r = q[i].r = read(); w = q[i].w = read(); left_list[l].push_back(make_pair(r, w)); right_list[r].push_back(make_pair(l, w)); a1[l] += w; a1[r + 1] -= w; } sort(q + 1, q + 1 + m); for (int i = 1; i <= n; ++i) { a1[i] += a1[i - 1]; } for (int i = 0; i < (int)num.size(); i++) { int r = i, l = find(num[i] ^ k); if (l != -1 && (int)pos_list[l].size() > blk_sz) { solve(l, r); } } for (int r = n, cur = 0; r; r--) { while (cur < m && q[cur + 1].r >= r) { ++cur; for (int i = q[cur].l, lim = min(q[cur].r, (q[cur].l / blk_sz + 1) * blk_sz - 1); i <= lim; ++i) { tag[i] += q[cur].w; } for (int i = q[cur].l / blk_sz + 1, lim = q[cur].r / blk_sz - 1; i <= lim; ++i) { blk_tag[i] += q[cur].w; } for (int i = max(q[cur].r / blk_sz, q[cur].l / blk_sz + 1) * blk_sz; i <= q[cur].r; ++i) { tag[i] += q[cur].w; } } int t = find(a[r] ^ k); if (t != -1 && (int)pos_list[t].size() <= blk_sz) { for (int tt = 0; tt < (int)pos_list[t].size(); ++tt) { int l = pos_list[t][tt] + 1; if (l <= r) { ans[l] += tag[l] + blk_tag[l / blk_sz]; ans[r + 1] -= tag[l] + blk_tag[l / blk_sz]; } else { break; } } } } for (int i = 1; i <= n; i++) { ans[i] += ans[i - 1]; printf("%d ", ans[i] % MOD); } return 0; }