vector<pair<int,int>> blocks[num_of_arrays];

// ...

int number;
cin >> number; // number requested
int f = frequency[number];
pair<int,int> x = {frequency, number};

int id = 0; // first array
while (id + 1 < num_of_arrays && blocks[id + 1][0] >= x) // O(sqrt(n))
    ++id;
int pos = 0;
while (pos + 1 < blocks[id].size() && blocks[id][pos + 1] >= x) // O(sqrt(n))
    ++pos;

// we found array (id), and position in the array (pos)
// thus can do, for example, insertion:
blocks[id].insert(blocks[id].begin() + pos, x); // size of blocks[id] <= 2 * sqrt(n)

// or deletion:
blocks[id].erase(blocks[id].begin() + pos, x); // size of blocks[id] <= 2 * sqrt(n)