Submission #1125387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125387		_8_8_	Fish 2 (JOI22_fish2)	C++20	13 / 100	4101 ms	148996 KiB

fish2

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

const int  N = (int)1e5 + 12, MOD = 998244353;
#define int ll      
int n, q;
set<pair<int, int>> s[N], x[N], y[N];
ll a[N], t[N];
const ll inf = (ll)1e15;
void  upd(int pos, ll val) {
    while(pos <= n) {
        t[pos] += val;
        pos += pos & -pos;
    }
}
ll get(int i) {
    ll ret = 0;
    while(i) {
        ret += t[i];
        i -= i & -i;
    }
    return ret;
}
ll get(int l, int r) {
    if(l > r) return 0;
    return get(r) - get(l - 1);
}
struct segtree{
    vector<ll> t, mod;

    void init() {
        t.resize(N * 4 + 1, 0);
        mod.resize(N * 4 + 1, 0);
    }
    void inc(int v, ll val) {
        mod[v] += val;
        t[v] += val;
    }
    void push(int v) {
        if(mod[v]) {
            inc(v + v, mod[v]);
            inc(v + v + 1, mod[v]);
            mod[v] = 0;
        }
    }
    void upd(int l, int r, ll val, int v, int tl, int tr) {
        if(l > r || tl > r || l > tr) return;
        if(tl >= l && tr <= r) {
            // cout << t[v] << "x\n";
            inc(v, val);
            // cout << t[v] << "x\n";
        } else {
            push(v);
            int tm = (tl + tr) >> 1;
            upd(l, r, val, v + v, tl, tm);
            upd(l, r, val, v + v + 1, tm + 1, tr);
            t[v] = max(t[v + v], t[v + v + 1]);
        }
        // cout << tl << ' ' << tr << ' ' << t[v] << '\n';
    }
    void upd1(int pos, ll val, int v, int tl, int tr) {
        if(tl == tr) {
            t[v] = val;
        } else {
            push(v);
            int tm = (tl + tr) >> 1;
            if(pos <= tm) upd1(pos, val, v + v, tl, tm);
            else upd1(pos, val, v + v + 1, tm + 1, tr);
            t[v] = max(t[v + v], t[v + v + 1]);
        }
    }
    ll get(int l, int r, int v, int tl, int tr) {
        if(l > r || tl > r || l > tr) return -(ll)1e18;
        if(tl >= l && tr <= r) return t[v];
        push(v);
        int tm = (tl + tr) >> 1;
        return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
    }
}tr1, tr2;
int getl(int l, int r) {
    if(l == 1) return 0;
    ll F = get(r + 1, n);
    int L = 1, R = l;
    while(R - L > 1) {
        int mid = (L + R) >> 1;
        if(tr2.get(mid, l - 1, 1, 1, n) > -F) {
            L = mid;
        } else {
            R = mid;
        }
    }
    return L;
    // ll s = get(l, r);
    // for(int i = l - 1; i >= 1; i--) {
    //     s += a[i];
    //     if(a[i - 1] > s) {
    //         cout << l << ' ' << r << ' ' << L << ' ' << i << '\n';
    //         return i;
    //     }
    // }
    // return 1;
}
int getr(int l, int r) {
    if(r == n) return n + 1;
    ll F = get(l - 1);
    int L = r, R = n;
    while(R - L > 1) {
        int mid = (L + R) >> 1;
        if(tr1.get(r + 1, mid, 1, 1, n) > -F) {
            R = mid;
        } else {
            L = mid;
        }
    }
    return R;
}

pair<int, int> f[N * 4];
int mod[N * 4];
int sum = 0;
void inc(int v, int val) {
    f[v].first += val;
    mod[v] += val;
}
void push(int v) {
    if(mod[v]) {
        inc(v + v, mod[v]);
        inc(v + v + 1, mod[v]);
        mod[v] = 0;
    }
}
pair<int, int> merge(pair<int, int> x, pair<int, int> y) {
    if(x.first == y.first) {
        x.second += y.second;
    }
    if(x.first <= y.first) return x;
    return y;
}
void upd1(int l, int r, int val, int v = 1, int tl = 1, int tr = n) {
    if(l > r || tl > r || l > tr) return ;
    if(tl >= l && tr <= r) {
        inc(v, val);
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        upd1(l, r, val, v + v, tl, tm);
        upd1(l, r, val, v + v + 1, tm + 1, tr);
        f[v] = merge(f[v + v], f[v + v + 1]);
    }
}
void build(int v = 1, int tl = 1, int tr = n) {
    f[v] = {0, tr - tl + 1};
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
}
pair<int, int> get1(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if(l > r || tl > r || l > tr) return {(int)1e9, 0};
    if(tl >= l && tr <= r) return f[v];
    push(v);
    int tm = (tl + tr) >> 1;
    return merge(get1(l, r, v + v, tl, tm), get1(l, r, v + v + 1, tm + 1, tr));
}
void add(int l, int r) {
    sum += (r - l + 1);
    upd1(l, r, 1);
    for(int i = l; i <= r; i++) {
        s[i].insert({l, r});
    }
    x[l - 1].insert({l, r});
    y[r + 1].insert({l, r});
}
void del(int l, int r) {
    upd1(l, r, -1);
    for(int i = l; i <= r; i++) {
        s[i].erase({l, r});
    }
    x[l - 1].erase({l, r});
    y[r + 1].erase({l, r});
}
void prec() {
    for(int i = 1; i <= n; i++) {
        upd(i, a[i]);
    }
    for(int i = 0; i <= n; i++) {
        int r = getr(i + 1, i);
        while(r <= n) {
            if(get(i + 1, r) < a[i]) {
                add(i + 1, r);
            } else break;
            r = getr(i + 1, r);
        }
    }
}
void u(int l, ll r) {
    vector<pair<int, int>> dd;
    auto _add = [&](set<pair<int, int>> &st) {
        for(auto [l, r] : st) {
            dd.emplace_back(l, r);
        }
    };
    _add(s[l]);_add(x[l]);_add(y[l]);
    for(auto [l, r] : dd) {
        del(l, r);
    }
    upd(l, -a[l]);
    ll delt = (r - a[l]);
    if(l - 1 >= 1) tr1.upd(l - 1, l - 1, delt, 1, 1, n);
    if(l + 1 <= n) tr2.upd(l + 1, l + 1, delt, 1, 1, n);
    tr1.upd(l, n, -delt, 1, 1, n);
    tr2.upd(1, l, -delt, 1, 1, n);
    a[l] = r;
    upd(l, a[l]);
    // exit(0);
    {
        int nx = getr(l + 1, l);
        while(nx <= n) {
            if(get(l + 1, nx) < a[l]) {
                add(l + 1, nx);
            } else break;
            nx = getr(l + 1, nx);
        }
    }
    {
        int prv = getl(l, l - 1);
        while(prv >= 1) {
            if(get(prv, l - 1) < a[l]) {
                add(prv, l - 1);
            } else break;
            prv = getl(prv, l - 1);
        }
    }
    {
        int nx = getr(l, l - 1), prv = getl(l + 1, l);
        while(nx <= n && prv >= 1) {
            ll val = get(prv, nx);
            if(val >= a[prv - 1]) {
                prv = getl(prv, nx);
            } else if(val >= a[nx + 1]) {
                nx = getr(prv, nx);
            } else {
                add(prv, nx);
                if(a[prv - 1] < a[nx + 1]) {
                    prv = getl(prv, nx);
                } else {
                    nx = getr(prv, nx);
                }
            }
        }
    }
}

void test() {
    cin >> n;
    tr1.init();
    tr2.init();
    a[0] = a[n + 1] = inf;
    ll pr = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        pr += a[i];
        tr1.upd1(i, a[i + 1] - pr, 1, 1, n);
    }
    pr = 0;
    for(int i = n; i >= 1; i--) {
        pr += a[i];
        tr2.upd1(i, a[i - 1] - pr, 1, 1, n);
    }
    build();
    prec();
    assert(sum <= n * 23);
    cin >> q;

    while(q--) {
        int tp, l, r;
        cin >> tp >> l >> r;
        if(tp == 2) {
            int res = 0;
            ll X = a[l - 1], Y = a[r + 1];
            if(l - 1 >= 1) u(l - 1, inf);
            if(r + 1 <= n) u(r + 1, inf);
            res = get1(l, r).second;
            cout << res << "\n";
            if(l - 1 >= 1) u(l - 1, X);
            if(r + 1 <= n) u(r + 1, Y);
        } else {
            u(l, r);
        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}   

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