Submission #738036

#	Time	Username	Problem	Language	Result	Execution time	Memory
738036		resting	Fish 2 (JOI22_fish2)	C++17	100 / 100	2807 ms	60380 KiB

fish2

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mx = 1e5 + 5;
const ll inf = 1e15;


struct segtree2 {
    int l, r, cnt1 = 0, cnt2 = 0, lz = 0;
    segtree2* lc, * rc;
    segtree2* getmem();
    segtree2() : segtree2(-1, -1) {};
    segtree2(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree2(l, m);
        rc = getmem(); *rc = segtree2(m + 1, r);
    }
    void fix() {
        if (l == r) {
            cnt1 = cnt2 = 0;
            if (lz == 1) cnt1 = 1;
            if (lz > 1) cnt2 = 1;
            return;
        }
        if (lz == 0) {
            cnt1 = lc->cnt1 + rc->cnt1;
            cnt2 = lc->cnt2 + rc->cnt2;
        } else if (lz == 1) {
            cnt2 = lc->cnt1 + rc->cnt1 + lc->cnt2 + rc->cnt2;
            cnt1 = (r - l + 1) - cnt2;
        } else {
            cnt1 = 0;
            cnt2 = (r - l + 1);
        }
    }
    void upd(int ql, int qr, int qv) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lz += qv; fix();
            return;
        }
        lc->upd(ql, qr, qv);
        rc->upd(ql, qr, qv);
        fix();
    }
    int q(int ql, int qr, int qlz = 0) {
        if (l > qr || r < ql) return 0;
        lz += qlz; fix();
        int res = 0;
        if (l >= ql && r <= qr) {
            res = cnt2 + cnt1;
        } else {
            res = lc->q(ql, qr, lz) + rc->q(ql, qr, lz);
        }
        lz -= qlz; fix();
        return res;
    }
};
segtree2 mem2[mx * 4];
int memsz2 = 0;
segtree2* segtree2::getmem() { return &mem2[memsz2++]; }
segtree2 ac2;

struct segtree {
    int l, r, v, m;
    segtree* lc, * rc;
    segtree* getmem();
    vector<pair<int, int>> k;
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        m = (l + r) / 2;
        if (l == r)return;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void del(int ql, int qr) {
        if (qr < m) { lc->del(ql, qr); return; }
        if (ql > m) { rc->del(ql, qr); return; }
        k.erase(find(k.begin(), k.end(), pair<int, int>(ql, qr)));
    }
    void add(int ql, int qr) {
        if (qr < m) { lc->add(ql, qr); return; }
        if (ql > m) { rc->add(ql, qr); return; }
        k.push_back({ ql, qr });
    }
    void q(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q(qi);
        else rc->q(qi);
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end();) {
                if (t->first <= qi) {
                    ac2.upd(t->first, t->second, -1);
                    k.erase(t);
                } else ++t;
            }
        } else {
            for (auto t = k.begin(); t != k.end(); ) {
                if (t->second >= qi) {
                    ac2.upd(t->first, t->second, -1);
                    k.erase(t);
                } else ++t;
            }
        }
    }
    void q2(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q2(qi);
        else rc->q2(qi);
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end();t++) {
                if (t->first <= qi) {
                    ac2.upd(t->first, t->second, -1);
                } 
            }
        } else {
            for (auto t = k.begin(); t != k.end(); t++) {
                if (t->second >= qi) {
                    ac2.upd(t->first, t->second, -1);
                } 
            }
        }
    }    void q3(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q3(qi);
        else rc->q3(qi);
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end();t++) {
                if (t->first <= qi) {
                    ac2.upd(t->first, t->second, 1);
                } 
            }
        } else {
            for (auto t = k.begin(); t != k.end(); t++) {
                if (t->second >= qi) {
                    ac2.upd(t->first, t->second, 1);
                } 
            }
        }
    }
};
segtree mem[mx * 4];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }


struct segtree3 {
    int l, r; ll mx = 0, sm = 0;
    segtree3* lc, * rc;
    segtree3* getmem();
    segtree3() : segtree3(-1, -1) {};
    segtree3(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree3(l, m);
        rc = getmem(); *rc = segtree3(m + 1, r);
    }
    void fix() {
        if (l == r) return;
        mx = max(lc->mx, rc->mx);
        sm = lc->sm + rc->sm;
    }
    void upd(int qi, ll qv) {
        if (l > qi || r < qi) return;
        if (l == r) {
            mx = qv; sm = qv;return;
        }
        lc->upd(qi, qv); rc->upd(qi, qv);
        fix();
    }
    int walkl(int ql, ll qv) {
        if (r < ql) return -1;
        if (mx <= qv) return -1;
        if (l == r) return l;
        int v = lc->walkl(ql, qv);
        return v == -1 ? rc->walkl(ql, qv) : v;
    }
    int walkr(int qr, ll qv) {
        if (l > qr) return -1;
        if (mx <= qv) return -1;
        if (l == r) return l;
        int v = rc->walkr(qr, qv);
        return v == -1 ? lc->walkr(qr, qv) : v;
    }
    ll qsum(int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return sm;
        return lc->qsum(ql, qr) + rc->qsum(ql, qr);
    }
};
segtree3 mem3[mx * 4];
int memsz3 = 0;
segtree3* segtree3::getmem() { return &mem3[memsz++]; }


segtree ac;  segtree3 ac3; vector<ll> ac4;
int n;

void clear(int i) {
    ac.q(i);
}

void redo(int i, bool extendleft, bool extendright) {
    //cout << "REDO " << i << endl;
    //walking time
    int l = i, r = i;
    while (1) {
        ll t = ac3.qsum(l, r);
        int wr = ac3.walkl(r + 1, t);
        int wl = ac3.walkr(l - 1, t);
        if (wl < i - 1 && !extendleft) break;
        if (wr > i + 1 && !extendright) break;
        if (wl == -1 || wr == -1) break;
        t = ac3.qsum(wl + 1, wr - 1);
        if (ac4[wl] > t && ac4[wr] > t) {
            ac.add(wl + 1, wr - 1);
            ac2.upd(wl + 1, wr - 1, 1);
        }
        l = wl + 1, r = wr - 1;
        if (ac4[wl] > ac4[wr]) {
            if (!extendright) break;
            r++;
        } else {
            if (!extendleft) break;
            l--;
        }
    }
}

int getl(int l, int r) {
    int rr = l;
    int res = l;
    while (1) {
        ll t = ac3.qsum(l, rr);
        rr = ac3.walkl(rr + 1, t);
        if (rr > r || rr == -1) break;
        t = ac3.qsum(l, rr - 1);
        if (ac4[rr] > t) res = rr;
    }
    return res;
}

int getr(int l, int r) {
    int l2 = r;
    int res = r;
    while (1) {
        ll t = ac3.qsum(l2, r);
        l2 = ac3.walkr(l2 - 1, t);
        if (l2 < l || l2 == -1) break;
        t = ac3.qsum(l2 + 1, r);
        if (ac4[l2] > t) res = l2;
    }
    return res;
}

void upd(int i, ll v, bool left, bool right) {
    ac4[i] = v; ac3.upd(i, v);
    clear(i);
    if (i < n + 1 && right)clear(i + 1);
    if (i && left)clear(i - 1);

    redo(i, 1, 1);
    if (i < n + 1 && right)redo(i + 1, 0, 1);
    if (i && left)redo(i - 1, 1, 0);
}

void solve() {
    cin >> n;
    vector<int> a(n + 1, 0); for (int i = 1; i <= n; i++) cin >> a[i];
    ac = segtree(0, n + 1); ac2 = segtree2(0, n + 1); ac3 = segtree3(0, n + 1); ac4 = vector<ll>(n + 2, 0);
    for (int i = 0; i <= n + 1; i++) { ac4[i] = a[i]; ac3.upd(i, a[i]); }
    for (int i = 0; i <= n + 1; i++) { redo(i, 1, 0); }
    int q; cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y; a[x] = y;
            upd(x, y, 1, 1);
        } else {
            int l, r; cin >> l >> r;
            int l2 = getl(l, r), r2 = getr(l, r);
            ac.q2(l);
            cout << (r2 - l2 + 1 - ac2.q(l2, r2)) << endl;
            ac.q3(l);
        }
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17