# APIO 2019 - Bridges

Author: Andi Qu

The main idea in this problem is to use square-root decomposition on queries.
For convenience, call type 1 queries **updates** and type 2 queries
**calculations**.

First, split the queries into blocks of about $\sqrt N$ queries. In each block, there are $\mathcal{O}(\sqrt N)$ updates or calculations. For each block:

- Split the bridges into two groups:
**changed**and**unchanged**. - If we sort the calculations and unchanged bridges in decreasing order of weight, we can simply use DSU to find which nodes are connected from those bridges alone.
- These connected nodes are constant for all calculations in the current block

- To handle the updates:
- Iterate over the queries in the current block (without sorting)
- If the query is an update, simply update the bridge's weight
- If the query is a calculation, iterate through each changed bridge and connect the nodes if the weight limit is above the query's weight limit
- This works because this means the answer for the current query is dependent only on previous updates
- The key thing here is that we need a way to roll back DSU unions, since the set of "good" bridges may differ from query to query
- To achieve this, we simply use DSU with path balancing only and keep a stack of previous DSU operations

## Implementation

**Time Complexity:** $\mathcal{O}((Q + M) \log N \sqrt Q )$

However, it is possible to remove the log factor as mentioned in this comment.

C++

#include <bits/stdc++.h>#define FOR(i, x, y) for (int i = x; i < y; i++)typedef long long ll;using namespace std;const int B = 1000;int n, m, q;stack<int> stck;

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!