Submission #1188562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188562		12345678	Fish 2 (JOI22_fish2)	C++17	100 / 100	1827 ms	25664 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, a[nx], q, t, l, r, x, y, ql, qr;

struct segtreesum
{
    ll d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=a[l], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
    }
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md ,2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql||qr<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md ,2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} sm;

struct segtreeleft
{
    // qs[i]-qs[l-1] < a[i+1] -> qs[i]-a[i+1] < qs[l-1]
    ll d[4*nx], lz[4*nx];
    void apply(int i, ll vl)
    {
        d[i]+=vl;
        lz[i]+=vl;
    }
    void pushlz(int i)
    {
        apply(2*i, lz[i]);
        apply(2*i+1, lz[i]);
        lz[i]=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=sm.query(1, n, 1, 1, l)-a[l+1], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        //cout<<"update "<<ql<<' '<<qr<<' '<<vl<<'\n';
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return apply(i, vl);
        int md=(l+r)/2;
        pushlz(i);
        update(l, md, 2*i, ql, qr ,vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    ll query(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<ql||qr<l||r<ql||d[i]>=vl) return ql-1;
        if (l==r) return l;
        int md=(l+r)/2;
        pushlz(i);
        auto tmp=query(md+1, r, 2*i+1, ql, qr, vl);
        if (tmp<ql) return query(l, md, 2*i, ql, qr, vl);
        return tmp;
    }
    void queryfill(int l, int r, int i, int ql, int qr, ll vl, vector<int> &v)
    {
        if (qr<l||r<ql||d[i]>=vl) return;
        if (l==r) return v.push_back(l), void();
        int md=(l+r)/2;
        pushlz(i);
        queryfill(l, md, 2*i, ql, qr, vl, v);
        queryfill(md+1, r, 2*i+1, ql, qr ,vl, v);
    }
    void show(int l, int r, int i)
    {
        if (l==r) return cout<<"vl "<<l<<' '<<d[i]<<'\n', void();
        pushlz(i);
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
} ls;

struct segtreeright
{
    // qs[r] - qs[i-1] < a[i-1] -> qs[r] < a[i-1] + qs[i-1]
    ll d[4*nx], lz[4*nx];
    void apply(int i, ll vl)
    {
        d[i]+=vl;
        lz[i]+=vl;
    }
    void pushlz(int i)
    {
        apply(2*i, lz[i]);
        apply(2*i+1, lz[i]);
        lz[i]=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=sm.query(1, n, 1, 1, l-1)+a[l-1], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return apply(i, vl);
        int md=(l+r)/2;
        pushlz(i);
        update(l, md, 2*i, ql, qr ,vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    ll query(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<ql||qr<l||r<ql||d[i]<=vl) return qr+1;
        if (l==r) return l;
        int md=(l+r)/2;
        pushlz(i);
        auto tmp=query(l, md, 2*i, ql, qr, vl);
        if (tmp>qr) return query(md+1, r, 2*i+1, ql, qr, vl);
        return tmp;
    }
    void queryfill(int l, int r, int i, int ql, int qr, ll vl, vector<int> &v)
    {
        if (qr<l||r<ql||d[i]<=vl) return;
        //if (l==r) cout<<"debug "<<l<<' '<<d[i]<<' '<<vl<<'\n';
        if (l==r) return v.push_back(l), void();
        int md=(l+r)/2;
        pushlz(i);
        queryfill(l, md, 2*i, ql, qr, vl, v);
        queryfill(md+1, r, 2*i+1, ql, qr ,vl, v);
    }
} rs;

struct segtreefreq
{
    struct node
    {
        ll mn, f, lz;
        node(): mn(1e18), f(0), lz(0){}
    } d[4*nx];
    void apply(int i, ll vl)
    {
        d[i].mn+=vl;
        d[i].lz+=vl;
    }
    void pushlz(int i)
    {
        apply(2*i, d[i].lz);
        apply(2*i+1, d[i].lz);
        d[i].lz=0;
    }
    node merge(node l, node r)
    {
        node res;
        res.mn=min(l.mn, r.mn);
        res.f=(l.f*(l.mn==res.mn))+(r.f*(r.mn==res.mn));
        return res;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i].mn=0, d[i].f=1, d[i].lz=0, void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return apply(i, vl);
        int md=(l+r)/2;
        pushlz(i);
        update(l, md, 2*i, ql, qr ,vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void show(int l, int r, int i)
    {
        //cout<<"show "<<l<<' '<<r<<' '<<i<<'\n';
        if (l==r) return cout<<l<<' '<<d[i].mn<<' '<<d[i].f<<'\n', void();
        int md=(l+r)/2;
        pushlz(i);
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return node();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        pushlz(i);
        return merge(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} fs;

set<pair<int, int>> ranges;
void addrange(int l, int r, int vl)
{
    //cout<<"addrange "<<l<<' '<<r<<' '<<vl<<'\n';
    fs.update(1, n, 1, l, r, vl);
    if (vl==1) ranges.insert({l, r});
    else ranges.erase({l, r});
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    a[0]=a[n+1]=1e18;
    sm.build(1, n, 1);
    ls.build(1, n, 1);
    rs.build(1, n, 1);
    fs.build(1, n, 1);
    //ls.show(1, n, 1);
    for (int i=1; i<=n; i++)
    {
        vector<int> p;
        rs.queryfill(1, n, 1, 1, i, sm.query(1, n, 1, 1, i), p);
        for (auto x:p) if (sm.query(1, n, 1, x, i)<a[i+1]) addrange(x, i, 1);
    }
    //fs.show(1, n, 1);
    cin>>q;
    while (q--)
    {
        cin>>t;
        if (t==1)
        {
            cin>>x>>y;
            vector<int> pl, pr;
            ls.queryfill(1, n, 1, x, n, sm.query(1, n, 1, 1, x-1), pr);
            rs.queryfill(1, n, 1, 1, x, sm.query(1, n, 1, 1, x), pl);
            vector<ll> ppr(pr.size()), ppl(pl.size());
            for (int i=0; i<pr.size(); i++) ppr[i]=sm.query(1, n, 1, x, pr[i]);
            for (int i=0; i<pl.size(); i++) ppl[i]=sm.query(1, n, 1, pl[i], x);
            for (int i=0; i<pr.size(); i++) for (int j=0; j<pl.size(); j++) if (ppr[i]+ppl[j]-a[x]<a[pr[i]+1]&&ppr[i]+ppl[j]-a[x]<a[pl[j]-1]) addrange(pl[j], pr[i], -1);
            pl.clear(), pr.clear();
            ls.queryfill(1, n, 1, x+1, n, sm.query(1, n, 1, 1, x), pr);
            rs.queryfill(1, n, 1, 1, x-1, sm.query(1, n, 1, 1, x-1), pl);
            for (int i=0; i<pr.size(); i++) if (sm.query(1, n, 1, x+1, pr[i])<a[x]) addrange(x+1, pr[i], -1);
            for (int i=0; i<pl.size(); i++) if (sm.query(1, n, 1, pl[i], x-1)<a[x]) addrange(pl[i], x-1, -1);
            ls.update(1, n, 1, x, n, y-a[x]);
            ls.update(1, n, 1, x-1, x-1, -(y-a[x]));
            rs.update(1, n, 1, x+1, n, y-a[x]);
            rs.update(1, n, 1, x+1, x+1, y-a[x]);
            //ls.show(1, n, 1);
            a[x]=y;
            sm.update(1, n, 1, x, y);
            pl.clear(), pr.clear();
            ls.queryfill(1, n, 1, x, n, sm.query(1, n, 1, 1, x-1), pr);
            rs.queryfill(1, n, 1, 1, x, sm.query(1, n, 1, 1, x), pl);
            ppr.resize(pr.size()), ppl.resize(pl.size());
            for (int i=0; i<pr.size(); i++) ppr[i]=sm.query(1, n, 1, x, pr[i]);
            for (int i=0; i<pl.size(); i++) ppl[i]=sm.query(1, n, 1, pl[i], x);
            for (int i=0; i<pr.size(); i++) for (int j=0; j<pl.size(); j++) if (ppr[i]+ppl[j]-a[x]<a[pr[i]+1]&&ppr[i]+ppl[j]-a[x]<a[pl[j]-1]) addrange(pl[j], pr[i], 1);
            pl.clear(), pr.clear();
            ls.queryfill(1, n, 1, x+1, n, sm.query(1, n, 1, 1, x), pr);
            rs.queryfill(1, n, 1, 1, x-1, sm.query(1, n, 1, 1, x-1), pl);
            for (int i=0; i<pr.size(); i++) if (sm.query(1, n, 1, x+1, pr[i])<a[x]) addrange(x+1, pr[i], 1);
            for (int i=0; i<pl.size(); i++) if (sm.query(1, n, 1, pl[i], x-1)<a[x]) addrange(pl[i], x-1, 1);
            //for (auto [l, r]:ranges) cout<<"ranges "<<l<<' '<<r<<'\n';
        }
        else
        {
            cin>>l>>r;
            ql=ls.query(1, n, 1, l, r-1, sm.query(1, n, 1, 1, l-1))+1;
            qr=rs.query(1, n, 1, l+1, r, sm.query(1, n, 1, 1, r))-1;
            //cout<<"debug "<<ql<<' '<<qr<<'\n';
            cout<<fs.query(1, n, 1, ql, qr).f<<'\n';
        }
    }
    //2 3 5 8 1 3 4 20 5 5
    //2 3 5 inf 1 3 4 9 5 5
}

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