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;elsebr[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;}}}
}