链接：https://ac.nowcoder.com/acm/contest/283/J
来源：牛客网

对于一个整数数组：    

1. 给定L和R，输出[L,R]中元素的和

2. 给定L，R和X，将[L,R]中每个元素与X进行按位或运算

3. 数组索引从1开始

按位或在C\C++、Java、Python中为'|'运算符
 

输入描述:

第一行为两个整数 n 和 m，表示数组元素个数和操作的次数

第二行有n个整数，第i个表示数组array中第i个元素的值array[i]

接下来m行，每行只有两种可能：

1. SUM L R

表示对[L,R]的元素求和并输出

2. OR L R X

表示对[L,R]的每一个元素与X进行按位或运算，L、R为base 1的数字序号

数据满足：

 

输出描述:

对于每个SUM操作，在一行内输出该操作的结果。

示例1

输入

5 3
1 2 3 4 5
SUM 1 4
OR 2 5 10
SUM 1 4

输出

10
36

说明

在第一个SUM操作时数组a为[1, 2, 3, 4, 5]，因此[1,4]和为10

在第二个SUM操作时数组a为[1, 10, 11, 14, 15]，因此[1,4]和为36

解题思路

读题，线段树裸题，然而由于题量太少，一开始没有想到 或运算 的传递性，赛后看了眼题解，明白是位运算的传递性，注意这里维护的懒惰标记是上一次没有做 或运算的数，所以当需要修改懒惰标记的时候，不应该直接+=，由于这里的关系传递是或运算，所以这里要写成|=，来自菜鸡的补题思路。

Code

#include <iostream>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1
using namespace std;
struct node
{
	int l;
	int r;
	ll sum[25];
	ll mark;//待 或运算的数
}que[200005 * 4];
int ql, qr;
ll val, a[200005];
void up(int k)
{
	for (int i = 0; i < 25; i++)
	{
		que[k].sum[i] = que[k << 1].sum[i] + que[k << 1 | 1].sum[i];
	}
}
void down(int k)
{
	if (que[k].mark)
	{
		que[k << 1].mark |= que[k].mark;
		que[k << 1 | 1].mark |= que[k].mark;
		for (int i = 0; i < 25; i++)
		{
			if (que[k].mark & (1 << i))
			{
				que[k << 1].sum[i] = (que[k << 1].r - que[k << 1].l + 1);
				que[k << 1 | 1].sum[i] = (que[k << 1 | 1].r - que[k << 1 | 1].l + 1);
			}
		}
		que[k].mark = 0;
	}
}
void build(int left, int right, int k)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	if (left == right)
	{
		for (int i = 0; i < 25; i++)
		{
			if (a[left] & (1 << i))
				que[k].sum[i] = 1;
			else
				que[k].sum[i] = 0;
		}
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update(int left, int right, int k)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		for (int i = 0; i < 25; i++)
			if ((1 << i)&val)
				que[k].sum[i] = que[k].r - que[k].l + 1;
		que[k].mark |= val;
		return;
	}
	imid;
	down(k);
	update(lson);
	update(rson);
	up(k);
}
ll query(int left, int right, int k)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
	{
		ll ans = 0;
		for (int i = 0; i < 25; i++)
			ans += que[k].sum[i] * (1 << i);
		return ans;
	}
	imid;
	down(k);
	return query(lson) + query(rson);
}
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	build(1, n, 1);
	char op[10];
	while (m--)
	{
		scanf("%s", op);
		if (op[0] == 'S')
		{
			scanf("%d%d", &ql, &qr);
			printf("%lld\n", query(1, n, 1));
		}
		else
		{
			scanf("%d%d%lld", &ql, &qr, &val);
			update(1, n, 1);
		}
	}
}