FZU 2105Digits 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.

大神说，经过若干次的操作就会出现很多相同的，然后懒惰标记就用来记做这个区间又没用相同的

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <cstring>
  5 using namespace std;
  6 typedef long long LL;
  7 const int Max = 1000000 + 10;
  8 int n, m;
  9 struct Node
 10 {
 11     int l, r;
 12     int num;
 13 };
 14 Node node[Max * 4];
 15 int A[Max];
 16 void buildtree(int l, int r, int k)
 17 {
 18     node[k].l = l;
 19     node[k].r = r;
 20     node[k].num = -1;
 21     if (l == r)
 22     {
 23         node[k].num = A[l];
 24         return;
 25     }
 26     int mid = (l + r) / 2;
 27     buildtree(l, mid, k * 2);
 28     buildtree(mid + 1, r, k * 2 + 1);
 29     if (node[k * 2].num >= 0 && node[k * 2].num == node[k * 2 + 1].num) // 如果左边区间和右边区间 num 相同，就要更改父节点
 30     {
 31         node[k].num = node[k * 2].num;
 32     }
 33 }
 34 int getopt(int num, int opn, int opt)
 35 {
 36     if (opt == 1)
 37         return opn & num;
 38     if (opt == 2)
 39         return opn | num;
 40     if (opt == 3)
 41         return (opn ^ num);
 42     return 0;
 43 }
 44 void update(int l, int r, int k, int opn, int opt)
 45 {
 46     if (node[k].l == l && node[k].r == r && node[k].num >= 0)
 47     {
 48        // 区间【l, r】上的数是相同的，只需改一次就ok了
 49         node[k].num = getopt(node[k].num, opn, opt);
 50         return;
 51     }
 52    // 不相同的话就继续往左右两边改
 53     if (node[k].num >= 0)  // 在改的过程中发现该点标记过，分给子节点，去掉自己的标记
 54     {
 55         node[k * 2].num = node[k * 2 + 1].num = node[k].num;
 56         node[k].num = -1;
 57     }
 58     int mid = (node[k].l + node[k].r) / 2;
 59     if (r <= mid)
 60         update(l, r, k * 2, opn, opt);
 61     else if (mid < l)
 62     {
 63         update(l, r, k * 2 + 1, opn, opt);
 64     }
 65     else
 66     {
 67         update(l, mid, k * 2, opn, opt);
 68         update(mid + 1, r, k * 2 + 1, opn, opt);
 69     }
 70     if (node[k * 2].num >= 0 && node[k * 2].num == node[k * 2 + 1].num)
 71         node[k].num = node[k * 2].num;
 72 }
 73 LL querry(int l, int r, int k)
 74 {
 75     if (node[k].l == l && node[k].r == r && node[k].num >= 0)
 76     {
 77         return (LL) node[k].num * (LL) (node[k].r - node[k].l + 1);
 78     }
 79     if (node[k].num >= 0)
 80     {
 81         node[k * 2].num = node[k * 2 + 1].num = node[k].num;
 82         node[k].num = -1;
 83     }
 84     int mid = (node[k].r + node[k].l) / 2;
 85     if (r <= mid)
 86     {
 87         return querry(l, r, k * 2);
 88     }
 89     else if (mid < l)
 90     {
 91         return querry(l, r, k * 2 + 1);
 92     }
 93     else
 94         return querry(l, mid, k * 2) + querry(mid + 1, r, k * 2 + 1);
 95 }
 96 int main()
 97 {
 98     int t;
 99     scanf("%d", &t);
100     while (t--)
101     {
102         scanf("%d%d", &n, &m);
103         for (int i = 1; i <= n; i++)
104             scanf("%d", &A[i]);
105         buildtree(1, n, 1);
106         while (m--)
107         {
108             char opt[5];
109             int opn, a, b;
110             scanf("%s", opt);
111             if (opt[0] == 'S')
112             {
113                 scanf("%d%d", &a, &b);
114                 printf("%I64d
", querry(a + 1, b + 1, 1));
115             }
116             else
117             {
118                 scanf("%d%d%d", &opn, &a, &b);
119                 if (opt[0] == 'A')
120                 {
121                     update(a + 1, b + 1, 1, opn, 1);
122                 }
123                 else if (opt[0] == 'O')
124                 {
125                     update(a + 1, b + 1, 1, opn, 2);
126                 }
127                 else
128                     update(a + 1, b + 1, 1, opn, 3);
129             }
130         }
131     }
132     return 0;
133 }

View Code