FZU 2105 Digits Count

Description:

Given N integers A={A[0],A[1],...,A[N-1]}. Here we have some operations:

Operation 1: AND opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] AND opn (here "AND" is bitwise operation).

Operation 2: OR opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] OR opn (here "OR" is bitwise operation).

Operation 3: XOR opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] XOR opn (here "XOR" is bitwise operation).

Operation 4: SUM L R

We want to know the result of A[L]+A[L+1]+...+A[R].

Now can you solve this easy problem?

Input:

The first line of the input contains an integer T, indicating the number of test cases. (T≤100)

Then T cases, for any case, the first line has two integers n and m (1≤n≤1,000,000, 1≤m≤100,000), indicating the number of elements in A and the number of operations.

Then one line follows n integers A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n).

Then m lines, each line must be one of the 4 operations above. (0≤opn≤15)

Output:

For each test case and for each "SUM" operation, please output the result with a single line.

Sample Input:

1
4 4
1 2 4 7
SUM 0 2
XOR 5 0 0
OR 6 0 3
SUM 0 2

Sample Output:

7
18

Hint:

A = [1 2 4 7]

SUM 0 2, result=1+2+4=7;

XOR 5 0 0, A=[4 2 4 7];

OR 6 0 3, A=[6 6 6 7];

SUM 0 2, result=6+6+6=18.

题目链接

题目要求对一数列支持 $4$ 种操作:

  1. SUM l r 求 $ \sum_{i=l}^{r}a_{i} $
  2. AND opn l r $ \forall a_i (i \in [l,r]) a_i=a_i \& opn $
  3. OR opn l r $ \forall a_i (i \in [l,r]) a_i=a_i|opn $
  4. XOR opn l r $ \forall a_i (i \in [l,r]) a_i=a_i \oplus opn $

题目数组元素范围很小 $ \forall a_i (i \in [1,n]) a_i \in [0,16] $ ,所以我们可以对二进制下 $1 \sim 4$ 位每位建立一棵线段树

修改时对于 $AND$ 操作对于 $opn$ 每为 $0$ 的位在数列区间 $[l,r]$ 中对每个数的此位修改为 $0$

对于 $OR$ 操作对于 $opn$ 每为 $1$ 的位在数列区间 $[l,r]$ 中对每个数的此位修改为 $1$

对于 $XOR$ 操作就是普通的线段树异或操作修改

询问时在区间中对每个区间的每一位按位加和

AC代码:

#include <cstdio>
const int maxn = 1e6 + 5;
const int maxdigit = 4;
struct SegTree {
  int n;
  int sum[maxdigit][maxn * 4];
  int lazy[maxdigit][maxn * 4];
  bool rev[maxdigit][maxn * 4];
  void Push(int o, int l, int r, int dgt) {
    int m = (l + r) / 2;
    if (lazy[dgt][o] != -1) {
      int f = lazy[dgt][o];
      if (f) {
        sum[dgt][o * 2] = m - l + 1;
        sum[dgt][o * 2 + 1] = r - m;
        lazy[dgt][o * 2] = lazy[dgt][o * 2 + 1] = 1;
        rev[dgt][o * 2] = rev[dgt][o * 2 + 1] = 0;
      }
      else {
        sum[dgt][o * 2] = sum[dgt][o * 2 + 1] = 0;
        lazy[dgt][o * 2] = lazy[dgt][o * 2 + 1] = 0;
        rev[dgt][o * 2] = rev[dgt][o * 2 + 1] = 0;
      }
      lazy[dgt][o] = -1;
    }
    if (rev[dgt][o] != 0) {
      sum[dgt][o * 2] = m - l + 1 - sum[dgt][o * 2];
      sum[dgt][o * 2 + 1] = r - m - sum[dgt][o * 2 + 1];
      rev[dgt][o * 2] ^= 1;
      rev[dgt][o * 2 + 1] ^= 1;
      rev[dgt][o] = 0;
    }
  }
  void Build(int o, int l, int r, int arr[]) {
    for (int dgt = 0; dgt < maxdigit; ++dgt) {
      lazy[dgt][o] = -1;
      rev[dgt][o] = 0;
    }
    if (l == r) {
      for (int dgt = 0; dgt < maxdigit; ++dgt) sum[dgt][o] = (bool)(arr[l] & (1 << dgt));
      return;
    }
    int m = (l + r) / 2;
    Build(o * 2, l, m, arr);
    Build(o * 2 + 1, m + 1, r, arr);
    for (int dgt = 0; dgt < maxdigit; ++dgt) sum[dgt][o] = sum[dgt][o * 2] + sum[dgt][o * 2 + 1];
  }
  void Init(int _n, int arr[]) {
    n = _n;
    Build(1, 1, n, arr);
  }
  void Modify(int o, int l, int r, int ll, int rr, int dgt, int f) {
    if (ll <= l && rr >= r) {
      if (f == 1) {
        sum[dgt][o] = lazy[dgt][o] = rev[dgt][o] = 0;
      }
      else if (f == 2) {
        sum[dgt][o] = r - l + 1;
        lazy[dgt][o] = 1;
        rev[dgt][o] = 0;
      }
      else if (f == 3) {
        sum[dgt][o] = r - l + 1 - sum[dgt][o];
        rev[dgt][o] ^= 1;
      }
      return;
    }
    Push(o, l, r, dgt);
    int m = (l + r) / 2;
    if (ll <= m) Modify(o * 2, l, m, ll, rr, dgt, f);
    if (rr > m) Modify(o * 2 + 1, m + 1, r, ll, rr, dgt, f);
    sum[dgt][o] = sum[dgt][o * 2] + sum[dgt][o * 2 + 1];
  }
  void Modify(int ll, int rr, int dgt, int f) {
    Modify(1, 1, n, ll, rr, dgt, f);
  }
  int Query(int o, int l, int r, int ll, int rr) {
    if (ll <= l && rr >= r) {
      int ret = 0;
      for (int dgt = maxdigit - 1; dgt >= 0; --dgt) ret = (ret << 1) + sum[dgt][o];
      return ret;
    }
    for (int dgt = 0; dgt < maxdigit; ++dgt) Push(o, l, r, dgt);
    int m = (l + r) / 2, ret = 0;
    if (ll <= m) ret += Query(o * 2, l, m, ll, rr);
    if (rr > m) ret += Query(o * 2 + 1, m + 1, r, ll, rr);
    return ret;
  }
  int Query(int ll, int rr) {
    return Query(1, 1, n, ll, rr);
  }
};
int t;
int n, m;
int a[maxn];
SegTree tree;
int main() {
  scanf("%d", &t);
  for (int cas = 1; cas <= t; ++cas) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    tree.Init(n, a);
    for (int i = 1; i <= m; ++i) {
      char op[4];
      scanf("%s", op);
      if (op[0] == 'S') {
        int l, r;
        scanf("%d%d", &l, &r);
        ++l; ++r;
        printf("%d\n", tree.Query(l, r));
      }
      else if (op[0] == 'A') {
        int opn, l, r;
        scanf("%d%d%d", &opn, &l, &r);
        ++l; ++r;
        for (int dgt = 0; dgt < maxdigit; ++dgt) {
          if (!(opn & (1 << dgt))) tree.Modify(l, r, dgt, 1);
        }
      }
      else if (op[0] == 'O') {
        int opn, l, r;
        scanf("%d%d%d", &opn, &l, &r);
        ++l; ++r;
        for (int dgt = 0; dgt < maxdigit; ++dgt) {
          if (opn & (1 << dgt)) tree.Modify(l, r, dgt, 2);
        }
      }
      else if (op[0] == 'X') {
        int opn, l, r;
        scanf("%d%d%d", &opn, &l, &r);
        ++l; ++r;
        for (int dgt = 0; dgt < maxdigit; ++dgt) {
          if (opn & (1 << dgt)) tree.Modify(l, r, dgt, 3);
        }
      }
    }
  }
  return 0;
}
Last modification:September 13th, 2019 at 02:10 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment