Подскажите структуру данных(В этой структуре в некотором виде хранится список целых чисел (числа могут повторяться, априори порядок неважен)), для которой будут эффективно выполняться следующие операции:

1) Добавление нового элемента

2) Удаление элемента с данным значением (не по индексу)

3) Поиск минимального, максимального элемента

4) Поиск медианного элемента

В этой реализации алгоритма Дейкстры граф с весовыми ребрами хранится в виде vector < vector < pair<int,int> > > g.

Допустим нужно написать программу, в которой потребуется пару раз применить эту реализацию алгоритма Дейкстры, но кроме этого в ней потребуется (несколько раз) по паре вершин v и to найти вес ребра (v,to). Я пытаюсь понять какой тут правильный подход. Просто искать в векторе g[v] элемент i, в котором g[v][i].first==to (тогда g[v][i].second будет искомым) или завести map, в котором хранить все расстояния? Как в таком случае правильно организовать поиск веса ребра по его вершинам?

Правильно ли я понимаю, что реализация алгоритма отсюда http://e-maxx.ru/algo/lca работает только для бинарного дерева, в то время как реализация алгоритма отсюда http://e-maxx.ru/algo/lca_simpler работает для любого дерева?

Нам дан C++ map<int,int> m; Как эффективно вычислить максимальное x, такое что m[x]!=0 и какая асимптотика одного такого вычисления?

Мне в голову приходит запустить цикл for с реверс-итератором и т.к. элементы упорядочены(?), то первое значение как раз и будет x. Даже если это работает, то я совсем не уверен, что это эффективный метод.

Пусть нам дан массив int a[n] . И требуется найти все коэффициенты многочлена (x+a[0])*...*(x+a[n-1]) Если считать в лоб, то будет сложность O(n^2). Есть ли способы считать быстрее? Есть ли смысл здесь применять быстрое преобразование Фурье? И есть ли другие хорошие подходы в этом случае. UPD. Как обычно считаю, что все операции производятся по модулю большого числа, если это здесь вдруг имеет значение.

Решил тут попробовать поучаствовать в тренировке. Понял, что даже А сложновата и решил посмотреть разбор — его не оказалось. Решения других людей посмотреть нельзя(????).

Условие задачи

Единственное упрощение, до которого я додумался — можно считать, что запросов одинаковой продолжительности меньше 3, поэтому n<=60 вместо n<=400 . Но для полного перебора это все равно многовато.