Блог пользователя 901001

Can some tell me how to solve the #88 problem D
Автор 901001, 13 лет назад, По-английски
I view some people's code. But I cannot understand their solutions. can some explain it?
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

You can write down what every layer is like,such as the first layer is [1,2,3,4],the second layer is [1,3][2,4],and the third layer is [1][3][2][4]


Suppose a [...] is a sequence

You can see,the ith layer has 2^(i-1) sequences,and each sequence is a arithmetic progression

First,we don't consider the value of it,only considering [l,r],and a query can be devided into some part of these sequence,just like the segment tree,a query can be devided into not more than 2logn sequences

Now,each sequence is a arithmetic progression and you can count the sum of the value in [u,v] easily


I'm not good at English,maybe the words are strange......
→ Ответить