首页 > 代码库 > FOJ 2105 Digits Count
FOJ 2105 Digits Count
题意：对一串数字进行抑或某数，和某数，或某数，统计某区间和的操作。
思路：因为化成二进制就4位可以建4颗线段树，每颗代表一位二进制。
and 如果该为是1 直接无视，是0则成段赋值为0；
or 如果是0 无视，是1则成段赋值为1；
xor 成段亦或，1个数和0个数交换；
sum 求和；
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include <iostream>#define N 1000050#define debug(x) printf(#x"= %d\n",x);using namespace std;int sum[4][N * 4], flag[4][N * 4], Xor[4][N * 4];int a[N];void pushup(int i, int now) { sum[now][i] = sum[now][i << 1] + sum[now][i << 1 | 1];}void pushdown(int i, int now, int l, int r) { int mid = (l + r) >> 1; if (flag[now][i] != -1) { flag[now][i << 1] = flag[now][i << 1 | 1] = flag[now][i]; sum[now][i << 1] = (mid - l + 1) * flag[now][i]; sum[now][i << 1 | 1] = (r - mid) * flag[now][i]; Xor[now][i << 1] = Xor[now][i << 1 | 1] = 0; flag[now][i] = -1; } if (Xor[now][i]) { Xor[now][i << 1] ^= 1; sum[now][i << 1] = (mid - l + 1) - sum[now][i << 1]; Xor[now][i << 1 | 1] ^= 1; sum[now][i << 1 | 1] = (r - mid) - sum[now][i << 1 | 1]; Xor[now][i] = 0; }}void build(int l, int r, int i, int now) { flag[now][i] = -1; Xor[now][i] = 0; if (l == r) { sum[now][i] = ((a[l] >> now) & 1); return; } int mid = (l + r) >> 1; build(l, mid, i << 1, now); build(mid + 1, r, i << 1 | 1, now); pushup(i, now);}void update(int l, int r, int pl, int pr, int type, int va, int i, int now) { if (l >= pl && r <= pr) { if (type == 1) { sum[now][i] = (r - l + 1) * va; flag[now][i] = va; Xor[now][i] = 0; } else { sum[now][i] = (r - l + 1 - sum[now][i]); Xor[now][i] ^= 1; } return; } pushdown(i, now, l, r); int mid = (l + r) >> 1; if (pl <= mid) update(l, mid, pl, pr, type, va, i << 1, now); if (pr > mid) update(mid + 1, r, pl, pr, type, va, i << 1 | 1, now); pushup(i, now);}int query(int l, int r, int pl, int pr, int i, int now) { if (l >= pl && r <= pr) { return sum[now][i]; } pushdown(i, now, l, r); int mid = (l + r) >> 1; int tmp = 0; if (pl <= mid) tmp += query(l, mid, pl, pr, i << 1, now); if (pr > mid) tmp += query(mid + 1, r, pl, pr, i << 1 | 1, now); pushup(i, now); return tmp;}int main() { int n, m, tt; scanf("%d", &tt); while (tt--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 0; i < 4; ++i) build(1, n, 1, i); while (m--) { char s[10]; scanf(" %s", s); if (strcmp(s, "OR") == 0) { int x, y, z; scanf("%d%d%d", &x, &y, &z); y++; z++; for (int i = 0; i < 4; ++i) { if ((x >> i) & 1) { update(1, n, y, z, 1, 1, 1, i); } } } else if (strcmp(s, "AND") == 0) { int x, y, z; scanf("%d%d%d", &x, &y, &z); y++; z++; for (int i = 0; i < 4; ++i) { if (((x >> i) & 1) == 0) { update(1, n, y, z, 1, 0, 1, i); } } } else if (strcmp(s, "XOR") == 0) { int x, y, z; scanf("%d%d%d", &x, &y, &z); y++; z++; for (int i = 0; i < 4; ++i) { if (((x >> i) & 1)) { update(1, n, y, z, 2, 1, 1, i); } } } else { int x, y; scanf("%d%d", &x, &y); x++; y++; int ans=0; for (int i = 0; i < 4; ++i) { ans+=query(1,n,x,y,1,i)*(1<<i); // debug(ans); } printf("%d\n",ans); } } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。