901001's blog

Can some tell me how to solve the #88 problem D
By 901001, 15 years ago, In English
I view some people's code. But I cannot understand their solutions. can some explain it?
  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
15 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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......
→ Reply