Разбор задачи C. Проверка на сообразительность

Тема: нахождение наидлиннейшей возрастающей подпоследовательности, сортировка, бинарный поиск
Сложность: средняя

С первого взгляда кажется это известная задача на поиск наибольшей общей подпоследовательности (LCS), которая решается за время `O(N*M)`, но фраза "В каждой из последовательностей все числа попарно различны" упрощает задачу. Так как каждый элемент второй последовательно встречается не более одного раза в первой последовательности, то выписав последовательность номеров, под которым элемент из второй последовательности идет в первой последовательности (только для общих элементов последовательностей), мы сведем задачу к поиску наидлиннейшей возрастающей подпоследовательности, который выполняется за `O(N*log(N))`.
Подробное изложение этого алгоритма можно посмотреть на сайте e-maxx.ru

int d[MAXN];
k=0;
for (int i=0; i<n; i++) {
	int j = int (lower_bound (d, d+k, a[i]) - d);
        if(j==k)
           d[k++]=a[i];
        else	if (a[i] < d[j])
	  d[j] = a[i];
}

Для ускорения поиска элементов в первой последовательности необходимо использовать map или быструю сортировку (см. разбор задачи 1692. Шпаги) и бинарный поиск в получившейся упорядоченной последовательности (см. разбор задачи 1366. Дипломы).