洛谷P8563 Magenta Potion 题解

题意：

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

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

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

输入格式：

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

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

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

输出格式：

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

数据范围：

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

注意到保证了 $k$ 的绝对值大于等于 $2$ ，因此乘不超过 $30$ 次就爆了。

所以暴力就是正解，记得加个 break 。时间复杂度 $\mathcal{O}(30\cdot q)$ 。代码没写。

~~考场上搞了个线段树 + $\mathtt{vector}$ 维护负下标的东西，那个复杂度是假的（但是过了）。~~

这里讲讲后来写的线段树+树状数组+$\mathtt{set}$ 维护负下标的写法。

具体做法是线段树维护区间乘积的绝对值和单点修改。

对于单点修改，如果它变成了负的就插入一个当前下标到 $\mathtt{set}$ 里。

对于区间 $[l,r]$ ，设 $\mathtt{lx},\mathtt{rx}$ 表示最左和最右的负值的位置，且有 $l \le \mathtt{lx}\le \mathtt{rx} \le r$ 。

注意可能不存在 $\mathtt{lx},\mathtt{rx}$ ，特判特判特判。~~这玩意调起来有点烦的~~。

如果 $\mathtt{lx},\mathtt{rx}$ 之间（包括）有奇数个负值，则选 $\max\{1,~\mathtt{query}(\mathtt{lx}+1,r),~ \mathtt{query}(l,\mathtt{rx}-1)\}$

否则如果有偶数个负值，那怎么乘都是正的，所以肯定选最大的区间，即选 $\mathtt{query}(l,r)$ 。

注意前者要加一个 $1$ ，是因为 $\mathtt{lx}+1$ 可能大于 $r$ ，答案为 $0$ 。这个只要特判一下就好了。

这个负值的个数就是树状数组单点修改区间查询，随便写写就过了。

不要用 std::distance() ，因为 set 是非随机访问迭代器，复杂度会变成 $\mathcal{O}(qn)$ 。

时间复杂度 $\mathcal{O}(q \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))
const int M = 1ll << 30;

void mul(int &x,int y) { (x *= y) > M ? x=M+1 : 0; }
set<int> st;
int n,Q,a[N],ans[N * 4],tree[N];
int lowbit(int x) { return x & (-x); }
void add(int x,int v)
{
    for(int i=x; i<=n; i+=lowbit(i))
        tree[i] += v;
}
int sum(int x)
{
    int res=0;
    for(int i=x; i; i-=lowbit(i))
        res += tree[i];
    return res;
}
#define ls(at) (at << 1)
#define rs(at) (at << 1 | 1)
void push_up(int at)
{
    ans[at] = ans[ls(at)] * ans[rs(at)];
    if(ans[at] > M) ans[at] = M+1;
}
void build(int l,int r,int at)
{
    if(l == r) { return ans[at] = abs(a[l]), void(0); }
    int mid = (l + r) >> 1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
    push_up(at);
}
void modify(int x,int l,int r,int k,int at)
{
    if(l == r)
    {
        if(k < 0) { if(a[x] > 0){ st.insert(x); add(x,1); } }
        else { if(a[x] < 0){ st.erase(st.lower_bound(x)),add(x,-1); } }
        a[x] = k; ans[at] = abs(k); return void(0);
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(x,l,mid,k,ls(at));
    else modify(x,mid+1,r,k,rs(at));
    push_up(at);
}
int query(int nl,int nr,int l,int r,int at)
{
    if(nl <= l && r <= nr) return ans[at];
    int res=1, mid = (l + r) >> 1;
    if(nl <= mid) mul(res, query(nl,nr,l,mid,ls(at)));
    if(nr > mid) mul(res, query(nl,nr,mid+1,r,rs(at)));
    return res;
}
int calc(int l,int r)
{
    int res = query(l,r,1,n,1);
    return res > M ? -1 : res;
}
int solve(int l,int r)
{
    if(l > r) return 1;
    if(st.empty()) return calc(l,r);
    auto p = st.lower_bound(l);
    if(p == st.end() || *p > r) return calc(l,r);
    auto q = st.upper_bound(r); --q;
    int lx = *p, rx = *q, len = sum(r)-sum(l-1);
    // cout << lx << ' ' << rx << ' ' << len << '\n';
    int res = 1;
    if(len & 1)
    {
        if(l <= rx-1) up(res, query(l, rx-1, 1,n,1));
        if(lx+1 <= r) up(res, query(lx+1, r, 1,n,1));
    }
    else return calc(l,r);
    return res > M ? -1 : res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        if(a[i] < 0) st.insert(i), add(i,1);
    }
    build(1,n,1);
    for(int op,x,l,r; Q--; )
    {
        cin >> op;
        if(op == 1)
        {
            cin >> l >> x;
            modify(l,1,n,x,1);
        }else
        {
            cin >> l >> r;
            int res = solve(l,r);
            if(res == -1) cout << "Too large\n";
            else cout << res << '\n';
            // assert(res == -1 || res > 0);
        }
    }
    return 0;
}