Submission #1125268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125268		_8_8_	Fish 2 (JOI22_fish2)	C++20	13 / 100	4099 ms	130360 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];

void  upd(int pos, int 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);
}
int getl(int l, int r) {
    if(l == 1) return 0;
    ll s = get(l, r);
    for(int i = l - 1; i >= 1; i--) {
        s += a[i];
        if(a[i - 1] > s) {
            return i;
        }
    }
    return 1;
}
int getr(int l, int r) {
    if(r == n) return n + 1;
    ll s = get(l, r);
    for(int i = r + 1; i <= n; i++) {
        s += a[i];
        if(a[i + 1] > s) {
            return i;
        }
    }
    return n;
}

void add(int l, int r) {
    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) {
    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]);
    a[l] = r;
    upd(l, a[l]);
    {
        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) {
            int 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);
                }
            }
        }
    }
}
const ll inf = (ll)1e18;
void test() {
    cin >> n;
    a[0] = a[n + 1] = (ll)1e18;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    prec();
    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);
            for(int i = l; i <= r; ++i) {
                res++;
                for(auto [tl, tr] : s[i]) {
                    if(tl < l || tr > r) continue;
                    if(tl == l && tr == r) continue;
                    res--;
                    // cout << i << " " << tl << ' ' << tr << '\n';
                    break;
                }
            }
            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