fzu 2105 Digits Count ( 线段树 ) from 第三届福建省大学生程序设计竞赛

http://acm.fzu.edu.cn/problem.php?pid=2105

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.

Source

“高教社杯”第三届福建省大学生程序设计竞赛

【题解】：

　　　　这题思路想到经过多次操作之后的区间应该是一个数字很多相同的区间：

　　因为如果相邻两个数经过操作之后变成相同的数了，那么再经过覆盖了该区间的操作时，那么他们的值将同时发生改变，变成另外一个相同的值，这多次操作下去，之后将生更多的相同的数字区间，这里的相同数字就是懒惰标记更新的关键：例如:OR 6 0 3, A=[6 6 6 7]; 其中6出现了3次

详见代码：

【code】：

 /**

 status:Accepted     language:Visual C++

 time:1953 ms   memory:47156KB

 code length:2686B   author:cj

 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define N 1000010

 #define lson p<<1

 #define rson p<<1|1

 using namespace std;

 struct Nod

 {

     int l,r;

     int num;  //标记区间数字是否相同

 }node[N<<];

 void building(int l,int r,int p)

 {

     node[p].l = l;

     node[p].r = r;

     node[p].num = -;

     if(l==r)

     {

         scanf("%d",&node[p].num);

         return;

     }

     int mid = (l+r)>>;

     building(l,mid,lson);

     building(mid+,r,rson);

     if(node[lson].num!=-&&node[lson].num==node[rson].num)  //向上更新

     {

         node[p].num = node[lson].num;

     }

 }

 int opreate(int op,int opn,int num)  //操作函数 op：操作符 opn，num：操作数

 {

     if(op==)   return opn&num;

     if(op==)   return opn|num;

     if(op==)   return opn^num;

 }

 void update(int l,int r,int p,int opn,int op)

 {

     if(node[p].l==l&&node[p].r==r&&node[p].num>=)  //当找到区间并且区间被相同的数覆盖

     {

         node[p].num = opreate(op,opn,node[p].num);

         return;

     }

     if(node[p].num>=) //经过该区间时，向下更新

     {

         node[lson].num = node[rson].num = node[p].num;

         node[p].num = -;

     }

     int mid = (node[p].l+node[p].r)>>;

     if(r<=mid)  update(l,r,lson,opn,op);

     else if(l>mid)  update(l,r,rson,opn,op);

     else

     {

         update(l,mid,lson,opn,op);

         update(mid+,r,rson,opn,op);

     }

     if(node[lson].num!=-&&node[lson].num==node[rson].num)  //向上更新

     {

         node[p].num = node[lson].num;

     }

 }

 __int64 query(int l,int r,int p)

 {

     if(node[p].l==l&&node[p].r==r&&node[p].num>=)

     {

         return node[p].num*(node[p].r-node[p].l+);

     }

     if(node[p].num>=)  //经过该区间时，向下更新

     {

         node[lson].num = node[rson].num = node[p].num;

         node[p].num = -;

     }

     int mid = (node[p].l+node[p].r)>>;

     if(r<=mid)  return query(l,r,lson);

     else if(l>mid)  return query(l,r,rson);

     else return query(l,mid,lson)+query(mid+,r,rson);

     if(node[lson].num!=-&&node[lson].num==node[rson].num)  //向上更新

     {

         node[p].num = node[lson].num;

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

        int n,m;

        scanf("%d%d",&n,&m);

        char op[];

        building(,n,);

        while(m--)

        {

             scanf("%s",op);

             int opn,a,b;

             if(op[]=='S')

             {

                 scanf("%d%d",&a,&b);

                 printf("%I64d\n",query(a+,b+,));

             }

             else

             {

                 scanf("%d%d%d",&opn,&a,&b);

                 if(op[]=='A')  update(a+,b+,,opn,);

                 else if(op[]=='O')  update(a+,b+,,opn,);

                 else if(op[]=='X')  update(a+,b+,,opn,);

             }

        }

     }

     return ;

 }

fzu 2105 Digits Count ( 线段树 ) from 第三届福建省大学生程序设计竞赛

Input

Output

Sample Input

Sample Output

Hint

Source