Модификация избранных элементов на отрезке

Доброго времени суток.
Имеется следующая задача:
Есть одномерный массив A целых чисел  размерностью порядка N=10^6.
И есть также 3 вида запросов:
1. Параметры запроса - 4 целых числа B,V,L,R.
    Сделать все числа на отрезке [L,R]  (0<=L,R<N) для которых

 A[i]==B (L<=i<=R)

равными заданному V.
2. Параметры запроса - 3 целых числа V,L,R.
   Требуется посчитать количество чисел на отрезке [L,R] равных V.
3. Параметр запроса - целое число K.
  Требуется вернуть значение A[K].

Количество запросов также примерно 10^6.
Существует ли структура данных, позволяющая реализовать выполнение каждого из этих запросов за время ln(N) ну в крайнем случае
ln^2(N)?
Список запросов имеется заранее (не онлайн режим).

Если да, то расскажите как это можно сделать.
Спасибо)