RMQ

第一行为两个整数 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的数字序号

数据满足：

$1 \leq n,m \leq 200000$

$1\leq array_i, X \leq 1000000$

$1 \leq L,R \leq n$

C 解法, 执行用时: 1884ms, 内存消耗: 2280K, 提交时间: 2023-01-12 20:26:44

#include<stdio.h>
int main() {
	int n, m, i, L, R, X;
	long long sum;
	char op[4];
	scanf("%d %d", &n, &m);
	int a[n];
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	while (m--) {
		scanf("%s", op);
		if (op[0] == 'S') {
			scanf("%d %d", &L, &R);
			sum = 0;
			for (i = L - 1; i < R; i++) {
				sum += a[i];
			}
			printf("%lld\n", sum);
		} else if (op[0] == 'O') {
			scanf("%d %d %d", &L, &R, &X);
			for (i = L - 1; i < R; i++) {
				a[i] = a[i] | X;
			}
		}
	}
	return 0;
}

C++ 解法, 执行用时: 2082ms, 内存消耗: 2264K, 提交时间: 2021-12-14 10:59:01

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200005];
int main(){
	cin>>n>>m;
	for(int i =1;i<=n;i++){
		cin>>a[i];
	}
	while(m--){
		long long res=0;
		string s;
		int l,r,x;
		cin>>s;
		if(s=="SUM"){
			cin>>l>>r;
			for(int j = l;j<=r;j++) res+=a[j];
			cout<<res<<endl;
			res = 0;
		}
		else{
			cin>>l>>r>>x;
			for(int j = l;j<=r;j++) a[j] = a[j]|x;
		}
	}
	return 0;
}

详情