【KTU|【KTU Programming Camp (Day 3)】Queries 【KTUProgrammingCamp(Day3)】Queries

http://codeforces.com/gym/100739/problem/A
按位考虑，每一位建一个线段树。
求出前缀xor和，对前缀xor和建线段树。
线段树上维护区间内的0的个数和1的个数。
修改就修改p到最后的区间，进行区间取反。
回答询问时把总区间内0的个数和1的个数相乘即可。
时间复杂度\(O(n\log^2n)\)。

#include #include #include using namespace std; typedef long long ll; const int N = 100003; int a[N], s[N], n, m; struct node { node *l, *r; int sum0, sum1, mark; node() { sum0 = sum1 = mark = 0; l = r = NULL; } void pushdown() { if (mark) { mark = 0; if (l) { l->mark ^= 1; swap(l->sum0, l->sum1); } if (r) { r->mark ^= 1; swap(r->sum0, r->sum1); } } } void count_() { sum0 = sum1 = 0; if (l) { sum0 += l->sum0; sum1 += l->sum1; } if (r) { sum0 += r->sum0; sum1 += r->sum1; } } } *rt[15]; node *build_tree(int l, int r, int x) { node *t = new node; if (l == r) { if ((s[l] >> x) & 1) ++t->sum1; else ++t->sum0; return t; } int mid = ((l + r) >> 1); t->l = build_tree(l, mid, x); t->r = build_tree(mid + 1, r, x); t->count_(); return t; }void reserve(node *t, int l, int r, int L, int R) { if (L <= l && r <= R) { t->mark ^= 1; swap(t->sum0, t->sum1); return; } int mid = ((l + r) >> 1); t->pushdown(); if (mid >= L) reserve(t->l, l, mid, L, R); if (mid < R) reserve(t->r, mid + 1, r, L, R); t->count_(); }int S0, S1; void count(node *t, int l, int r, int L, int R) { if (L <= l && r <= R) { S0 += t->sum0; S1 += t->sum1; return; } t->pushdown(); int mid = ((l + r) >> 1); if (mid >= L) count(t->l, l, mid, L, R); if (mid < R) count(t->r, mid + 1, r, L, R); }int main() { //freopen("a.in", "r", stdin); scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i <= n; ++i) s[i] = (a[i] ^ s[i - 1]); for (int i = 0; i < 15; ++i) rt[i] = build_tree(0, n, i); int p, x, aa, bb, op; while (m--) { scanf("%d", &op); if (op == 1) { scanf("%d%d", &p, &x); for (int i = 0; i < 15; ++i) if (((a[p] >> i) & 1) != ((x >> i) & 1)) { reserve(rt[i], 0, n, p, n); a[p] ^= (1 << i); } } else { scanf("%d%d", &aa, &bb); int ans = 0; for (int i = 0; i < 15; ++i) { S0 = S1 = 0; count(rt[i], 0, n, aa - 1, bb); (ans += 1ll * S0 * S1 % 4001 * (1 << i) % 4001) %= 4001; } printf("%d\n", ans); } }return 0; }

【【KTU|【KTU Programming Camp (Day 3)】Queries】转载于:https://www.cnblogs.com/abclzr/p/9191561.html