Z. Trick or Treap SOLUTION

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?
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.
For each query of type 4, print the sum of the values in the queried group.
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
1 60420
3 1 1
3 1 1
1 49164
2 1 1
2 4 1
2 1 4
1 24036

Related :

Related :

Leave a Comment

5 × 5 =