Magenta Potion 题解

· · 个人记录

题目简述

给定一个长度为 n 的序列 a，每个数的绝对值大于 2。共有 m 次操作，每次可以改变第 k 个数的值，或者查询 a 的某个区间内所有子区间的最大乘积，如果大于 2^{30} 则输出 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

题目传送门：P8563 Magenta Potion

算法标签：树状数组、二分查询、

题目分析

这是一道查询问题，第一个操作很简单就能实现，难点在于第二个询问。注意题目中的疑点，为什么绝对值要大于 2，是否可以与 Too large 联系起来。

先假设所有数字都是正数，那最大值一定是区间内所有数的乘积。同时因为每个数都大于 2，所以只要区间的长度大于 30 就可以直接输出 Too large。 如果小于 30，循环算一遍也无妨，反正都是 O(1)。

有负数怎么办？如果区间内有偶数个负数那就和上面一样，因为最后乘起来一定是正的。而奇数个就需要认真思考一下了，并且我们怎么才能知道一个区间内有几个负数？

关于区间内负数的个数我们很容易联想到树状数组，如果是负数就打个标记，需要注意的是操作一也会改变负数的个数。

顺着这个思路往下想，奇数个负数的话只需要去掉一个负数就行了，可是去掉哪个？有两个选择，去掉最靠右边的或者最靠左边的。哪个才是最佳方案？两边都算一算就行了，反正循环不超过 30 次。而它们的位置可以用树状数组和二分来找到。

code

#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;

ll n,q,a[N];
int tree[N];

void add(int i,int k){
    for(;i<=n;i+=i&-i)tree[i]+=k;
}

int query(int i){
    int res=0;
    for(;i;i-=i&-i)res+=tree[i];
    return res;
}

ll mult(int l,int r){ //要保证为正数
    if(r-l+1>30)return 1ll<<31;
    if(r-l+1==0)return 1;
    ll res=1;
    for(int i=l;i<=r;i++){
        res*=a[i];
        if(abs(res)>(1ll<<30))return 1ll<<31;
    }
    return res;
}

int search(int x){
    int l=0,r=n,mid;
    while(l<r){
        mid=(l+r)>>1;
        int res=query(mid);
        if(res<x)l=mid+1;
        else if(res>x)r=mid-1;
        else if(res==x){
            if(query(mid-1)!=x)return mid;
            else r=mid-1;
        }
    }
    return l;
}

int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<0)add(i,1);
    }
    for(int i=1,x,y,z;i<=q;i++){
        cin>>x>>y>>z;
        if(x==1){
            if(z<0&&a[y]>0)add(y,1);
            if(z>0&&a[y]<0)add(y,-1);
            a[y]=z;
        }
        else{
            int r=query(z),l=query(y-1);
            ll ans;
            if((r-l)&1){
                int x1=search(r),x2=search(l+1);
                ans=max(mult(y,x1-1),mult(x2+1,z));
            }else ans=mult(y,z);
            cout<<(ans>(1ll<<30)?"Too large":to_string(ans))<<endl;
        }
    }
    return 0;
}