How to solve a problem in C++ faster than in n^2?

Question

Algorithms

Task text (large images!)

I came up with several solutions, but they are all n^2 in complexity anyway.
For example, you can use a singly linked list and a hash table with pointers to the nodes of the list for encryption. But to get the number of the node in the list, you have to go through the list, and this is already n ^ 2.
Can this problem be solved faster?

Answer 1

There is a solution in O(n log m), but it is technically complicated. Implemented via a balanced binary search tree with an implicit key. Roughly speaking, if each vertex of a balanced tree stores how many vertices are in the subtree, then in such a structure one can search for a vertex by number. You can also insert a vertex at a given position into this tree.
Also, for encryption, it is necessary to maintain an array of pointers for each number to the top of the tree where it is stored. You also need to maintain pointers to the top of the father.
When encrypting, having received a number, you find by the pointer where the top is in the tree. Climbing up, checking from the right or left subtree you came up with, you can calculate what your starting vertex in the tree is. This is the number and output in response. Then you remove the top from the tree and insert it at the beginning.
When decrypting, the read number indicates the ordinal number of the vertex in the tree. Find the vertex, write its value in response, delete the vertex and add it to the beginning.
Edit: There was a wrong solution here via under-skip-list.
There is a slightly easier to implement solution, but on the same idea. Instead of a binary search tree, use a segment tree.
Create a segment with n+m elements. Each character in the alphabet will correspond to one somewhere in this segment. Initially, they occupy the n rightmost positions. Their order will be the same permutation from the condition. The segment tree will calculate the sum. In such a tree, you can find the k-th unit using the logarithm (recursive descent) and find out what order this unit is (a request for the sum on the segment 0..i-1). Also, for each character of the alphabet, store exactly where on the segment the corresponding unit lies, and for each element on the segment, which character it corresponds to.
When encrypting, you find a unit for an alphabet character, consider what it is in order and output this number. then move this unit to the left of all units. This is done simply - on the i-th operation, you need to stick a unit in the position m-i + 1.
When decrypting, you find the k-th unit, print the character corresponding to it, and move the unit to the left of the others.

Answer 2

The complexity here is linear: O(n)
Encryption/decryption is one-pass.
When encrypting:
On the left - the symbol itself (its code), on the right - the symbol with the code of its position.
(in the center - "mixture")
Explanation - in the reverse order.
PS:

But to get the number of the node in the list, you have to go through the list, and this is already n ^ 2.

you need to add one more face to the cube with displacement vectors.