| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1321701 | batigol | Bubble Sort Machine (JOI25_bubble) | C++20 | 0 ms | 0 KiB |
/*
*/
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define iter vector<ll>::iterator
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define f(a) for(ll _ = 0; _ < a; _++)
#define fa(i,a) for(ll i = 0; i < a; i++)
#define fab(i,a,b) for(ll i = a; i < b; i++)
#define rf(a) for (ll _ = (a)-1; _ >= 0; --_)
#define rfa(i,a) for (ll i = (a)-1; i >= 0; --i)
#define rfab(i,a,b) for (ll i = (b)-1; i >= a; --i)
#define inf LLONG_MAX/2
#define ninf LLONG_MIN/2
#define input(a,b) a b; cin >> b
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<
T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct node{
ll s, e, val;
node *left, *right;
node(ll s, ll e):s(s), e(e) {
val = 0;
if(s==e) return;
ll mid = (s+e)/2;
left = new node(s, mid);
right = new node(mid+1, e);
}
void update(ll k, ll v){
if(s==e){
val = v;
return;
}
ll mid = (s+e)/2;
if(k<=mid) left->update(k,v);
else right->update(k,v);
val = left->val + right->val;
}
ll query(ll l, ll r){
if(l>e||r<s) return 0;
if(l<=s&&e<=r) return val;
return left->query(l,r) + right->query(l,r);
}
} *st;
struct skib{
ll i, k, n;
bool operator<(skib &other) const{
return (k+n) < (other.k + other.n);
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n; cin>>n;
st = new node(0, n-1);
vector <pll> temp(n);
fa(i,n){
ll a; cin>>a;
temp[i] = {a, i};
}
sort(all(temp),[](pll a, pll b){
return a.fir<b.fir;
});
vector <pll> arr(n);
fa(i,n){
arr[temp[i].sec] = {temp[i].fir, i};
}
ll q; cin>>q;
ll k = 0;
vector <skib> query;
ll counter = 0;
fa(i,q){
ll t; cin>>t;
if(t==1) k++;
else{
ll l, r; cin>>l>>r;
--l; --r;
query.pushb({counter, k, l-1});
query.pushb({counter, k, r});
counter++;
}
}
ordered_set <pll> s;
sort(all(query));
ll j = 0;
ll res[(ll)query.size()/2];
memset(res, -1, sizeof(res));
for(auto i:query){
while(j<n && j<=i.n+i.k){
st->update(arr[j].sec, arr[j].fir);
s.insert({arr[j].fir, arr[j].sec});
j++;
}
if(i.n!=-1){
auto val = s.find_by_order(i.n);
ll cali = st->query(0,val->sec);
if(res[i.i]==-1) res[i.i] = (cali);
else res[i.i] = abs(res[i.i]-cali);
}else{
if(res[i.i]==-1) res[i.i] = (0);
}
}
fa(i, (ll) query.size()/2){
cout<<res[i]<<endl;
return 0;
}