Treap data structure will be extremely useful ;)

You can do these types of operations quite easily with any balanced binary search tree. I prefer a Treap because the tree rotations that occur after insertion/deletion are very simple. Others might be a splay tree, red-black tree, AVL, etc. You can keep track of the number of elements stored in the subtree of each node in your tree, then it becomes easy to count the number of elements smaller than X. You can insert, delete and count the kth largest in O(log(N)) time.

You can take the sequence and the insert queries first. Sort the elements according to their values (including insert queries) and give them sorted indices in the final sequence. Set all elements position of the initial sequence to 1 and insert queries to 0. For each insert query you can update the element's position to 1. To get the Kth element you just need to find the smallest index where the cumulative sum is K from the first position. You can easily manage this update and find query with a segment tree. Complexity of per insert and find query of this technique is O(log(N)).

Hello! You can learn about Indexed Set in C++ (it is policy-based data structure). Antti Laaksonen (pllk) also wrote about that in his book (here you can download and find about Indexed Set in page 44).

Indexed Set can find position of x and x'th element in set in O(logn) but constant of complexity is a little big. Here I wrote program with Indexed Set for finding k'th maximum in array:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int main() {
    /***
    indexed_set s;
    s.insert(2);
    s.insert(3);
    s.insert(7);
    s.insert(9);
    auto x = s.find_by_order (2); /// find element in index 2 (0 based index)
    int y = s.order_of_key (7);  /// position of 7 in set
    cout << *x << " " << y << endl;
    ***/
    indexed_set s;
    int q, type, k;
    cin >> q;
    while (q --) {
        cin >> type >> k;
        if (type == 1)
            s.insert (k); /// insert element
        else {
            auto x = s.find_by_order (s.size() - k); /// set is sorted, so s.find_by_order(k) gives us k'th minimum, replacing k by (s.size() - k) will give us index of k'th maximum
            cout << *x << endl;  /// print k'th largest
        }
    }
    return 0;
}

UPD: I found problem like that with delete update, original solution is by treap, but my code with Indexed Set got AC 135ms. https://www.e-olymp.com/en/problems/687
Solution: https://pastebin.com/10iu04L9

You can solve this problem with O(log(n)²) per query. Just make a binary search over X and use a BIT (Segtree, whatever) to determine how many elements are bigger than X, with this you can determine if you have to go left or right.

You can do better using just a SegTree.

No hard data structures are needed if K is constant (see replies). Please write more detailed constraints.

priority_queue<int> q;

// preparation
for (int i = 0; i < n; ++i) {
    q.push(a[i]);
    if (q.size() > k) q.pop();
}

// operation 1
q.push(X);
q.pop();

// operation 2
cout << q.front() << endl;

Could you give the link to the problem? Thanks!