#include #include #include #include #include #include #include #include #include #include #include using namespace std; templatestruct SegTree { vector seg; long long N = 1; SegTree (long long n) : SegTree(vector(n, e())) {} SegTree (const vector &v){ long long n = v.size(); while (N < n) N *= 2; seg.resize(N*2-1, e()); for (long long i=0; i=0; i--){ seg[i] = op(seg[i*2+1], seg[i*2+2]); } } void set(long long loc, S val){ loc += N-1; seg[loc] = val; while (loc != 0){ loc = (loc-1)/2; seg[loc] = op(seg[loc*2+1], seg[loc*2+2]); } } //op(a[l], ..., a[r]) S prod (long long l, long long r) const{ return _prod(l, r, 0, 0, N-1); } S all_prod() const{ return seg[0]; } S _prod (long long l, long long r, long long idx, long long bitl, long long bitr) const{ if (r < bitl || l > bitr) return e(); if (l <= bitl && bitr <= r) return seg[idx]; long long bitm = (bitl+bitr)/2; return op(_prod(l, r, idx*2+1, bitl, bitm), _prod(l, r, idx*2+2, bitm+1, bitr)); } S get (long long i) const{ return seg[i+N-1]; } void show() const{ for (int i=N-1; i> N; vector A(N), B(N), x(N), y(N); for (int i=0; i> A[i]; for (int i=0; i> B[i]; for (int i=0; i mi(y), pl(x); auto judge = [&](auto i, auto j){ return (pl.prod(i, j-1) < A[j]+B[j]) && (mi.prod(i, j-1) < A[j]-B[j]); }; for (int r=0; r