제출 #1126249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126249		dwuy	Weirdtree (RMI21_weirdtree)	C++20	0 / 100	2095 ms	45372 KiB

weirdtree

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

struct Node{
    ll fm, sm, cm, lz, sum;
    Node() : fm(0), sm(-2), cm(0), sum(0) {}
};

struct SMT{
    ll n;
    vector<Node> tree;
    SMT(ll n = 0) : n(n), tree(n<<2|3, Node()) {};

    void down(ll id){
        if(tree[id].lz == 0) return;
        ll delta = tree[id].lz;
        tree[id<<1].lz += delta;
        tree[id<<1].fm += delta;
        tree[id<<1].sum += delta * tree[id<<1].cm;
        tree[id<<1|1].lz += delta;
        tree[id<<1|1].fm += delta;
        tree[id<<1|1].sum += delta * tree[id<<1|1].cm;
        tree[id].lz = 0;
    }

    void update(ll id){
        Node &L = tree[id<<1];
        Node &R = tree[id<<1|1];
        tree[id].sum = L.sum + R.sum;
        tree[id].fm = max(L.fm, R.fm);
        tree[id].cm = 0;
        if(tree[id].fm == L.fm) tree[id].cm += L.cm;
        if(tree[id].fm == R.fm) tree[id].cm += R.cm;
        if(L.fm != R.fm) tree[id].sm = min(L.fm, R.fm);
        else tree[id].sm = max(L.sm, R.sm);
    }

    void assign(ll pos, ll val){
        ll id = 1;
        for(ll lo=1, hi=n; lo<hi;){
            ll mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) id = id<<1, hi = mid;
            else lo = mid + 1, id = id<<1 | 1;
        }
        tree[id].fm = tree[id].sum = val;
        tree[id].cm = 1;
        for(id>>=1; id; id>>=1) update(id);
    }

    ll gmax(ll l, ll r, ll id, const ll &u, const ll &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].fm;
        down(id);
        ll mid = (l + r)>>1;
        return max(gmax(l, mid, id<<1, u, v), gmax(mid + 1, r, id<<1|1, u, v));
    }

    ll gmax(ll l, ll r){
        return gmax(1, n, 1, l, r);
    }

    ll gsum(ll l, ll r, ll id, const ll &u, const ll &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].sum;
        ll mid = (l + r)>>1;
        return gsum(l, mid, id<<1, u, v) + gsum(mid + 1, r, id<<1|1, u, v);
    }

    ll gsum(ll l, ll r){
        return gsum(1, n, 1, l, r);
    }

    ll gmid(ll l, ll r, ll id, const ll &u, const ll &v, const ll &val){
        if(l > v || r < u || tree[id].fm <= val) return 0;
        if(l >= u && r <= v && tree[id].sm < val) return tree[id].cm*(tree[id].fm - val);
        down(id);
        ll mid = (l + r)>>1;
        return gmid(l, mid, id<<1, u, v, val) + gmid(mid + 1, r, id<<1|1, u, v, val);
    }

    ll gmid(ll l, ll r, ll val){
        return gmid(1, n, 1, l, r, val);
    }

    void zmin(ll l, ll r, ll id, const ll &u, const ll &v, const ll &val){
        if(l > v || r < u || tree[id].fm <= val) return;
        if(l >= u && r <= v && tree[id].sm < val){
            tree[id].sum -= tree[id].cm * (tree[id].fm - val);
            tree[id].lz += val - tree[id].fm;
            tree[id].fm = val;
            return;
        }
        down(id);
        ll mid = (l + r)>>1;
        zmin(l, mid, id<<1, u, v, val);
        zmin(mid + 1, r, id<<1|1, u, v, val);
        update(id);
    }
    
    void zmin(ll l, ll r, ll val){
        zmin(1, n, 1, l, r, val);
    }

    void pmin(ll l, ll r, ll id, const ll &u, const ll &v, const ll &mx, ll &k){
        if(l > v || r < u || k == 0 || tree[id].fm < mx) return;
        if(l >= u && r <= v && tree[id].sm < tree[id].fm - 1 && tree[id].fm == mx && tree[id].cm <= k){
            k -= tree[id].cm;
            tree[id].sum -= tree[id].cm;
            tree[id].lz += -1;
            tree[id].fm--;
            return;
        }
        down(id);
        ll mid = (l + r)>>1;
        pmin(l, mid, id<<1, u, v, mx, k);
        pmin(mid + 1, r, id<<1|1, u, v, mx, k);
        update(id);   
    }

    void pmin(ll l, ll r, ll k){
        pmin(1, n, 1, l, r, gmax(l, r), k);
    }
} smt;

ll n, q;
void initialise(int N, int Q, int h[]){
    n = N;
    q = Q;
    smt = SMT(n);
    for(ll i=1; i<=n; i++) smt.assign(i, h[i]);
}

void cut(int l, int r, int k){
    ll pos = -1;
    ll pre = 0;
    for(ll lo=1, hi=smt.gmax(l, r); lo<=hi;){
        ll mid = (lo + hi)>>1;
        ll cnt = smt.gmid(l, r, mid);
        if(cnt <= k){
            pre = cnt;
            pos = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }
    smt.zmin(l, r, pos);
    smt.pmin(l, r, k - pre);
}

void magic(int p, int x){
    smt.assign(p, x);
}

ll inspect(int l, int r){
    return smt.gsum(l, r);
}

#ifdef LOCAL
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin >> n >> q;
    int a[n + 1];
    for(int i=1; i<=n; i++) cin >> a[i];
    initialise(n, q, a);
    while(q--){
        int oper;
        cin >> oper;
        if(oper == 1){
            int l, r, k; cin >> l >> r >> k;
            cut(l, r, k);
        }
        if(oper == 2){
            int p, x; cin >> p >> x;
            magic(p, x);
        }
        if(oper == 3){
            int l, r; cin >> l >> r;
            cout << inspect(l, r) << ' ';
        }
    }
}
#endif

/*

5 3
1 2 3 4 5
1 1 5 5
2 1 5
3 1 5

 6 10
 1 2 3 1 2 3
 1 1 6 3
 3 1 6
 1 1 3 3
 3 1 6
 1 1 3 1000
 3 1 6
 2 1 1000
 3 1 6
 1 1 3 999
 3 1 5

 6 4
 1 2 3 1 2 3
 1 1 6 3
 3 1 6
 1 1 3 3
 3 1 6


 1 2 3 1 2 3
 1 1 2 1 2 2
 0 0 1 1 2 2

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29