for this problem UVA 12501
How to solve this problem with segment tree ?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
for this problem UVA 12501
How to solve this problem with segment tree ?
Name |
---|
something like that. you need to test it, there can be a lot of bugs.
i have not understood your code!!
can you give me the idea to solve the problem ?
all what you need to solve the problem: 1) you need to know how to combine segments. you can find this in my code
2) google "lazy propagation segment tree".
i am not new to segment tree..
I just want to know how to query for this problem. how to combine ? for this interval: [2,5] how to give the ans like this 1*a[2]+2*a[3]+3*a[4]+4*a[5]
btw thanks for the help so far.. :)
let's divide interval [2, 5] into [2, 3] and [4, 5]
1*a[2]+2*a[3]+3*a[4]+4*a[5] = 1*a[2]+2*a[3]+ 2*(a[4]+a[5]) +1*a[4]+2*a[5]
I didn't think of that! Thank you very much for the insight :)
updated code