35179번 - Dodgeball Diplomacy 서브태스크다국어인터랙티브

A region consists of $N$ cities, numbered from $1$ to $N$. These cities may establish treaties, which indicate their willingness to collaborate with each other.

An alliance is a group of cities where each city is connected to every other city in the group through one or more treaties. The size of an alliance is the number of cities that belong to that alliance.

Each treaty has a length, representing the number of pages used to draft it. To reduce bureaucracy, cities will occasionally remove the longest active treaty (i.e., the one with the highest page count).

Beyond administrative matters, the cities also engage in dodgeball rounds between alliances. A dodgeball round follows the following rules:

• Each alliance forms a team.
• Alliances are paired up to play against each other.
• If the number of alliances is odd, one team will play against an empty alliance of size $0$.
• The unfairness score of a match between two alliances of sizes $A$ and $B$ is $|A-B|$.
• The total unfairness score for a round is the sum of unfairness scores across all matches.

You must determine the minimum possible total unfairness score by optimally pairing the alliances.

You must support $Q$ queries of the following types:

• a: Add a treaty between cities $u$ and $v$ with $p$ pages.
• r: Remove the longest treaty (the one with the highest page count). All page counts are unique.
• d: Compute the minimum unfairness score for a dodgeball round based on the current alliances.

Queries of type d must be answered immediately upon request, before processing any further queries.

The program should read:

• Line 1: $N$ $Q$
• Next $Q$ lines: one of
  • a $u$ $v$ $p$
  • r
  • d

For each query of type d, the program should immediately output the corresponding answer before processing further queries. You must also flush the output immediately, e.g.:

• C++: std::cout << std::endl;
• Python: print("", flush=True)

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 500000$
• $1 \leq p \leq 10^9$
• $1 \leq u, v \leq N$
• $u \neq v$ for each a query
• No duplicate active treaty between $u$ and $v$
• All page counts $p$ are unique