3252. Range Sum Query

 

Дан массив целых чисел, изначально заполненный нулями. С ним необходимо производить два типа операций:

·        ! i x – присвоить ячейке i значение x;

·        ? l r – узнать сумму значений на отрезке [l, r].

 

Вход. Первая строка содержит размер массива n и количество запросов m (1 ≤ n ≤ (109 + 7), 1 ≤ m ≤ 2 * 105). За ним следуют m запросов по одному в строке.

В процессе работы программы необходимо поддерживать два числа P и Q. Изначально P = 91, Q = 47.

Запрос вида "! A B" обозначает, что в ячейку (A + P) mod n необходимо записать число (B + Q) mod (109 + 7).

Запрос вида "? A B" обозначает, что необходимо посчитать сумму между элементами (A + P) mod n, (B + Q) mod n включительно. Пусть ответ равен Z. Тогда необходимо изменить числа P и Q следующим образом:

P = (P * 31) + Z mod (109 + 7),

Q = (Q * 29) + Z mod (109 + 7)

Нумерация элементов начинается с нуля.

Все входные числа не превосходят 109 + 7.

 

Выход. Для каждого запроса на сумму нужно вывести ответ на него в отдельной строке.

 

Пример входа 1

Пример выхода 1

10 8

! 1 4

! 2 5

? 3 6

! 4 1

? 5 9

! 1 4

? 5 9

? 5 9

52

1416

42558

103

 

 

Пример входа 2

Пример выхода 2

15 6

! 1 1

! 5 2

? 5 14

! 8 7

? 1 4

? 4 13

97

0

0

 

 

РЕШЕНИЕ

дерево отрезков - динамическое

 

Анализ алгоритма

Построим дерево отрезков на указателях, поддерживающее сумму. Изначально дерево будет состоять из одного корня, покрывающего интервал [0; n – 1] (индексы изменяемых и запрашиваемых отрезков берутся по модулю n). Вершины в нем будем создавать по мере надобности. С каждым запросом у нас будет появляться не более O(log2n) узлов. Следовательно требования программы по памяти составят O(m log2n).

 

Пример

Пусть m – входной массив, изначально заполненный нулями. Для первого примера последовательность реальных запросов имеет вид:

m2 = 51;

m3 = 52;

sum[3; 4] = 52;

m7 = 1416;

sum[4; 8] = 1416;

m0 = 42455;

sum[0; 4] = 42558;

sum[2; 6] = 103;

 

Реализация алгоритма

Объявим константу модуля 109 + 7.

 

#define MOD 1000000007

 

Объявим структуру вершины дерева: указатели на левого и правого сыновей и значение суммы на отрезке.

 

struct tree

{

  tree *left,*right;

  long long sum;

  tree(): left(NULL), right(NULL), sum(0) {}

};

 

Объявим динамическое дерево отрезков root.

 

tree* root = new tree();

 

Возвращает сумму в узле дерева t. Если t равно NULL, то возвращаем 0.

 

long long get_sum(tree *t)

{

  return (t) ? t->sum : 0;

}

 

Вершине t соответствует отрезок [left; right]. Совершаем изменение элемента: m[pos] = val.

 

void update(tree *t, int left, int right, int pos, int val)

{

 

Если дошли до листа, то значение суммы на отрезке равно val.

 

  if(left == right)

  {

    t->sum = val;

    return;

  }

 

Делим отрезок [left; right] на [left; mid] и [mid + 1; right].

 

  int mid = (left + right) / 2;

 

Смотрим, в каком из сыновей (левом или правом) находится индекс pos. Создаем сына если его еще нет и рекурсивно производим замену в нем.

 

  if(pos <= mid)

  {

    if(t->left == NULL) t->left = new tree();

    update(t->left,left,mid,pos,val);

  }

  else

  {

    if(t->right == NULL) t->right = new tree();

    update(t->right,mid+1,right,pos,val);

  }

 

Пересчитываем суммы в вершине как сумму в сыновьях. Если сын равен NULL, то get_sum возвращает 0.

 

  t->sum = get_sum(t->left) + get_sum(t->right);

}

 

Вершине t соответствует отрезок [left; right]. Функция get возвращает сумму на отрезке [L; R].

 

long long get(tree *t, int left, int right, int L, int R)

{

 

  if(L > R) return 0;

 

Если отрезок запроса [L; R] совпадает с фундаментальным отрезком [left; right], который хранится в вершине t дерева, то возвращаем находящееся в ней значение суммы.

 

  if(L == left && R == right) return t->sum;

 

Делим отрезок [left; right] на две части [left; mid] и [mid + 1; right].

 

  int mid = (left + right) / 2;

 

Вычисляем сумму в левом и правом поддереве. Если сын равен NULL, то возвращаем 0.

 

  long long s1 = (t->left) ? get(t->left,left,mid,L,min(mid,R)) : 0;

  long long s2 = (t->right) ? get(t->right,mid+1,right,max(L,mid+1),R) : 0;

  return s1 + s2;

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d %d\n",&n,&m);

P = 91; Q = 47;

 

Последовательно обрабатываем m запросов.

 

while(m--)

{

  scanf("%c %d %d\n",&ch,&l,&r);

  if(ch == '!')

    update(root,0,n-1,(l+P)%n,(r+Q)%MOD);

  else

  {

    l = (l + P) % n;

    r = (r + Q) % n;

    if(l > r) swap(l,r);

    long long z = get(root,0,n-1,l,r);

    printf("%lld\n",z);

 

    P =((P * 31LL) + z) % MOD;

    Q =((Q * 29LL) + z) % MOD;

  }

}