#include #ifdef ATCODER #include using namespace atcoder; using mint = modint998244353; #endif #ifdef ONLINE_JUDGE #else #include using namespace atcoder; using mint = modint998244353; #endif using namespace std; template using vec = vector; using ll = long long; using ull = unsigned long long; using vi = vec; using vs = vec; using si = set; using sll = set; using vc = vec; using vvi = vec; using vll = vec; using vvll = vec; using vsi = vec; using vsll = vec; using vd = vec; using vvd = vec; using pii = pair; using pll = pair; using mii = map; using mll = map; using msi = map; using vpii = vec; using vpll = vec; using spii = set; using spll = set; using vb = vector; using vvb = vector; #define rep(i,j,n) for(ll i=j;i=j; i--) #define rp(i,n) rep(i,0,n) #define rrp(i,n) rrep(i,0,n) #define all(v) v.begin(), v.end() #define pb push_back #define ins insert #define yes cout<<"Yes"< seg(n); //S:中身型 op:左右合成 e:初期値 //F:遅延型 mapping:遅延適用後の要素 composition:遅延合成( 関数f(g()) ) id:遅延初期値(何もさせない) /* using S = double; using F = int; S op(S a,S b) { return min(a, b); } S e() { return lmax; } S mapping(F x, S a) {//xをaに作用(x初期値に注意) if (x != 0)return x; else return a; } F composition(F f, F g) {//fの方が後(f初期値に注意) if (f != 0)return f; else return g; } F id() {return 0;}*/ //cout< 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...) template//keyの型、値の型 struct topk { multiset> top; multiset> bot;//昇順の時はgreaterを消す map ktov; int k = 0; ll tsum = 0, asum = 0; void ar() {//個数整理 while (top.size() > k) { auto it = top.end(); it--; bot.insert(*it); tsum -= it->fi; top.erase(it); } while (top.size() < k && bot.size() != 0) { auto it = bot.begin(); top.insert(*it); tsum += it->fi; bot.erase(it); } } void set(int newk) {//最初に必ず呼ぶ k = newk; ar(); } void erase(T1 a) { if (ktov.find(a) != ktov.end()) { auto b = ktov[a]; if (top.find({ b,a }) != top.end()) { tsum -= b; asum -= b; top.erase({ b,a }); ar(); } else if (bot.find({ b,a }) != bot.end()) { asum -= b; bot.erase({ b,a }); ar(); } ktov.erase(a); } } void insert(T1 a, T2 b) {//兼update erase(a); ktov[a] = b; if (top.sz != 0 && (--top.end())->fi > b) {//昇順の時は> top.insert({ b,a }); asum += b; tsum += b; } else { bot.insert({ b,a }); asum += b; } ar(); } void insert(pair a) { insert(a.fi, a.se); } int bsum() { return asum - tsum; } auto find(T1 a) { return ktov.find(a); } T2 operator[](T1 a) { return ktov[a]; } }; int main() { int n, k, q; cin >> n >> k >> q; vll a(n); rp(i, n) cin >> a[i]; topk r; r.set(k); rp(i, n)r.insert(i, a[i]); while (q--) { ll x; cin >> x; if (x == 1) { ll y; cin >> y; a.pb(y); r.insert(ll(a.sz) - 1, y); } if (x == 2) { ll y; cin >> y; auto it = r.top.end(); it--; y += it->first; ll b = it->second; r.erase(b); r.insert(b, y); } if (x == 3) { auto it = r.top.end(); it--; cout << it->first << endl; } } }