Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

tunyash's blog

By tunyash, 8 years ago, In Russian,

GSS4.

Собственно, нужно уметь брать сумму на отрезке и уметь каждый элемент отрезка заменять квадратным корнем из него, округленным вниз. Сумма всех элементов изначально не превосходит 1018

Я придумал решение за ( и я не уверен ли это). Идея тупая: каждое число станет единицей, если взять корень 7 раз. Тогда заведем 7 декартовых деревьев, первое из которых будет хранить текущий массив, второе — корни из его элементов, третье — корни из корней и так далее. при запросе на замену на корень вырежем из каждого нужный отрезок и сделаем циклический сдвиг вырезанных отрезков. Отрезок дерева, который мы вытащили из самого первого дерева зальем единичками (после этого вставим в последнее).

Такое решение дает ТЛ. Интересно, можно ли быстрее и/или проще?

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nobody answered! Why??? :'(

I was doing the same problem and got stuck. -_-

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Actually, two solutions were proposed. But in Russian.