# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Name |
---|
Auto comment: topic has been updated by code_tycoon (previous revision, new revision, compare).
Seems solvable with a simple segment tree.
Maintain sum of triplets, sum of pairs, and sum of elements in each node of a segment tree. Merging nodes should be pretty straightforward.
can u elaborate a bit on the merging part in the segment tree.
Say you're merging two nodes a and b, into res.
res.triplets = a.triplets + b.triplets + (a.pairs * b.sum) + (a.sum * b.pairs)
res.pairs = a.pairs + b.pairs + a.sum * b.sum
res.sum = a.sum + b.sum
Initialize single element nodes with (0, 0, arr[i]).
I'm not sure how to explain the general process, but try defining what you're trying to calculate into simpler things, even if it means defining new things to store. For e.g. in triplets, either they'll be completely on left or right side, or 2 will be on one side, one on the other. How do you get product of 2 at a time? They can be both on left, both right, or one each side. Keep doing until you have merging logic for all things you store in your segment tree nodes.
Do these for a bit of practice:
https://www.spoj.com/problems/GSS1/ https://www.spoj.com/problems/GSS3/ https://www.spoj.com/problems/GSS5/ https://www.codechef.com/problems/HARRYGOF
thanks it worked!! Here is the link to the solution if someone wants to refer: https://pastebin.com/ixKP3Ugk