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
Sample Input
Sample Output
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#
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 ;
}