제출 #1284733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284733		Math4Life2020	Bubble Sort Machine (JOI25_bubble)	C++20	컴파일 에러	0 ms	0 KiB

bubble

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = (1LL<<19); const ll E = 19;


ll v2(ll x) {
    if (x==0) {
        return 100;
    }
    return __builtin_ctz(x);
}


struct st { //segtree
    vector<ll> st0 = vector<ll>(2*Nm,0);
    void upd(ll x, ll v) {
        ll p = x+Nm;
        do {
            st0[p]+=v;
            p=p/2;
        } while (p>0);
    }
    ll qry(ll a, ll b) {
        if (a>b) {
            return 0;
        }
        ll va = v2(a); ll vb = v2(b+1);
        if (va<vb) {
            return (st0[(1LL<<(E-va))+(a>>va)]+qry(a+(1LL<<va),b));
        } else {
            return (st0[(1LL<<(E-vb))+(b>>vb)]+qry(a,b-(1LL<<vb)));
        }
    }
};

st stb; //for B[N]
st stav; //segtree of active values (b-index to value)
st stan; //segtree of active indices (normal)
st stab; //segtree of active indices (b-index)
st stiv; //segtree of inactive values 

void act(ll x, ll b, ll a) {
    //cout << "act: "<<x<<","<<b<<","<<a<<"\n";
    stiv.upd(x,-a);
    stav.upd(b,a);
    stan.upd(x,1);
    stab.upd(b,1);
}

ll clc(ll x) {
    if (x==-1) {
        return 0;
    }
    //first get b-index of the x+1th smallest term
    ll bmin = 0; ll bmax = Nm-1;
    while (bmin != bmax) {
        ll bcen = (bmin+bmax)/2;
        ll nact = stab.qry(0,bcen); //sum of all in [0,bcen]
        if (nact==(x+1)) {
            bmin = bcen; bmax = bcen;
        } else if (nact>(x+1)) {
            bmax = bcen-1;
        } else {
            bmin = bcen+1;
        }
    }
    //cout << "bmin="<<bmin<<"\n";
    return (stav.qry(0,bmin));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    ll A[N];
    ll B[N]; //compressed A
    vector<pii> vb;
    for (ll i=0;i<N;i++) {
        cin >> A[i];
        vb.push_back({A[i],i});
        stiv.upd(i,A[i]);
    }
    sort(vb.begin(),vb.end());
    ll srtps[N+1];
    srtps[0]=0;
    for (ll j=0;j<N;j++) {
        B[vb[j].second]=j;
        srtps[j+1]=srtps[j]+vb[j].first;
    }
    vector<ll> incl[N]; //indices (vector) to add at a given time T
    ll T = 0; //time
    for (ll x=0;x<N;x++) {
        incl[stb.qry(B[x]+1,Nm-1)].push_back(x);
        stb.upd(B[x],1);
    }
    for (ll v0: incl[0]) {
        act(v0, B[v0], A[v0]);
    }
    ll Q; cin >> Q;
    for (ll q=0;q<Q;q++) {
        ll tj; cin >> tj;
        if (tj==1) {
            if (T<(N-1)) {
                stan.upd(T,-1);
                T++;
                for (ll v0: incl[T]) {
                    act(v0,B[v0],A[v0]);
                }
            }
        } else {
            ll l,r; cin >> l >> r; l--; r--;
            ll ans = 0;
            if (r>=(N-T)) {
                ll l1 = max(l,N-T);
                // ans += ((r*(r+1))/2)-((l1*(l1+1))/2);
                ans += srtps[r+1]-srtps[l1];
                //cout << "anst1="<<ans<<"\n";
            }
            if (l<=(N-1-T)) {
                ll r1 = min(r,N-T-1)+T;
                ll l1 = l+T;
                ans += stiv.qry(l1,r1);
                //cout << "anst2="<<ans<<"\n";
                ll x = stan.qry(0,l1-1)-1;
                ll y = stan.qry(0,r1)-1; //get all active values with b-indices in (x,y]
                //cout << "x,y="<<x<<","<<y<<"\n";
                ans -= clc(x); //calculate
                ans += clc(y);
                //cout << "anst3="<<ans<<"\n";
            }
            cout << ans << "\n";
        }
    }
}