P8563 Magenta Potion

· · 个人记录

P8563 Magenta Potion

进入正题【doge】

本题一眼就是线段树，但是其实仔细一读，这道题因为存在“Too large”用暴力枚举即可。

怎样寻找乘积最大的子区间？

题目要求输出[l,r]之间的最大乘积子区间,我们可以分类讨论

首先，如果区间中的奇数的个数是偶数个（3 ，-2 ， 9 ， -4 ， 3），因为负负得正

所以 奇数的个数是偶数个时 最大乘积一定是 所有数的乘积

如果, 如果区间中的奇数的个数是奇数个（-3 ，-2 ， 9 ， -4 ， 3）

只需要删除一个奇数，乘积就会为 正数；

答案一定是把最左（右）边的负数除掉（本例中就是删除左边的（-3）或者右边的（-4 ， 3））

我们只去要暴力枚举从 a_l到第一个负数 和 最后一个负数 到 a_r 的乘积 选取 绝对值 小的区间删去（本样例 为 删除 -3）

所以 奇数的个数是奇数个时 删除 a_l到第一个负数 和 最后一个负数 中 乘积绝对值小的一段

为什么暴力就可以实现？

读题发现 因为 |a _ i| 必定 > 2

而M > 2 ^ {30}时 就需要输出 “Too large”。

那么暴力就成为了可能。

我们举一种最极端的例子（对于所有的|a_i| = 2），那需要达到“Too large” 就至少需要 30 个数（2 ^ {30}）

但本题还会存在负数的情况 , 因为我们只能从两边删除数字 所以为了让结果减小对多， 我们让负数在最中间

如下表格：

为了让最终的结果最大，我们必定会删除一半的数

a_1 - a_{mid}$ 或 $a_{mid}-a_n

删除任意一半都会留下 剩下 的 n - mid 个 2 (mid = \lceil n /2\rceil)

\because2 ^ {n - mid} > 2 ^ {30}

\therefore n - mid > 30

\therefore n - \lceil n /2\rceil > 30h

\therefore n > 62 所以 n (q_i.r - q_i.l + 1) > 62 时 必定输出“Too large”

*呢么我们就可以发现 实际我们 需要的时间复杂度是$O(60 n)$**

代码实现

本题有 2 种操作

对于 操作1 需要单点修改 因为我们用暴力求解所以只需要用数组存数，单点修改直接赋值即可

对于 操作2 求出区间乘积最大的子序列 前面我们已经证明过寻找的方法即：

奇数的个数是偶数个时 最大乘积一定是 所有数的乘积

奇数的个数是奇数个时 删除 a_l到第一个负数 和 最后一个负数 中 乘积绝对值小的一段

先判断 会不会超过 范围

if(r - l > 63) {cout << "Too large\n"; continue;}

如果可能出现小于等于2 ^ {30}时，再暴力算出乘积

__int128 fi_neg = 0 ,fi_sum = 1 , la_sum = 1, Sum = 1 , f = 0;
// fi_sum 为前半段乘积 la_sum 为后半段乘积 Sum 为 总乘积
// f 为 Sum 真实值 为 '正' 还是 '负'
// fi_neg 记录是否出现过第一个负数
for(int i = l;i <= r;++ i){ 
    Sum *= a[i];
    if(a[i] < 0) f ^= 1; 
// f 初值为 1 , 1 ^ 1 = 0 , 0 ^ 1 = 1
// 这里实现了 用 f 记录是否为正数
    if(!fi_neg && a[i] < 0) fi_neg = i , fi_sum *= a[i];
    if(!fi_neg) fi_sum *= a[i];
    if(a[i] < 0) la_sum = Sum / a[i];
}
__int128 ans = -1;
if(la_sum)la_sum = Sum / la_sum;

再按顺序判断

注： 本题开int128 也会焯范围，但是因为int128 比较大所以不会再次溢出成为正数。\ 所以在答案一定为正的时候记录了负数说明溢出了（真实值>2^{128}）

if(Sum < 0 && !f){cout << "Too large\n"; continue;} // 防止溢出
if(Sum > (1ll << 30)){cout << "Too large\n"; continue;} 
// 为正数且超范围
if(Sum > 0){write(Sum); cout << "\n";continue;} 
// 为整数且不超范围
if(la_sum) ans = max(Sum / la_sum , ans);
if(fi_sum) ans = max(Sum / fi_sum , ans);
// 计算删除前（后）半段的最大值
if(ans > (1ll << 30)){cout << "Too large\n"; continue;}
// 超范围
write(max((__int128)1 , ans));cout << "\n";
// 不超范围

注：本代码用到了__int128，输出时要用 '快写’;因为本题没有输出负数的情况所以不需要管x的正负

inline void write(__int128 x){
    if(x > 9)
        write(x/10);//上一位
    putchar(x % 10 + '0');//取出来这一位然后putchar
}

讲解结束【doge】上AC代码

#include<bits/stdc++.h>
using namespace std;
#define xztx main 
#define ll long long
#define Mod 
int n , q;
ll a[2000020];
inline void write(__int128 x){
    if(x > 9)
        write(x/10);
    putchar(x % 10 + '0');
}
void Init(){
    cin >> n >> q;
    for(int i = 1;i <= n;++ i)
        cin >> a[i];
}
int xztx(){
    Init();
    for(int k = 1;k <= q;++ k){
        int op , l , r;
        cin >> op >> l >> r;
        if(op - 1){
            if(r - l >= 63) {cout << "Too large\n"; continue;}
            __int128 fi_neg = 0 ,fi_sum = 1 , la_sum = 1, Sum = 1 , f = 0; 
            for(int i = l;i <= r;++ i){ 
                Sum *= a[i];
                if(a[i] < 0) f ^= 1;
                if(!fi_neg && a[i] < 0) fi_neg = i , fi_sum *= a[i];
                if(!fi_neg) fi_sum *= a[i];
                if(a[i] < 0) la_sum = Sum / a[i];
            }                   
            __int128 ans = -1;
            if(la_sum)la_sum = Sum / la_sum;        
            if(Sum < 0 && !f){cout << "Too large\n"; continue;}
            if(Sum > (1ll << 30)){cout << "Too large\n"; continue;} 
            if(Sum > 0){write(Sum); cout << "\n";continue;} 
            if(la_sum) ans = max(Sum / la_sum , ans);
            if(fi_sum) ans = max(Sum / fi_sum , ans);
            if(ans > (1ll << 30)){cout << "Too large\n"; continue;}
            write(max((__int128)1 , ans));cout << "\n";
        } else a[l] = r;
    }
    return 0;
}