can anyone help me with the chgoram problem of august challenge

# | User | Rating |
---|---|---|

1 | tourist | 3645 |

2 | Radewoosh | 3403 |

3 | Um_nik | 3348 |

4 | LHiC | 3336 |

5 | Benq | 3316 |

6 | V--o_o--V | 3275 |

7 | mnbvmar | 3241 |

8 | yutaka1999 | 3190 |

9 | ainta | 3180 |

10 | Petr | 3106 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 177 |

3 | rng_58 | 164 |

4 | PikMike | 161 |

5 | Vovuh | 160 |

6 | majk | 158 |

7 | 300iq | 154 |

7 | antontrygubO_o | 154 |

9 | Um_nik | 151 |

10 | kostka | 149 |

can anyone help me with the chgoram problem of august challenge

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/20/2019 07:10:39 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Here is a link for some quick explanation.

For example, let's suppose that restaurants must be in increasing order: 1, 2, 3.

Assume that you are checking all the vertexes as the middle one. Now you want to know how many can be the first and how many can be the last, of course, they must belong to different subtrees of our current vertex.

For every vertex

`i`

, go through each vertex`j`

that share an edge with`i`

. Try to visualize it as a splitting the tree into two subsets, where subset`A`

is from`j`

to all other vertexes connected to it except from`i`

and subset`B`

the remaining vertexes.Also, let

`val`

be the value of our current vertex. We need to count how many`(x, y)`

pairs we have, where:`x`

is in`A`

`y`

is in`B`

`x < val < y`

`L`

= how many values are less than`val`

in`A`

`R`

= how many values are greater than`val`

in`B`

`current_answer`

=`L`

*`R`

If the middle value is not 2, after you sum the answer for every vertex, you need to divide the

`total_answer`

by two, to remove some repeted pairs.The biggest problem now is: how to do fast queries on how many values are less/greater than

`val`

in a subtree?I have solved this with persistent segment tree, where I do a query in an interval that represent this subtree. Like:

`st[current_version]->query(x, y) - st[current_version - size_of_this_subtree]->query(x, y)`

The problem have a tight time limit if you code with persistent segment tree, you can use other faster methods to do this offline, like the small to large trick.