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?

给定N个整数A={A[0],A[1],...,A[N-1]}。下面有一些操作。

操作1：AND opn L R

其中opn，L和R都是整数。

对于L≤i≤R，我们使A[i]=A[i] AND opn（这里的"AND"是位运算）。

操作2：OR opn L R

其中opn，L和R都是整数。

对于L≤i≤R，我们使A[i]=A[i] OR opn（这里的"OR"是位运算）。

操作3：XOR opn L R

其中opn，L和R都是整数。

对于L≤i≤R，我们使A[i]=A[i] XOR opn（这里的"XOR"是位运算）。

操作4：SUM L R

我们想要知道A[L]+A[L+1]+...+A[R]的值。

现在，你能解决这个简单的问题吗？

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)

第一行有一个整数T，表示测试样例的数量。(T≤100)

后面有T个样例，每个样例的第一行有2个整数n和m(1≤n≤1,000,000, 1≤m≤100,000)，表示元素数量与操作次数。

下一行有n个整数A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n)。

接着m行，每行都是上述4种操作的其中一个。(0≤opn≤15)

Output	输出
For each test case and for each "SUM" operation, please output the result with a single line.	对于每个测试样例的每个"SUM"操作，都要输出到单独的一行。

Sample Input - 输入样例

Sample Output - 输出样例

4 4

1 2 4 7

SUM 0 2

XOR 5 0 0

OR 6 0 3

SUM 0 2

【题解】

　　单纯的线段树。

　　利用线段树查找快速的特点保存元素，对于某段区间内相同状态的元素进行合并。

　　进行操作的时候不断查找，直到可操作的区间。因为数据都是非负整数，所以可以用负数标记元素不同的区间。

　　PS：状态发生变化的时候都要下压，注意深入的方向。

　　PS2：简单的运算速度是高于开辟空间的速度，所以没必要把线段树每个节点的左右区间都记录下来。

　　PSP：开辟元素数量4倍的空间一定够用。

【代码 C++】

 1 #include<cstdio>
 2 int data[1000000 << 4], opn, L, R;
 3 char ts[5];
 4 int build(int data_i, int L, int R){//[L, R]
 5     if (L == R) scanf("%d", &data[data_i]);
 6     else{
 7         int mid = (L + R) >> 1;// [L, mid]  (mid, R]
 8         L = build(data_i << 1 | 1, L, mid);
 9         R = build(data_i + 1 << 1, mid + 1, R);
10         if (L == R) data[data_i] = L;
11         else data[data_i] = -1;
12     }
13     return data[data_i];
14 }
15 int bitwise_peration(int data_i, int L_now, int R_now){
16     if (data[data_i] != -1 && L <= L_now && R_now <= R){
17         if (*ts == 'A') data[data_i] &= opn;
18         else if (*ts == 'O') data[data_i] |= opn;
19         else if (*ts == 'X') data[data_i] ^= opn;
20     }
21     else{
22         if (data[data_i] != -1) data[data_i << 1 | 1] = data[data_i + 1 << 1] = data[data_i];
23         int mid = (R_now + L_now) >> 1;
24         if (R <= mid){// goto Right
25             L_now = bitwise_peration(data_i << 1 | 1, L_now, mid);
26             R_now = data[data_i + 1 << 1];
27         }
28         else if (mid < L){// goto Left
29             L_now = data[data_i << 1 | 1];
30             R_now = bitwise_peration(data_i + 1 << 1, mid + 1, R_now);
31         }
32         else{
33             L_now = bitwise_peration(data_i << 1 | 1, L_now, mid);
34             R_now = bitwise_peration(data_i + 1 << 1, mid + 1, R_now);
35         }
36         if (L_now == R_now) data[data_i] = L_now;
37         else data[data_i] = -1;
38     }
39     return data[data_i];
40 }
41 int sum(int data_i, int L_now, int R_now){
42     if (data[data_i] != -1 && L <= L_now && R_now <= R){
43         return data[data_i] * (R_now - L_now + 1);
44     }
45     if (data[data_i] != -1) data[data_i << 1 | 1] = data[data_i + 1 << 1] = data[data_i];
46     int mid = (R_now + L_now) >> 1;
47     if (R <= mid) return sum(data_i << 1 | 1, L_now, mid);
48     if (mid < L) return sum(data_i + 1 << 1, mid + 1, R_now);
49     return sum(data_i << 1 | 1, L_now, mid) + sum(data_i + 1 << 1, mid + 1, R_now);
50 }
51 int main(){
52     int t, m, n, i;
53     for (scanf("%d", &t); t; --t){
54         scanf("%d%d", &n, &m);
55         --n;
56         build(0, 0, n);
57         while (m--){
58             scanf("%s", ts);
59             if (*ts == 'S'){
60                 scanf("%d%d", &L, &R);
61                 printf("%d
", sum(0, 0, n));
62             }
63             else{
64                 scanf("%d%d%d", &opn, &L, &R);
65                 bitwise_peration(0, 0, n);
66             }
67         }
68     }
69     return 0;
70 }

 1 #include<cstdio>
 2 int L, R;
 3 char data[2097149], opn, ts[5];
 4 int read_g(){// 输入挂
 5     int add = getchar() - '0';
 6     int a = getchar();
 7     while (a >= '0' && a <= '9') add = add * 10 + a - '0', a = getchar();
 8     return add;
 9 }
10 int build(int data_i, int L, int R){// [L, R]
11     if (L == R) data[data_i] = read_g();
12     else{// [L, mid]  (mid, R]
13         int mid = (L + R) >> 1;
14         L = build(data_i << 1 | 1, L, mid);
15         R = build(data_i + 1 << 1, ++mid, R);
16         if (L == R) data[data_i] = L;
17         else data[data_i] = -1;
18     }
19     return data[data_i];
20 }
21 int bitwise_peration(int data_i, int L_now, int R_now){
22     if (~data[data_i] && L <= L_now && R_now <= R){
23         if (*ts == 'A') data[data_i] &= opn;
24         else if (*ts == 'O') data[data_i] |= opn;
25         else if (*ts == 'X') data[data_i] ^= opn;
26     }
27     else{
28         if (~data[data_i]) data[data_i << 1 | 1] = data[data_i + 1 << 1] = data[data_i];
29         int mid = (R_now + L_now) >> 1;
30         if (R <= mid){// goto Right
31             L_now = bitwise_peration(data_i << 1 | 1, L_now, mid);
32             R_now = data[data_i + 1 << 1];
33         }
34         else if (mid < L){// goto Left
35             L_now = data[data_i << 1 | 1];
36             R_now = bitwise_peration(data_i + 1 << 1, mid + 1, R_now);
37         }
38         else{
39             L_now = bitwise_peration(data_i << 1 | 1, L_now, mid);
40             R_now = bitwise_peration(data_i + 1 << 1, mid + 1, R_now);
41         }
42         if (L_now == R_now) data[data_i] = L_now;
43         else data[data_i] = -1;
44     }
45     return data[data_i];
46 }
47 int sum(int data_i, int L_now, int R_now){
48     if (~data[data_i]){
49         if (L_now < L) L_now = L;
50         if (R < R_now) R_now = R;
51         return data[data_i] * (++R_now - L_now);
52     }
53     int mid = (R_now + L_now) >> 1;
54     if (R <= mid) return sum(data_i << 1 | 1, L_now, mid);
55     if (mid < L) return sum(++data_i << 1, ++mid, R_now);
56     return sum(data_i << 1 | 1, L_now, mid) + sum(data_i + 1 << 1, mid + 1, R_now);
57 }
58 int main(){
59     int m, n;
60     short t = read_g();
61     while (t--){
62         n = read_g(); m = read_g(); --n;
63         build(0, 0, n);
64         while (m--){
65             scanf("%s", ts); getchar();
66             if (*ts == 'S'){
67                 L = read_g(); R = read_g();
68                 printf("%d
", sum(0, 0, n));
69             }
70             else{
71                 opn = read_g(); L = read_g(); R = read_g();
72                 bitwise_peration(0, 0, n);
73             }
74         }
75     }
76     return 0;
77 }

FZU 2105