Advertisement
pb_jiang

t4

May 25th, 2024
724
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.17 KB | None | 0 0
  1. namespace atcoder
  2. {
  3.  
  4. template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  5.     int ceil_pow2(int n)
  6.     {
  7.         int x = 0;
  8.         while ((1U << x) < (unsigned int) (n))
  9.             x++;
  10.         return x;
  11.     }
  12.  
  13.   public:
  14.     segtree() : segtree(0) {}
  15.     explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
  16.     explicit segtree(const std::vector<S> &v) : _n(int(v.size()))
  17.     {
  18.         log = ceil_pow2(_n);
  19.         size = 1 << log;
  20.         d = std::vector<S>(2 * size, e());
  21.         for (int i = 0; i < _n; i++)
  22.             d[size + i] = v[i];
  23.         for (int i = size - 1; i >= 1; i--) {
  24.             update(i);
  25.         }
  26.     }
  27.  
  28.     void set(int p, S x)
  29.     {
  30.         assert(0 <= p && p < _n);
  31.         p += size;
  32.         d[p] = x;
  33.         for (int i = 1; i <= log; i++)
  34.             update(p >> i);
  35.     }
  36.  
  37.     S get(int p) const
  38.     {
  39.         assert(0 <= p && p < _n);
  40.         return d[p + size];
  41.     }
  42.  
  43.     S prod(int l, int r) const
  44.     {
  45.         assert(0 <= l && l <= r && r <= _n);
  46.         S sml = e(), smr = e();
  47.         l += size;
  48.         r += size;
  49.  
  50.         while (l < r) {
  51.             if (l & 1)
  52.                 sml = op(sml, d[l++]);
  53.             if (r & 1)
  54.                 smr = op(d[--r], smr);
  55.             l >>= 1;
  56.             r >>= 1;
  57.         }
  58.         return op(sml, smr);
  59.     }
  60.  
  61.     S all_prod() const { return d[1]; }
  62.  
  63.     template <bool (*f)(S)> int max_right(int l) const
  64.     {
  65.         return max_right(l, [](S x) { return f(x); });
  66.     }
  67.     template <class F> int max_right(int l, F f) const
  68.     {
  69.         assert(0 <= l && l <= _n);
  70.         assert(f(e()));
  71.         if (l == _n)
  72.             return _n;
  73.         l += size;
  74.         S sm = e();
  75.         do {
  76.             while (l % 2 == 0)
  77.                 l >>= 1;
  78.             if (!f(op(sm, d[l]))) {
  79.                 while (l < size) {
  80.                     l = (2 * l);
  81.                     if (f(op(sm, d[l]))) {
  82.                         sm = op(sm, d[l]);
  83.                         l++;
  84.                     }
  85.                 }
  86.                 return l - size;
  87.             }
  88.             sm = op(sm, d[l]);
  89.             l++;
  90.         } while ((l & -l) != l);
  91.         return _n;
  92.     }
  93.  
  94.     template <bool (*f)(S)> int min_left(int r) const
  95.     {
  96.         return min_left(r, [](S x) { return f(x); });
  97.     }
  98.     template <class F> int min_left(int r, F f) const
  99.     {
  100.         assert(0 <= r && r <= _n);
  101.         assert(f(e()));
  102.         if (r == 0)
  103.             return 0;
  104.         r += size;
  105.         S sm = e();
  106.         do {
  107.             r--;
  108.             while (r > 1 && (r % 2))
  109.                 r >>= 1;
  110.             if (!f(op(d[r], sm))) {
  111.                 while (r < size) {
  112.                     r = (2 * r + 1);
  113.                     if (f(op(d[r], sm))) {
  114.                         sm = op(d[r], sm);
  115.                         r--;
  116.                     }
  117.                 }
  118.                 return r + 1 - size;
  119.             }
  120.             sm = op(d[r], sm);
  121.         } while ((r & -r) != r);
  122.         return 0;
  123.     }
  124.  
  125.   private:
  126.     int _n, size, log;
  127.     std::vector<S> d;
  128.  
  129.     void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
  130. };
  131.  
  132. } // namespace atcoder
  133. using atcoder::segtree;
  134.  
  135. struct S {
  136.     int pp, pn, np, nn;
  137. };
  138. S op(S a, S b) {
  139.     S c;
  140.     c.pp = max(a.pp, a.pn) + b.np;
  141.     c.pp = max(c.pp, a.pn + max(b.pp, b.np));
  142.  
  143.     c.pn = a.pn + max(b.nn, b.pn);
  144.     c.pn = max(c.pn, a.pp + b.nn);
  145.  
  146.     c.np = a.nn + max(b.np, b.pp);
  147.     c.np = max(c.np, a.np + b.np);
  148.     // c.nn = a.nn + b.nn;
  149.     c.nn = a.nn + max(b.pn, b.nn);
  150.     c.nn = max(c.nn, max(a.nn, a.np) + b.nn);
  151.     return c;
  152. }
  153. S e() {return S{0, 0, 0, 0};}
  154.  
  155. class Solution {
  156. public:
  157.     int maximumSumSubsequence(vector<int>& ns, vector<vector<int>>& qs) {
  158.         int ret = 0, n = ns.size();
  159.         constexpr int mod = 1e9 + 7;
  160.         segtree<S, op, e> seg(n);
  161.         for (int i = 0; i < n; ++i)
  162.             seg.set(i, S{ns[i], 0, 0, 0});
  163.  
  164.         for (const auto& q: qs) {
  165.             seg.set(q[0], S{q[1], 0, 0, 0});
  166.             auto s = seg.all_prod();
  167.             ret = (ret + max({s.pp, s.pn, s.np, s.nn})) % mod;
  168.         }
  169.         return ret;
  170.     }
  171. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement