1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include <algorithm> #include <cstdio> const int N = 100050; typedef long long LL; struct Frac{ int x, y; Frac(int x = 1, int y = 0) : x(x), y(y) {} bool operator<(const Frac &f) const { return (LL)y * f.x < (LL)f.y * x; } }maxv[N * 4]; int lenv[N * 4], Y[N]; int query(int o, int l, int r, Frac x) { if (!(x < maxv[o])) return 0; if (l == r) return 1; int mid = (l + r) / 2; return maxv[o << 1] < x ? query(o << 1 | 1, mid + 1, r, x) : query(o << 1, l, mid, x) + lenv[o] - lenv[o << 1]; } void upd(int o, int l, int r) { if (l == r) { lenv[o] = 1; maxv[o] = Frac(l, Y[l]); } else { int lc = o << 1, rc = o << 1 | 1, mid = (l + r) / 2; maxv[o] = std::max(maxv[lc], maxv[rc]); lenv[o] = lenv[lc] + query(rc, mid + 1, r, maxv[lc]); } } void modify(int o, int l, int r, int x, int y) { if (l > x || r < x) return; if (l == r) Y[x] = y; else { int mid = (l + r) / 2; modify(o << 1, l, mid, x, y); modify(o << 1 | 1, mid + 1, r, x, y); } upd(o, l, r); } void build(int o, int l, int r) { maxv[o] = Frac(l, 0); lenv[o] = 1; if (l != r) { int mid = (l + r) / 2; build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); } } int main() { int n, m, x, y; scanf("%d%d", &n, &m); build(1, 1, n); while (m--) { scanf("%d%d", &x, &y); modify(1, 1, n, x, y); printf("%d\n", query(1, 1, n, Frac())); } return 0; }
|