P8563 Magenta Potion

题目描述

给定一个长为 $n$ 的整数序列 $a$，其中所有数的绝对值均大于等于 $2$。有 $q$ 次操作，格式如下：

$\text{1 i k}$，表示将 $a_i$ 修改为 $k$。保证 $k $ 的绝对值大于等于 $2$。

$\text{2 l r}$，考虑 $[l,r]$ 的子区间（包括本身）中乘积最大的的区间乘积 $M$。如果 $M>2^{30}$，输出 Too large，否则输出 $M$。特别地，空区间的元素乘积定义为 $1$。

输入格式

第一行两个正整数表示 $n,q$。

第二行输入 $n$ 个整数表示 $a_i$。

接下来 $q$ 行，每行三个整数表示一次询问，格式见上。

输出格式

对于每次 $2$ 操作输出一行表示询问的答案。

输入输出样例 #1

输入 #1

5 7
2 2 3 4 5
2 1 5
1 3 -3
2 1 5
2 3 3
1 1 100000
1 2 100000
2 1 2

输出 #1

240
20
1
Too large

说明/提示

对于所有的数据，$2\le |a_i|,|k|\le 10^9$，$1\le n,q\le 2\times 10^5$，$1\le l\le r\le n$。

$$\begin{array}{ccc}\text{测试点编号}& \mathbf{n},\mathbf{q}\le & \text{特殊限制}\\ \text{1}\sim 2& 10& \\ 3\sim 6& 100& \\ 7\sim 10& 5\times 10^3& \\ 11\sim 13& & \mathsf{A}\\ 14\sim 16& & \mathsf{B}\\ 17\sim 20& & \end{array}$$

$\text{A}$：保证 $a_i,k\ge 2$。

$\text{B}$：保证对于每一组询问，对应的 $r-l\ge 100$。

C++实现

#include <bits/stdc++.h>
#define ll long long
#define inf 1<<30
using namespace std;
int n, q;
ll arr[200005];

int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	while (q--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1)
			arr[x] = y;
		else {
			if (x == y && arr[x] < 0)
				cout << 1 << endl;
			else {
				if (y - x + 1 > 61)
					cout << "Too large" << endl;
				else {
					int cnt = 0;
					for (int i = x; i <= y; i++)
						if (arr[i] < 0)
							cnt++;
					if (cnt % 2 == 0) {
						ll res = 1;
						for (int i = x; i <= y && res <= inf; i++)
							res *= abs(arr[i]);
						if (res > inf)
							cout << "Too large" << endl;
						else
							cout << res << endl;
					} else {
						int l = x, r = y;
						while (arr[l] > 0 && l <= y)
							l++;
						while (arr[r] > 0 && r >= x)
							r--;
						ll res1 = 1, res2 = 1;
						for (int i = l + 1; i <= y && res1 <= inf; i++)
							res1 *= abs(arr[i]);
						for (int i = x; i < r && res2 <= inf; i++)
							res2 *= abs(arr[i]);
						if (res1 > inf || res2 > inf)
							cout << "Too large" << endl;
						else
							cout << max(res1, res2) << endl;
					}
				}
			}
		}
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容