G - Add and Multiply Queries

G - Add and Multiply Queries

思路

开始直接用的线段树，写完才意识到是假的

由于题目说答案不会超过$10^{18}$，所以一个询问区间内的大于2的b的个数不超过64个，这样一个区间内大于2的b的就可以把a分成不超过64个连续的区间，用树状数组维护，b大于2的位置可以用线段树二分或者set的做法来找到(64logn)，在这种位置上判断+a和*b哪个选择更好即可

为了防止超时，实际上应该也超不了，用链表+set写复杂度仅为64+logn，具体做法是用链表维护b大于2的位置，查询的时候二分找到第一个b大于二的位置，后面的用链表来找

代码

#define lowbit(x) (x & -x)

int n;
vector<int> a, b;
vector<ll> tr;

void add(int d, int x) {
    for (; d <= n; d += lowbit(d))
        tr[d] += x;
}

ll get(int d) {
    ll res = 0;
    for (; d > 0; d -= lowbit(d))
        res += tr[d];
    return res;
}

ll getd(int l, int r) {
    return get(r) - get(l - 1);
}

void solve() {
    cin >> n;
    a.resize(n + 1), b.resize(n + 1);
    tr.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    set<int> ds;
    vector<int> br(n + 1);
    int last = INF;
    for (int i = n; i >= 1; i--) {
        if (b[i] > 1) {
            ds.insert(i);
            br[i] = last;
            last = i;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            add(l, r - a[l]);
            a[l] = r;
        } else if (op == 2) {
            if (b[l] < 2 && r > 1) {
                auto tt = ds.lower_bound(l);
                if (tt != ds.end())
                    br[l] = *tt;
                else
                    br[l] = INF;
                if (tt != ds.begin()) {
                    br[*--tt] = l;
                }
                ds.insert(l);
            } else if (b[l] > 1 && r < 2) {
                auto tt = ds.lower_bound(l);
                auto ft = tt;
                if (tt != ds.begin())
                    br[*--tt] = br[l];
                ds.erase(ft);
            }
            b[l] = r;
        } else {
            ll v = a[l++];
            if (l > r)
                cout << v << endl;
            else {
                auto tt = ds.lower_bound(l);
                int d = (tt == ds.end() ? INF : *tt);
                while (d <= r) {
                    if (d > l) {
                        v += getd(l, d - 1);
                    }
                    v + a[d] >= v* b[d] ? (v += a[d]) : (v *= b[d]);
                    l = d + 1;
                    d = br[d];
                }
                if (l <= r) {
                    v += getd(l, r);
                }
                cout << v << endl;
            }
        }
    }
}