|
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 - 输出样例 |
|
1 4 4 1 2 4 7 SUM 0 2 XOR 5 0 0 OR 6 0 3 SUM 0 2 |
7 18
|
【题解】
单纯的线段树。
利用线段树查找快速的特点保存元素，对于某段区间内相同状态的元素进行合并。
进行操作的时候不断查找，直到可操作的区间。因为数据都是非负整数，所以可以用负数标记元素不同的区间。
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\n", 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 }
原文：http://www.cnblogs.com/Simon-X/p/5202396.html