#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 map compress(vector &A){ map comp; int N = A.size(), i=0; for (int i=0; i> N; vector A(N), B(N); for (int i=0; i> A[i]; for (int i=0; i> B[i]; vector> v(N), w(N); map mp = compress(B); SegTree mi(N+1), pl(N+1); auto judge = [&](auto a, auto b){ return (pl.prod(mp[b], N) < a+b) && (mi.prod(0, mp[b]-1) < a-b); }; for (int r=0; r