Submission #1125287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125287		_8_8_	Fish 2 (JOI22_fish2)	C++20	13 / 100	4096 ms	104880 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, 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);
}
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;
}

pair<int, int> f[N * 4];
int mod[N * 4];
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) {
    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]);
    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) {
            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);
                }
            }
        }
    }
}
const ll inf = (ll)1e15;
void test() {
    cin >> n;
    a[0] = a[n + 1] = inf;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build();
    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);
            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