https://www.acmicpc.net/problem/17022
This is one of the most difficult problems I’ve ever solved, I think.
The idea is not complicated.
We have to just find the range sorted in ascending order and put elements in front of that range into proper locations.
Assume that numbers, $3,2,6,4,1,5$, was given as input and let’s check this procedure.
This is a simple process.
The part “sorted” is already sorted and we just should think about how many times an element at the front has to be moved in the sorted part.
So the answer is $k=4$ and it becomes $4,3,5,3$.
The problem is that it takes too much time if we do it one by one.
If we have $N$ numbers, then one more iteration occurs to find a proper spot in “sorted” and the time complexity is $O(N^2)$.
The maximum value of $N$ is $10^5$, so it leads to time exceed.
I found a method called “Segment Tree”.
Simply saying, this is a data structure where a parent has information about its children.
Thus, leaf nodes have information about the smallest segment which is just an element and by going up, the length of each segment is increased and parents have knowledge about that segment.
This is a simply described segment tree.
Its base is a complete binary tree and if the number of data is not a power of $2$, then it is convenient to build it by adding some nodes with default values or empty values.
In this problem, we want to know that if we have a certain value $p$ to put into the sorted range, how many numbers exist smaller than $p$.
After counting that, the total distance to move is the addition of the count and the rest of the values that are not sorted.
Therefore, when we build a segment tree for this situation, we set each leaf node has $0$ or $1$(because each number exist only once) and make each parent have the number of values in the segment.
int tree[262144];
int power = 1;
The tree is made of an array.
The variable power is set to decide the smallest power of $2$ bigger than $N$, which is necessary to make the tree into a perfect binary tree.
In other words, the number of the leaf would be the same as power.
And the smallest power of $2$ bigger than maximum $N$ which is $10^5$ is $262144$.
First, I made the function update to update the value of upper nodes after changing the leaf node’s value and the function query to return the number of values in a certain range.
Both of them is built in bottom-up approach.
void update(int leaf) {
int index = leaf/2;
while(1) {
tree[index] = tree[index*2] + tree[index*2+1];
if (index <= 1) {
break;
}
index /= 2;
}
}
Let’s see update first.
We can see that after updating the value of certain leaf, I put the index of it as a parameter.
Children exist at $2i$ and $2i+1$ according to a parent’s index $i$, so until the function reaches the root, it adds the values of two children and updates it into their parent node.
int query(int left, int right) {
int sum = 0;
left += (power-1);
right += (power-1);
while(1) {
if (left >= right) {
break;
}
if (left % 2 == 1) {
sum += tree[left];
++left;
}
if (right % 2 == 0) {
sum +=tree[right];
--right;
}
left /= 2;
right /= 2;
}
sum += tree[left];
return sum;
}
The function query was a little bit difficult and the most important thing is which node I should consider.
If left is the right child among two children, then we don’t need the information about the parent anymore.
Because the parents contain the information of the sibling also.
So we just stop there and add the value.
And it is the same when right is the left child.
If the case is not either of them, we should go up to the parent.
When left and right become equal, then we just add the value.
These functions are executed similarly to those of the binary tree, so the running time is bounded by $logN$, therefore the total is $O(NlogN)$.
This is the entire code.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> cows;
int tree[262144];
int power = 1;
void update(int leaf) {
int index = leaf/2;
while(1) {
tree[index] = tree[index*2] + tree[index*2+1];
if (index <= 1) {
break;
}
index /= 2;
}
}
int query(int left, int right) {
int sum = 0;
left += (power-1);
right += (power-1);
while(1) {
if (left >= right) {
break;
}
if (left % 2 == 1) {
sum += tree[left];
++left;
}
if (right % 2 == 0) {
sum +=tree[right];
--right;
}
left /= 2;
right /= 2;
}
sum += tree[left];
return sum;
}
int main() {
scanf("%d", &N);
int idx = 0;
for (int i=0; i<N; ++i) {
int p;
scanf("%d", &p);
cows.push_back(p);
if (i > 0) {
if (cows[i] > cows[i-1]) {
continue;
} else {
idx = i;
}
}
}
while(1) {
if (power >= N) {
break;
}
power *= 2;
}
for (int i=idx; i<N; ++i) {
++tree[power + cows[i]-1];
update(power + cows[i]-1);
}
int k = idx;
printf("%d\n", k);
for (int i=0; i<k; ++i) {
int val = 0;
val += (idx-i-1);
val += query(1, cows[i]);
++tree[power + cows[i] - 1];
update(power + cows[i] - 1);
printf("%d ", val);
}
printf("\n");
return 0;
}