Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- namespace atcoder
- {
- template <class S, S (*op)(S, S), S (*e)()> struct segtree {
- int ceil_pow2(int n)
- {
- int x = 0;
- while ((1U << x) < (unsigned int) (n))
- x++;
- return x;
- }
- public:
- segtree() : segtree(0) {}
- explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
- explicit segtree(const std::vector<S> &v) : _n(int(v.size()))
- {
- log = ceil_pow2(_n);
- size = 1 << log;
- d = std::vector<S>(2 * size, e());
- for (int i = 0; i < _n; i++)
- d[size + i] = v[i];
- for (int i = size - 1; i >= 1; i--) {
- update(i);
- }
- }
- void set(int p, S x)
- {
- assert(0 <= p && p < _n);
- p += size;
- d[p] = x;
- for (int i = 1; i <= log; i++)
- update(p >> i);
- }
- S get(int p) const
- {
- assert(0 <= p && p < _n);
- return d[p + size];
- }
- S prod(int l, int r) const
- {
- assert(0 <= l && l <= r && r <= _n);
- S sml = e(), smr = e();
- l += size;
- r += size;
- while (l < r) {
- if (l & 1)
- sml = op(sml, d[l++]);
- if (r & 1)
- smr = op(d[--r], smr);
- l >>= 1;
- r >>= 1;
- }
- return op(sml, smr);
- }
- S all_prod() const { return d[1]; }
- template <bool (*f)(S)> int max_right(int l) const
- {
- return max_right(l, [](S x) { return f(x); });
- }
- template <class F> int max_right(int l, F f) const
- {
- assert(0 <= l && l <= _n);
- assert(f(e()));
- if (l == _n)
- return _n;
- l += size;
- S sm = e();
- do {
- while (l % 2 == 0)
- l >>= 1;
- if (!f(op(sm, d[l]))) {
- while (l < size) {
- l = (2 * l);
- if (f(op(sm, d[l]))) {
- sm = op(sm, d[l]);
- l++;
- }
- }
- return l - size;
- }
- sm = op(sm, d[l]);
- l++;
- } while ((l & -l) != l);
- return _n;
- }
- template <bool (*f)(S)> int min_left(int r) const
- {
- return min_left(r, [](S x) { return f(x); });
- }
- template <class F> int min_left(int r, F f) const
- {
- assert(0 <= r && r <= _n);
- assert(f(e()));
- if (r == 0)
- return 0;
- r += size;
- S sm = e();
- do {
- r--;
- while (r > 1 && (r % 2))
- r >>= 1;
- if (!f(op(d[r], sm))) {
- while (r < size) {
- r = (2 * r + 1);
- if (f(op(d[r], sm))) {
- sm = op(d[r], sm);
- r--;
- }
- }
- return r + 1 - size;
- }
- sm = op(d[r], sm);
- } while ((r & -r) != r);
- return 0;
- }
- private:
- int _n, size, log;
- std::vector<S> d;
- void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
- };
- } // namespace atcoder
- using atcoder::segtree;
- struct S {
- int pp, pn, np, nn;
- };
- S op(S a, S b) {
- S c;
- c.pp = max(a.pp, a.pn) + b.np;
- c.pp = max(c.pp, a.pn + max(b.pp, b.np));
- c.pn = a.pn + max(b.nn, b.pn);
- c.pn = max(c.pn, a.pp + b.nn);
- c.np = a.nn + max(b.np, b.pp);
- c.np = max(c.np, a.np + b.np);
- // c.nn = a.nn + b.nn;
- c.nn = a.nn + max(b.pn, b.nn);
- c.nn = max(c.nn, max(a.nn, a.np) + b.nn);
- return c;
- }
- S e() {return S{0, 0, 0, 0};}
- class Solution {
- public:
- int maximumSumSubsequence(vector<int>& ns, vector<vector<int>>& qs) {
- int ret = 0, n = ns.size();
- constexpr int mod = 1e9 + 7;
- segtree<S, op, e> seg(n);
- for (int i = 0; i < n; ++i)
- seg.set(i, S{ns[i], 0, 0, 0});
- for (const auto& q: qs) {
- seg.set(q[0], S{q[1], 0, 0, 0});
- auto s = seg.all_prod();
- ret = (ret + max({s.pp, s.pn, s.np, s.nn})) % mod;
- }
- return ret;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement