題意：對一串?dāng)?shù)字進行抑或某數(shù)，和某數(shù)，或某數(shù)，統(tǒng)計某區(qū)間和的操作。

思路：因為化成二進制就4位可以建4顆線段樹，每顆代表一位二進制。

and 如果該為是1 ?直接無視，是0則成段賦值為0；

or ?如果是0 無視，是1則成段賦值為1；

xor 成段亦或，1個數(shù)和0個數(shù)交換；

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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/L-Ecry/p/3879576.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的FOJ 2105 Digits Count的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。