Digits Count（线段树）

 

Problem 2105 Digits Count

Accept: 144    Submit: 865
Time Limit: 10000 mSec    Memory Limit : 262144 KB

 

Problem 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.

 

 

       题意：

       给出 T （1 ~ 100）组 case，每组 case 给出 N（1 ~ 1000000），M（1 ~ 100000），代表有 N 个数 ai（0 ~ 16），和 M 个操作。操作有 4 类：

       1、SUM A B 代表将 A 到 B 的数求和；

       2、XOR K A B 代表将 A 到 B 的数异或 K；

       3、OR K A B 代表将 A 到 B 的数或 K；

       4、AND K A B 代表将 A 到 B 的数与 K；

       输出所有 SUM 操作时候的结果。

 

       思路：

       线段树 + 区间操作。将每个数拆位后每位建线段树，数最大才 16 所以建 4 颗线段树即可。

       与 CF 那题不同的是多了 OR 和 AND 的操作，或 0 的结果是不改变原来状态的，或 1 的结果是所有的数都会变成 1；与 1 的结果是不改变原来的状态的，与 0 的结果是所有的数都会变成 0。那么可以开另外一个标记域标记区间是否被 0 或者 被 1 覆盖的情况，另外一个标记是异或的情况。

       异或标记和覆盖标记是不会同时存在的，oth 标记 -1 代表未被覆盖，0 代表被 0 覆盖，1 代表被 1 覆盖；xor 标记 1 代表相反一次状态，0 代表不改变状态。若这个标记域被 0 或者被 1 覆盖，当异或的时候直接改变覆盖标记即可，其他异或操作和 CF 那题一样。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 1000005;

int n, dim, L, R, res;
int num[MAX];
int tree[5][MAX * 3], flag_xor[5][MAX * 3], flag_oth[5][MAX * 3];

void Mark (int k, int l, int r) {
        int mid = (l + r) >> 1;
        if (flag_oth[dim][k] != -1) {
                tree[dim][k << 1] = (mid - l + 1) * flag_oth[dim][k];
                tree[dim][k << 1 | 1] = (r - mid) * flag_oth[dim][k];
                flag_oth[dim][k << 1] = flag_oth[dim][k << 1 | 1] = flag_oth[dim][k];
                flag_xor[dim][k << 1] = flag_xor[dim][k << 1 | 1] = 0;
                flag_oth[dim][k] = -1;
        }

        if (flag_xor[dim][k]) {
                flag_xor[dim][k] = 0;
                tree[dim][k << 1] = mid - l + 1 - tree[dim][k << 1];
                tree[dim][k << 1 | 1] = r - mid - tree[dim][k << 1 | 1];
                if (flag_oth[dim][k << 1] != -1) flag_oth[dim][k << 1] ^= 1;
                else flag_xor[dim][k << 1] ^= 1;
                if (flag_oth[dim][k << 1 | 1] != -1) flag_oth[dim][k << 1 | 1] ^= 1;
                else flag_xor[dim][k << 1 | 1] ^= 1;
        }

}

void Build (int k, int l, int r) {
        int mid = (l + r) >> 1;
        flag_oth[dim][k] = -1;
        flag_xor[dim][k] = 0;
        if (l == r) {
                tree[dim][k] = (num[l] >> dim) & 1;
                return;
        }
        Build(k << 1, l, mid);
        Build(k << 1 | 1, mid + 1, r);
        tree[dim][k] = tree[dim][k << 1] + tree[dim][k << 1 | 1];
}

void Sum (int k, int l, int r) {
        int mid = (l + r) >> 1;
        if (L > r || R < l) return;
        if (L <= l && R >= r) {
                res += tree[dim][k];
                return;
        }
        Mark(k, l, r);
        Sum(k << 1, l, mid);
        Sum(k << 1 | 1, mid + 1, r);
}

void Update (int op, int k, int l, int r) {
        int mid = (l + r) >> 1;
        if (L > r || R < l) return;
        if (L <= l && R >= r) {
                if (op == 1) {
                        tree[dim][k] = r - l + 1 - tree[dim][k];
                        if (flag_oth[dim][k] != -1) flag_oth[dim][k] ^= 1;
                        else flag_xor[dim][k] ^= 1;
                } else if (op == 2) {
                        tree[dim][k] = r - l + 1;
                        flag_xor[dim][k] = 0;
                        flag_oth[dim][k] = 1;
                } else if (op == 3) {
                        tree[dim][k] = 0;
                        flag_xor[dim][k] = 0;
                        flag_oth[dim][k] = 0;
                }
                return;
        }
        Mark(k, l ,r);
        Update(op, k << 1, l, mid);
        Update(op, k << 1 | 1, mid + 1, r);
        tree[dim][k] = tree[dim][k << 1 | 1] + tree[dim][k << 1];
}

int main() {
        int t;
        scanf("%d", &t);
        while (t--) {

                int m;
                scanf("%d%d", &n, &m);
                for (int i = 1; i <= n; ++i)
                        scanf("%d", &num[i]);

                for (dim = 0; dim < 4; ++dim)
                        Build(1, 1, n);

                while (m--) {
                        char s[10];
                        int ans;
                        scanf("%s", s);
                        if (s[0] == 'S') {
                                int sum = 0;
                                scanf("%d%d", &L, &R);
                                ++L, ++R;
                                for (dim = 0; dim < 4; ++dim) {
                                        res = 0;
                                        Sum(1, 1, n);
                                        sum += (res * (1 << dim));
                                }

                                printf("%d\n", sum);

                        } else if (s[0] == 'X') {
                                scanf("%d%d%d", &ans, &L, &R);
                                ++L, ++R;

                                for (dim = 0; dim < 4; ++dim) {
                                        if ((ans >> dim) & 1) Update(1, 1, 1, n);
                                }
                        } else if (s[0] == 'O') {
                                scanf("%d%d%d", &ans, &L, &R);
                                ++L, ++R;
                                for (dim = 0; dim < 4; ++dim) {
                                        if ((ans >> dim) & 1) Update(2, 1, 1, n);
                                }
                        } else if (s[0] == 'A') {
                                scanf("%d%d%d", &ans, &L, &R);
                                ++L, ++R;
                                for (dim = 0; dim < 4; ++dim)
                                        if (!((ans >> dim) & 1)) Update(3, 1, 1, n);
                        }
                }
        }
        return 0;
}