Z. Trick or Treap SOLUTION

Page Contents

Z. Trick or Treap Algorithms Thread Treaps Contest

Halloween is almost here! Here in the United States, it is a tradition for young children to dress up as demons and super heros wonder around in the dark very late at night, visit random strangers in their houses, and ask for candy.
Alice and Bob just solved a problem that required them to eat about 109 candies and are very full now, so instead, they will ask their neighbors to either show them a trick, or give them a brand new treap (“trick or treap”)! q times, one of the following will happen:
– 1. This neighbor will given them a new treap node i, with value y. Here, i is the query number.
– 2. This neighbor will perform a trick: if the nodes y and z are not in the same group, he will merge them into the same group, with y’s group to the left of z’s group. Otherwise, he will teach them how to juggle.
– 3. This neighbor will perform a different trick: If the group containing node y contains more than z nodes, he will split the first z nodes from the rest of them. Otherwise, he will teach them Kotlin.
– 4. Alice’s and Bob’s overprotective mother will call and ask them about the sum of values in the group that y is in.
Can you write a bot to pretend to answer the queries for Alice so that she can continue to bother her neighbors in the middle of the night without interruption?
Input
The first line will contain a single integer q. 1≤q≤5∗105 q lines follow. They will look like one of the following:
– 1 y. In this case 0≤y≤105.
– 2 y z. Nodes y and z will already exist.
– 3 y z. Node y will already exist. 0<z.
– 4 y. Node y will already exist.
Output
For each query of type 4, print the sum of the values in the queried group.
Examples
inputCopy
10
1 38788
3 1 1
3 1 2
1 56200
3 1 2
3 1 2
4 4
3 4 4
4 1
3 4 6
outputCopy
56200
38788
inputCopy
8
1 60420
3 1 1
3 1 1
1 49164
2 1 1
2 4 1
2 1 4
1 24036
output

Related :

Related :

Leave a Comment

error: Content is protected !!
Please Click on 1 or 2 Ads to help us run this site.