Codeforces 1660 D

我是蒟蒻！
我是蒟蒻！
我是蒟蒻！
重要的事情说三遍！

传送门

传送门点这儿！
$ \color{white}{哈哈哈！你被骗了！} $

$ \color{white}{真传送门在上面的感叹号！} $

思路

嗯？一片空白？

最重要的地方：$ a_i \in \{ -2, -1, 0, 1, 2 \} $ ！！
首先为了尽可能大我们肯定不可能有 0 。
所以用双指针的方法处理出 $ [l, r] $ ，$ a_{l}a_{l + 1}a_{l + 2} \cdots a_{r - 1}a_{r} $ 里面不能有 $ 0 $ 。
其次大小从哪里来？$ -2, 2 $ ！
所以我们的乘积就可以变为 $ 2^n $ 或 $ -(2^n) $ ，后面处理 max product 就不会爆了。
最后，如果乘积是负数怎么办？
截取第一个和最后一个范围内的负数，把其中一个弄没就行了。

细节看代码。

代码

#include <bits/stdc++.h>
using namespace std;

int a[200005], pre1[200005], pre2[200005];;

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		memset(pre1, 0, sizeof pre1);
		memset(pre2, 0, sizeof pre2);
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= n; i++) {
			pre1[i] = pre1[i - 1] + (a[i] < 0);
			pre2[i] = pre2[i - 1] + (abs(a[i]) == 2);
		}
		int ans = 0, ans_l = 1, ans_r = 0;
		int l = 1, r = 0;
		while (l <= n) {
			while (l <= n && a[l] == 0) {
				l++;
			}
			if (l > n) {
				break;
			}
			r = l;
			while (r <= n && a[r] != 0) {
				r++;
			}
			r--;
			if ((pre1[r] - pre1[l - 1]) & 1) {
				int nl = l, nr = r;
				while (nl <= n && a[nl] > 0) {
					nl++;
				}
				nl++;
				while (nr >= 1 && a[nr] > 0) {
					nr--;
				}
				nr--;
				if (pre2[r] - pre2[nl - 1] > ans) {
					ans = pre2[r] - pre2[nl - 1];
					ans_l = nl;
					ans_r = r;
				}
				if (pre2[nr] - pre2[l - 1] > ans) {
					ans = pre2[nr] - pre2[l - 1];
					ans_l = l;
					ans_r = nr;
				}
			} else {
				if (pre2[r] - pre2[l - 1] > ans) {
					ans = pre2[r] - pre2[l - 1];
					ans_l = l;
					ans_r = r;
				}
			}
			l = r + 1;
		}
		printf("%d %d\n", ans_l - 1, n - ans_r);
	}
}