In Bubbleland a group of special programming forces gets a top secret job to calculate…
- User
In Bubbleland a group of special programming forces gets a top secret job to calculate the number of potentially infected people by a new unknown virus. The state has a population of n people and every day there is new information about new contacts between people. The job of special programming forces is to calculate how many contacts in the last k days a given person had.
The new virus has an incubation period of k days, and after that time people consider as non-infectious. Because the new virus is an extremely dangerous, government mark as suspicious everybody who had direct or indirect contact in the last k days, independently of the order of contacts.
This virus is very strange, and people can't get durable immunity.
You need to help special programming forces to calculate the number of suspicious people for a given person (number of people who had contact with a given person).
There are 3 given inputs on beginning n where n is population, q number of queries, k virus incubation time in days. Each query is one of three types:
- (x, y) person x and person y met that day (x ≠ y).
- (z) return the number of people in contact with z, counting himself.
- The end of the current day moves on to the next day.
Input
The first line of input contains three integers n (1 ≤ n≤ 10^5) the number of people in the state, q (1 ≤ q≤ 5×10^5) number of queries and k (1 ≤ k≤ 10^5) virus incubation time in days.
Each of the next q lines starts with an integer t (1 ≤ t≤ 3) the type of the query.
A pair of integers x and y (1 ≤ x, y ≤ n) follows in the query of the first type (x ≠ y).
An integer i (1 ≤ i≤ n) follows in the query of the second type.
Query of third type does not have the following number.
Output
For the queries of the second type print on a separate line the current number of people in contact with a given person.
Examples
Input
5 12 1 1 1 2 1 1 3 1 3 4 2 4 2 5 3 2 1 1 1 2 1 3 2 2 1 3 2 1
Output
4 1 1 3 1
Input
5 12 2 1 1 2 1 1 3 1 3 4 2 4 2 5 3 2 1 1 1 2 1 3 2 2 1 3 2 1
Output
4 1 4 4 3
Input
10 25 2 1 9 3 2 5 1 1 3 1 3 1 2 2 1 8 3 1 5 6 3 1 9 2 1 8 3 2 9 1 3 1 2 5 1 6 4 3 3 2 4 3 1 10 9 1 1 7 3 2 2 3 1 5 6 1 1 4
Output
1 1 5 2 1 1
Note
Pay attention if persons 1 and 2 had contact first day and next day persons 1 and 3 had contact, for k>1 number of contacts of person 3 is 3(persons:1,2,3).
Assistant
We need to understand the problem fully. The scenario: There is a population of n people. We have a series of queries, with time moving forward. There are three types of queries:
-
(x, y): person x and y meet that day (the current day). The meeting is undirected contact.
-
(i): output the number of suspicious people for person i, which is defined as the number of people who had direct or indirect contact with i within the last k days, including i themselves. Essentially, we need the size of the connected component of the graph formed by edges (contacts) that occurred in the last k days, containing person i, at the moment of the query. However note that the graph changes over time: edges have timestamps (day), and they expire after k days. When we have a "3" query, we move to the next day. So the timeline is divided into days. There can be multiple type-1 queries per day. At the end of the day, we advance to the next day. So edges added during day d have the same timestamp (day d). After k days, those edges are no longer considered. So we need to maintain a dynamic graph with edge insertions (type-1) and edge deletions (after exactly k days, edges expire). However there are no explicit deletion queries; they happen implicitly when days pass. So we need to handle edge expiration after k days. Also we need to answer queries for component size at any point (including during the same day, after some contacts have happened but before day ends). The contacts of the same day are considered for the same incubation period: edges added on day d are valid for days d, d+1, ..., d+k-1? Actually the problem says: "virus incubation time of k days, and after that time people consider as non-infectious. ... suspicious everybody who had direct or indirect contact in the last k days, independently of the order of contacts." So if we are at day T (some day number, starting from day 1?), then contacts that occurred on days T-k+1 through T are considered (i.e., within last k days inclusive). The query "3" moves on to the next day. So initially we start at day 1? The problem statement: "The first line ... k virus incubation time in days. Each of the next q lines... Query of third type does not have the following number." It doesn't specify an initial day number, but we can assume day 1 at start. Each "3" increments the current day by 1. So we have to process q queries sequentially, with a current day counter.
We need to support:
- Insert edge (x,y) with timestamp current_day (the day when the query occurs, before any "3"? Actually type-1 queries occur on the current day. So the edge's timestamp = current_day.
- When we process a "3" query, we increment current_day, and edges that were added exactly k days ago (i.e., at day current_day - k) should expire. Since we move to the next day, after moving, the set of active edges are those with day > (current_day - k) after increment? Actually careful: Suppose before processing any queries, we are at day 1. We may have type-1 queries on day 1. Then after some queries, a "3" moves to day 2. At that point, edges from day 1 are still valid because they are within last k days (if k >= 2? Actually "last k days" at day 2 includes day 2 and day 1 if k=2, or just day 2 if k=1? For k=1, only contacts from day 2 are considered. So after moving to day 2, for k=1, edges from day 1 expire. So expiration happens exactly when the day becomes > (edge_day + k - 1)? At day D, the active edges are those with edge_day >= D - k + 1 (if D - k + 1 can be less than 1, maybe day 1 start). Let's define: The current day number cur_day (starting from 1). When we answer query type 2 at any point, we consider contacts "in the last k days". That includes contacts that happened on day cur_day (since it's the current day). So active edges are those where edge_day >= cur_day - k + 1 and <= cur_day. So edges expire when cur_day - k + 1 > edge_day, i.e., cur_day > edge_day + k - 1. When we process a "3", we increment cur_day. Then after increment, edges with edge_day + k - 1 < new_cur_day are expired. So we need to delete those edges.
Thus, we have a dynamic graph with both insertions and deletions (expirations). We need to answer component size queries. This is a classic problem that can be solved with dynamic connectivity (or offline using divide & conquer on time). But constraints: n up to 1e5, q up to 5e5, k up to 1e5. So total number of edge insertions up to 5e5. Deletions also up to 5e5 (since each insertion will be deleted exactly after k days). However, edges have fixed lifetimes: each edge is active from its insertion day (the day when type-1 query occurs) until exactly k days later (inclusive? Actually inclusive: if insertion day = d, then last day it is active = d + k - 1? Because at day d + k, the edge is expired? Let's test with examples. Example 1: k=1. Input: ... They have type-1 queries on day 1: 1 1 2, 1 1 3, 1 3 4. Then type-2 4 gives output 4. That means that at that moment (still day 1), the component containing 4 includes 1,2,3,4? Edges: (1-2),(1-3),(3-4) all active (since day 1 is within last 1 day). So yes. Then type-2 5 gives output 1 (only itself). Then "3" moves to day 2. Then type-2 1 gives output 1. That means after moving to day 2, edges from day 1 expire (since k=1). So component of 1 is just {1}. Then new edges: 1 1 2, 1 3 2 (and maybe also a previous 1 1 2 again? Actually after moving to day 2 they do: 1 1 2, 1 3 2). That yields edges on day 2: (1-2) and (3-2). So component of 1 includes {1,2,3} (since 2 connects 1 and 3). Then type-2 1 outputs 3. Then another "3" to day 3? Actually after that they have "3" and then "2 1" output 1. So at day 3, no edges? Actually after moving to day 3, edges from day 2 expire, so component of 1 = {1}. So matches.
Thus, edge inserted at day d is active for days d, d+1, ..., d+k-1 inclusive. So its lifespan is [d, d+k-1] as integer days. After day d+k-1, when we move to day d+k, it expires.
We need to process operations online? Yes, we read queries sequentially and need to output for type 2 immediately. This suggests we need an online data structure supporting edge insertions, deletions, and connectivity queries (size of component). The classic approach is a dynamic connectivity data structure using a spanning forest with Euler tour trees (ETT) or Link-Cut Trees (LCT) to maintain connectivity and component size under edge insertions and deletions. However, we can also exploit the fact that each edge has a known expiration time (the day after it is inserted). That is, each insertion has a corresponding deletion scheduled at a known future time (when cur_day becomes d+k). However, the deletions are not triggered by a query with an explicit edge identifier; they are triggered by day advancement. So we can schedule deletions. Since we process queries sequentially, we know exactly when each edge will expire: at the moment when we process the "3" query that increments cur_day to a value that makes it expire. But we may also have multiple "3" queries; edges expire in batches when day passes. This is similar to sliding window of edges over time: edges become active at insertion time and become inactive exactly k days later.
Given that k can be up to 1e5, but q is up to 5e5, we can handle expiration using a queue of edges per day? Because the total number of days encountered equals number of "3" queries + 1? Actually we start at day 1, and each "3" increments. But there could be up to 5e5 "3" queries, so days can go up to ~5e5+1. So we can maintain an array of lists for edges expiring on each day.
We could think of using an offline method: treat each edge as an interval [start_day, end_day] where end_day = start_day + k - 1 (inclusive). We have queries (type 2) at specific times (a particular day, within that day). We need to answer connectivity queries on a graph that is the union of edges active at that moment. This is a classic "dynamic graph connectivity with offline queries and edge intervals" problem that can be solved using a segment tree over time (divide and conquer) with a DSU that supports rollbacks. Known as "offline dynamic connectivity" or "divide and conquer on time". We process all events (edge additions and deletions) on a timeline, and answer queries at specific times. This works even when edge intervals are known. However, here the deletions are not given as events but can be derived from insertions and k. Additionally, the queries of type 3 simply advance the day; they don't directly produce output. But they affect the expiration of edges. So we can model the timeline as a sequence of "operations" (including type-1, type-2, type-3). We need to know at each step what the current day is. That's easy to simulate; we just maintain cur_day variable while reading input. But for offline approach, we need to map each operation to a timestamp (like an integer index of the operation, not necessarily the day). However, the active edges at a given operation depend on the day number, not on the operation index. Since days are incremented by type-3, and day number matters for expiration. So if we treat each operation (including type-3) as a point in time, we can assign a global time index (1..q) and also a day number. But expiration of an edge occurs not at a specific operation but when the day passes a threshold. Actually edge expiration happens exactly at the moment when we process a type-3 operation that moves cur_day beyond the edge's expiration day. So we can treat that type-3 as the deletion event for all edges whose expiration day = new_cur_day - 1? Let's derive precisely.
Let cur_day start at 1. For each type-1 at operation index i, we note its insertion day d = cur_day (the day before any type-3 that may occur later). This edge should be active for all operations that occur while cur_day is between d and d+k-1 inclusive. When we process a type-3, we increment cur_day. After increment, the new cur_day is d' = cur_day+1? Actually let's simulate with operations:
We have a sequence of q operations. Maintain cur_day integer, initially 1. For each operation in order:
-
If op is type 1 (x,y): record edge with insertion_day = cur_day. The edge will expire after cur_day + k - 1 days? Actually it will become inactive when cur_day becomes cur_day + k. So the last day it's active is cur_day + k - 1. So the edge should be considered active for all operations whose associated cur_day is in [insertion_day, insertion_day + k - 1]. But note that during the same day, multiple operations occur. After an edge insertion, subsequent queries (including type-2) in the same day still see it. So for operations on the same day, they have the same cur_day.
-
If op is type 2: query. We need the connectivity at that moment (with cur_day as current day). So we need to consider all edges with insertion_day >= cur_day - k + 1 and insertion_day <= cur_day. (i.e., active at that cur_day).
-
If op is type 3: increment cur_day by 1. The operation itself doesn't produce output but changes state for subsequent operations.
So the active set changes only at type-3 operations (when cur_day increments) and at type-1 (when edges are added). So deletions happen at type-3 when cur_day crosses expiration thresholds.
Thus, we can treat the whole process as a timeline of events (edges added at certain times, edges removed at certain times). The removal time is the operation index of the type-3 that causes the expiration? But careful: edges expire at the moment the day changes, i.e., after processing type-3. Actually when we process a type-3, we first increment cur_day, and then subsequent operations (including any further type-1/2) will use the new cur_day. So the removal should be applied before processing any operations after the day change. In other words, the deletion of edges that expired should happen at the moment of the type-3 operation, after incrementing cur_day but before handling the next operation? But the type-3 operation itself doesn't need the graph; it's just a day change. So we can process the type-3 by: first increment cur_day, then delete all edges whose expiration_day = cur_day - 1? Actually if an edge inserted at day d expires when cur_day becomes d+k, i.e., when cur_day > d+k-1. So after incrementing cur_day to new_day, edges with d + k - 1 < new_day are expired. That is, d <= new_day - k -? Let's solve: active if cur_day - d < k? Actually cur_day - d <= k-1? So active if cur_day - d <= k-1, i.e., cur_day <= d + k - 1. So expiration condition: cur_day > d + k - 1. So after increment, if new_cur_day > d + k - 1, then edge expired. So the first cur_day at which it's not active is when cur_day = d + k. So the edge should be removed at the moment cur_day becomes d + k. This removal occurs when we process a type-3 that makes cur_day become d + k. But note that there could be multiple type-3's between insertion and expiration; we need to schedule removal exactly at that transition.
Therefore, we can model each edge as an interval of operation indices: from the operation index of its insertion (call it t_add) up to but not including the operation index of the type-3 that triggers expiration? But that's messy because the expiration is triggered by a type-3 which occurs at some operation index. However, we can precompute for each edge, its expiration day, and then find the operation index of the type-3 that increments cur_day to that expiration day. Since the process is online, but we can pre-scan the input to determine the day number at each operation index. That is, we can simulate the days first (without processing graph) to compute cur_day for each operation index. Then we can record for each edge the operation index of its addition and the operation index when it should be removed (the first operation index where cur_day becomes > d + k - 1). Since type-3 operations themselves don't need graph connectivity (they just change day), we can treat the removal happening before that operation? Let's define:
We have a sequence of q operations. For each operation i (1-indexed), we can compute the cur_day before executing operation i. But careful: For a type-1 operation at index i, the insertion occurs with cur_day = day_i (the day before executing operation i? Actually at the start of operation i, we have a current day number. When we process type-1, we add the edge and that edge is immediately active for the rest of the day. So its active interval should start at operation i (immediately after addition) and remain active until the end of day d+k-1. So if we consider operation indices as points in time, the edge is active for all operations j such that the current day at operation j (the day when operation j is executed) is within [d, d+k-1]. That includes operations after i on the same day, and operations on later days up to and including operations that occur on day d+k-1. When day becomes d+k, the edge is no longer active for operations after that point.
So we can define for each operation i, its associated day number day[i] (the current day when that operation is executed). This can be computed by scanning the operations: start with day=1, for each op, set day[i]=current_day; if op is type-3, then after processing, increment day for subsequent operations. But careful: For type-3, the operation itself has a day number (the day before increment). Since the increment occurs after processing the operation? The problem statement: "Query of third type The end of the current day moves on to the next day." This implies that when we encounter a type-3 query, it signifies the end of the current day; after processing it, we move to the next day. So the type-3 query itself is processed on the current day (the day that ends), and it doesn't perform any other action. So it should be considered as happening on that day, and after it, the day increments. So for our modeling, for type-3 operation i, day[i] = the day that ends (say d). Then after this operation, subsequent operations have day = d+1.
Thus, we can compute day[i] for each i by scanning the input and counting type-3's before i.
Now, an edge added at operation i (type-1) with day d = day[i] is active for all operations j where day[j] is in [d, d+k-1]. So its active interval in terms of operation indices is from i (inclusive) up to the last operation that occurs on day d+k-1 (inclusive). But there could be multiple operations on the same day. The expiration occurs at the point when the day becomes d+k, i.e., before the first operation with day = d+k. So the edge should be considered inactive for any operation j where day[j] = d+k. So we can say the edge is active for operations with index >= i and day <= d+k-1. The removal time (when it becomes inactive) is before the first operation that has day = d+k. That could be at a particular operation index (the first operation of day d+k) or after the last operation of day d+k-1.
Thus, we can treat the timeline of operations as discrete points; we want to support insert edge at time i, delete edge at time j (where j is the first operation index where day = d+k). We can compute j as: the smallest operation index such that day[j] = d+k. If there is no operation with that day (i.e., the simulation ends before day d+k), then the edge never expires (or expires after all queries). We'll need to handle that as well.
Alternatively, we can use the offline segment tree approach where we add each edge to segment tree intervals covering the range of operation indices where it is active. Then we process queries (type-2) by answering at the moment of that operation index. That is classic: we have a set of intervals (time intervals) for each edge, and point queries. We can recursively traverse a segment tree over the range [1, q] and maintain a DSU with rollback. This yields O((E+Q) log Q * α(n)) time, which is feasible for q up to 5e5.
But careful: The edges are undirected and we need component size queries (count nodes in the component). DSU with rollback can maintain component sizes if we support union and can revert. This is standard: when we union, we push changes onto a stack (parent changes, size changes, etc.) and rollback to a previous state when exiting recursion.
Thus, offline method seems plausible. Let's outline:
- Parse input, store operations.
- First, compute day[i] for each operation i (1-indexed). Also count number of days? We'll need to know for each edge added at i, its expiration day = day[i] + k. Actually active while day <= day[i] + k - 1, so expiration_day = day[i] + k. We need the operation index range where it is active: from i to (the last operation index with day <= day[i] + k - 1). Let L = i, R = last operation index such that day[index] <= day[i] + k - 1. Since operations are sequential, we can precompute an array "last_op_of_day" or compute for each day the max operation index. But days can go up to potentially many (up to q+1). However we can compute for each operation its day, then we need to find, for a given day d, the last operation with that day. Then for an insertion with day d_i, we need the last operation with day <= d_i + k - 1. That is essentially the index of the last operation whose day is <= some threshold.
We can precompute an array "max_index_for_day" if we know all possible day numbers. But days are sequential from 1 to some maximum day D (which could be up to number of type-3 + 1, up to q). Since q up to 5e5, D up to 5e5+1. So we can create a vector or map day -> max operation index (the last operation of that day). While scanning operations, we can record for each day, the first operation index and last operation index (or at least the last). Because days are contiguous, we can create an array first_op[d] and last_op[d] after scanning.
Procedure: Initialize day=1. For i from 1 to q:
- day[i] = day.
- If op[i] type is 3, after processing this op, day++.
- Also, for each day d, we can track that the operations with that day cover a contiguous range of indices? Since day increments only at type-3, but there can be multiple operations on the same day. The operations of a given day are a contiguous block because once we encounter a type-3, day increments and subsequent operations are on next day. So indeed, the operations for each day form contiguous intervals. So we can compute for each day d: start_index[d] = first operation index with that day, end_index[d] = last operation index with that day. This can be recorded during the scan: when we first encounter a new day, set start, and as we process operations with that day, update end.
We can compute these arrays size D+something.
Now for a type-1 insertion at operation i (with day d_i), we need the active interval: it should be active from i to end_index[d_i + k - 1] if d_i + k - 1 <= D (max day). If d_i + k - 1 > D, then it's active until the end of all operations (i.e., q). So we can compute R = (d_i + k - 1 <= D) ? end_index[d_i + k - 1] : q.
But careful: At operation i, the edge is added. For queries occurring at the same operation i (but after insertion? Actually the operation order is: at operation i, we do type-1. The edge is added immediately; any query later on the same day (with higher index) will see it. But what about a query at the same index? There is no query at same index because each operation is either type-1,2,3. So no conflict. So the edge is active starting at time i (after insertion). So the active interval is [i, R] inclusive, where R is the last operation index of the last day it is active.
But we must consider that after the last operation of day d_i+k-1, the next operation (if any) will have day d_i+k. The edge should be inactive at that next operation. So our interval ends exactly at the last operation of day d_i+k-1. So that is correct.
Edge case: If k=0? But k>=1.
Now for queries of type 2 at operation i: they ask for the component size of node x at that moment. We will answer by processing the segment tree recursion: At leaf node corresponding to operation index i, we will have a DSU state representing all edges that are active at that moment. So we need to assign each edge to the segment tree intervals covering its active range. Then we recursively traverse the segment tree, adding edges when entering a node, and rolling back when leaving. At each leaf that is a type-2 operation, we query DSU to get size of component of given node, and record answer.
We also need to handle type-3 operations: they don't produce output, but they are just points on the timeline; they affect the active intervals of edges (via day changes). In the segment tree approach, type-3 operations are just leaves that do nothing (no query). We still need to propagate edges correctly across intervals.
Thus, offline approach is feasible.
Complexities: O((M + Q) log Q * α(N)) where M is number of edge additions, up to 5e5. That's about 5e5 * log 5e5 ~ 5e5 * 19 = 9.5e6 operations, each union/find with rollback is near O(α) but with stack overhead; should be okay. But DSU with rollback typically uses O(log n) union? Actually union by size/rank with rollback: we need to store changes to parent and size; union is O(1) ammortized but with rollback we store the changes. It's okay.
Memory: We'll store edges (x,y) for each type-1. We'll assign each edge to O(log Q) segment tree nodes. So total number of insertions into segment tree ~ M log Q ~ 5e5 * 19 ≈ 9.5e6, which is okay if we store edges as pairs of ints per node. But 9.5e6 edges stored as two ints each may be large (~76 MB if 4 bytes each, 9.5e6*8=76 MB). Plus overhead of vectors. Might be high but possibly acceptable if optimized. Alternatively, we could use a different method: since k is up to 1e5, maybe we can do a sliding window with dynamic connectivity using link-cut trees or ETT? But offline approach is simpler to implement if we handle memory carefully.
But there might be a catch: The graph can have up to 5e5 edges active at any time? Possibly, since k can be large, many edges could be active concurrently. The offline DSU with rollback can handle many unions, but we need to handle rollbacks efficiently. However, the segment tree recursion depth is log Q and we push changes onto a stack. Each union operation may be applied multiple times (once per segment tree node that covers the interval). In worst-case, if an edge is active for a long interval (say whole timeline), it will be added to O(log Q) nodes but each addition corresponds to a union operation when traversing those nodes. But in the recursive traversal, we will union edges in each node as we go down; each union operation is performed at most once per node where the edge is stored. So total union operations across the whole traversal is the total number of edge-node assignments, which is O(M log Q). That's similar to 9.5e6 unions. That's fine.
But DSU rollback union operations require pushing state onto a stack. For each union, we push a record of changed data (like which root changed, size updates). So total stack size could be up to the total number of unions performed along the current recursion path, which is O(M log Q) total across all leaves? Actually the stack depth at any time is bounded by the number of unions applied along the path from root to leaf. Since each edge may be added in multiple nodes along the path, but we only add edges stored in nodes that fully cover the current segment. In segment tree decomposition, each edge is added in O(log Q) nodes, and along a root-to-leaf path, an edge may be added in O(log Q) nodes? Actually the way segment tree for intervals: we add an edge to nodes whose segment is fully covered by the edge's active interval, and that set is a partition of the interval into O(log Q) nodes. When we recursively traverse, we only apply the edges stored in the current node. So along any root-to-leaf path, an edge will be applied at most once? Let's think: The set of nodes covering an interval are disjoint in the sense that they partition the interval; they are not nested. Actually the standard segment tree interval addition: when we want to add an edge for interval [L,R], we call a function that traverses the tree and adds the edge to all nodes whose segment is completely inside [L,R] and that are not recursively explored. So those nodes are not ancestors of each other; they are separate. So when we later traverse from root to leaf, we will visit some nodes; an edge will be applied if the leaf is inside the interval of the node where the edge was stored. But each node we visit along the path may have many edges stored. The edge's interval may be stored in a node that is not necessarily on the path? Actually if the leaf is within the edge's active interval, then that leaf is covered by some of the nodes where the edge was stored. But which nodes? The decomposition of [L,R] into nodes ensures that for any point x in [L,R], there exists exactly one node on the root-to-leaf path for x that contains the edge? Let's recall: In segment tree range-add, we store the edge in all nodes that are fully covered by [L,R]. This set of nodes covers the whole interval, and for any point x, the nodes on the path from root to leaf that have their segment covering x, only one of them might have stored the edge if that node's segment is fully contained in [L,R] and we stopped recursing there. But if a node's segment is partially overlapped, we didn't store the edge there; we recursed deeper. So for a leaf x, the edge will be stored in exactly one node on the path from root to leaf: the node that is the highest (closest to root) such that its segment is fully inside [L,R] and also contains x? Actually the decomposition algorithm: we start at root covering [1,N]. If [L,R] fully covers current node, we add edge to that node and stop. Else, we recurse to children. So for a point x that lies within [L,R], when we descend from root, we will eventually reach a node where the node's segment is fully inside [L,R] (maybe at some depth). At that node, we add the edge and stop recursion for that branch. So for that leaf x, only that node will contain the edge. Because if we go deeper, we would have recursed further only if the node was not fully covered. Since we stopped at that node, we don't add the edge to any deeper nodes. So indeed, each edge is stored in a set of nodes that partition the interval; and for any leaf in the interval, the edge appears in exactly one node on the path to that leaf (the node where the recursion stopped). Therefore, along a root-to-leaf path, each edge is applied at most once (if the leaf is within its interval). So the total number of union operations along a path is at most the number of edges active at that time? Actually each active edge will be applied exactly once at the node where it is stored. So the total number of union operations performed during the entire DFS is sum over nodes of (number of edges stored in that node) * (the number of leaves in that node's segment?) No, careful: In the offline approach, we do a DFS over the segment tree. At each node, we apply all edges stored there (by union in DSU) and then recursively visit children. After children, we rollback those unions. So the number of union operations performed overall is total number of edge assignments to nodes. Because each edge is unioned once per node it's stored in, but then rolled back. That is O(M log Q). However, the stack depth of DSU modifications (the number of changes to roll back after each child) can be as high as O(M log Q) in worst-case if many edges are stored in a node covering a huge segment, but we push them onto a stack and roll them back after recursion; the maximum stack size at any point is the total number of unions applied along the path from root to current node. Since each edge is stored at most once per node, and each node's edges are all applied before descending, the maximum number of applied unions on a path is the sum of edges stored in all nodes on that path. In worst-case, if we store many edges in the root, that could be large (M). But then the path includes root (which may have many edges) and then other nodes. So total could be M in worst-case. However, that's okay because the DSU rollback stack will have at most M entries, and that's fine memory wise (M up to 5e5). But note that if root has M edges, then we apply all of them at once, then we push them onto the stack. That's okay: we have stack of size up to M. Then as we go down, we might add more edges (but edges stored in children are subsets of edges not stored in ancestors? Actually edges stored at different nodes are disjoint in terms of intervals: an edge stored in a node is not stored in any of its descendants or ancestors because of the decomposition property. So if an edge is stored at root, it means its interval covers the whole [1,N]. Then it will not be stored anywhere else. So the root's edges are those that are active for the whole timeline. So the maximum number of unions on a path is the sum of edges stored in nodes on that path, which could be up to M if there is an edge stored at each node? But due to disjointness, each edge belongs to exactly one node on any root-to-leaf path. So the total number of unions on a path is exactly the number of edges that are active at the leaf (since each active edge appears exactly once on that path). So the stack size at leaf is the number of active edges at that time, which can be up to M (in worst-case if all edges are active at the same time). That's okay; DSU with rollback stores modifications, not the whole set of active edges. However, when we union, we may modify two nodes (parents and sizes). So the number of modifications on the stack can be up to 2 * (number of unions along the path). But worst-case number of active edges is up to M = 5e5, so stack size up to 1e6, which is okay.
Thus offline DSU with rollback segment tree approach works.
But we need to be careful: The number of operations q up to 5e5, so segment tree size about 4*q = 2e6, which is okay. We'll store vector edges for each node? Actually we can store edge IDs or pairs. We'll create a segment tree over indices 1..q. For each edge addition at time i with active interval [i, R] (inclusive), we add it to the segment tree covering that range. For a query at time i (type-2), we answer at leaf i. For type-3 leaves, we do nothing. The DSU must support finding component size for a node.
Implementation Steps:
- Read n, q, k.
- Read all operations into arrays: type[i], maybe x[i], y[i] for type1, i[i] for type2.
- First pass: Compute day[i] for each operation i, and also compute for each day d: first_op_index[d] and last_op_index[d]. Since we don't know max day ahead, we can record the day for each op, and also keep a vector or array to store first and last indices per day. Since q up to 5e5, day numbers can go up to q+1. So we can allocate arrays of size q+2 for first and last, initialized to 0.
- Initialize cur_day = 1.
- For i from 1 to q: day[i] = cur_day. if type[i] == 3: after processing, cur_day++.
- Also, as we go, we can set first_op[cur_day] when we first encounter that day. Actually we need to know start of each day. Since day[i] is known after we assign, we can later fill start and end by scanning the day array. After this loop, we have max_day = cur_day (the day after the last operation? Actually after loop, cur_day is the day that would be used for the next operation, but since there is none, it's fine. The maximum day that appears in operations is cur_day-1 (since the last operation had that day). Because after last op, if it was a type-3, cur_day incremented but that day never used. So the days that appear in operations are from 1 to cur_day-1. So we can compute first and last indices for each day d by iterating over i=1..q and updating: if first[d] == 0: first[d] = i; last[d] = i; This will work because we have day[i] for each i.
- Compute for each type-1 operation at index i: its active range. Let d = day[i]. Let last_active_day = min(d + k - 1, max_day_used) where max_day_used = cur_day-1 (the maximum day that appears). Actually we need the last operation index where day <= d + k - 1. So we compute: end_day = d + k - 1. if end_day > max_day: then the edge never expires (active until end of operations). Then R = q. else R = last_op_index[end_day] (the last operation of that day). L = i (since it's active starting at its own addition time). But careful: At the moment of insertion (operation i), the edge is added and should be considered for queries at i? But i is a type-1 operation, not a query. There is no query at that point. However, if there is a type-2 later on the same day, it should see the edge. So the active interval includes times after i. But does it include i itself? In terms of segment tree, we want to cover all operation indices where the edge is present. Since we only query at type-2 indices, and we never query at a type-1 index, it's safe to include i or not? But we need to ensure that if there is a type-2 at the same index? Not possible. But we have to be careful: If there is a type-2 earlier on the same day, it shouldn't see the edge added later. So the active interval should start after the addition. So we set L = i (the addition time). But note: In segment tree, the point representing operation i (type-1) is not a query. So if we cover i, it's fine; but the edge is not needed for that point. However, we need to ensure that for any point j > i, if j is within active days, edge is active. So we can set L = i+1? Actually if there is a type-2 at index i+1 on the same day, the edge should be active. So the interval should be (i, R]? But if we set L = i, then leaf i (type-1) would also consider the edge, but that's not used. But is it a problem? In segment tree, we add edges to nodes covering [L,R] inclusive. At leaf i (type-1), the DSU during DFS would have that edge applied. That would be incorrect because at the time of that leaf (the moment of insertion), the edge might not have been added yet? Actually the chronological order: We process operations sequentially. At operation i (type-1), we add the edge. For answering queries at later times, the edge should be present. In the offline segment tree approach, we treat each operation as a point in time, and we need the DSU state at that point to reflect all edges that are active at that moment (i.e., after processing previous operations). Typically, we model that at time t (after processing operation t), we consider the state. But we want to answer queries at the moment they occur, which is after processing all previous operations including any type-1's that happened earlier in the same day. So the DSU state at time t should include all edges added at indices < t that are still active. So for a type-2 at index i, we need to include all type-1 edges with index < i and still active. But our active interval for a type-1 edge added at index j should be (j, ...] (i.e., start after j). Usually, in segment tree offline connectivity, we assign each edge to the interval of time indices where it is active, starting from the moment after its addition until its removal. So L = j+1. But we need to be precise: If we treat each operation as an event at a discrete point, and we want to query at point i (the moment after processing operation i? or before?). Let's define:
We have operations 1..q. We consider time moments between operations. Typically, we can consider that at time t (an integer between 0 and q), the state is after processing first t operations. Then a query at operation i (type-2) should be answered using state after processing operations 1..i-1? Actually the query occurs at operation i; at that moment, we have already processed previous operations i-1. So the state reflects all additions from previous operations. Also, if there are type-1 edges earlier on the same day, they should be included. So we need the DSU state just before executing operation i? But the type-2 query asks "current number of people in contact with a given person" at that moment, i.e., after all previous operations have been applied, but before any later ones. So it's the state after processing all operations with index < i. However, note that if there is a type-1 operation at the same index i, it's impossible because each operation is either type-1,2,3. So no conflict. So for a query at index i, we need to apply all edge additions from indices j < i that are still active (i.e., added at j and not yet expired by time i). Also, we need to consider expiration: an edge expires at the moment when the day changes to d+k, i.e., before operations on day d+k. Since we define state before processing operation i, we need to consider whether the edge is still active at the moment just before operation i. That depends on day[i] (the day of operation i). The edge added at index j with day day[j] is active for any operation i such that i > j and day[i] is within [day[j], day[j]+k-1]. Also, if day[i] == day[j]+k, then it's not active. So our interval for edge j is from j+1 (since after addition) up to the last operation index with day <= day[j]+k-1. But careful: What about operations that occur on the same day as the addition but after it? Those have day[i] = day[j] and i > j, so they are included. So that's fine.
Thus, for each edge addition at index j, we define its active interval as (j, R] where R is the last operation index with day <= day[j]+k-1. However, we also need to consider that if the edge addition occurs on a day, and then later on the same day there is a "3" that ends the day? Actually "3" is an operation that ends the day; it has the same day number as the previous operations. After processing that "3", the day increments. So for an operation after the "3" (i.e., next operation), day is incremented. So the edge's active interval should include up to operations before the day increments, i.e., include the "3" operation? But the "3" operation is just a marker; no query occurs at that point. However, the edge might still be active during the "3" operation? But "3" doesn't ask about connectivity; it just moves to the next day. So it doesn't matter. For queries after the "3", day is incremented, so if the new day equals day[j]+k, then the edge is expired. So the edge should not be active for operations after the "3". So R should be the last operation index of day day[j]+k-1. That could be a "3" operation, but we don't query at that point, so fine. So using (j, last_index_of_day(day[j]+k-1)] works.
But we must handle the case where day[j]+k-1 >= max_day_used; then R = q (since after last operation, it's still active). However, what about edges added after the last query? They might not need to be considered for queries, but they could still affect later queries if there are any. Since we have queries up to q, it's fine.
Now, we have defined intervals for each edge: from L = j+1 to R inclusive (if L <= R). But note that if R < j+1, then the edge is never active (e.g., if k=0, but k>=1). But could be that the edge expires immediately if k=1 and there are no operations after j on that day? Let's test: if k=1, edge is active only on day day[j]. So it should be active for any operation after j on the same day. If there are no operations after j on that day, then the edge is never used. So interval L = j+1 to R = last operation of day day[j] (since day[j]+k-1 = day[j]). R could be j if last operation of that day is j itself? But j is a type-1 operation; after it, there may be other operations. The last operation of that day could be j if j is the last operation of that day. In that case, L = j+1 > R, so interval empty. That means the edge is never active for any query because there are no further operations on that day. That matches: if we add an edge and then the day ends (maybe after a "3" later? But if there is a "3" later, then there are operations after j? Actually if j is the last operation of the day, then after j there might be a "3"? No, a "3" is an operation; it would have its own index > j. So if j is the last operation of the day, it could be that the last operation is a "3"? Let's see: The day's operations are contiguous. The day ends with a "3" operation? Actually not necessarily; the day ends when a "3" query occurs. The problem says "Query of third type The end of the current day moves on to the next day." So the day ends exactly at a type-3 operation. So the last operation of a day is always a type-3 (unless it's the final day and no type-3 at the end, but then the day doesn't officially end? The problem statement implies that days are separated by type-3 queries. So the simulation starts at day 1, and day only changes when we encounter a type-3. So the last operation of a day (if any) is a type-3. Therefore, after a type-1 on day d, there could be later operations on day d (including other type-1, type-2, and finally a type-3). So there will always be at least one operation after the type-1 if there is a type-3 later that day? Actually not necessarily: It's possible that a type-1 is the last operation before a type-3? The type-3 is also an operation. So if we have a type-1 and then immediately a type-3, the type-1 is not the last operation; the type-3 is the last operation. So the last operation of the day is a type-3. So for any type-1, there is at least a type-3 later on that day? Possibly not if the day ends without a type-3? But the day ends only when we encounter type-3. If we never encounter type-3 after some type-1, then the day never ends; all subsequent operations are still on the same day until a type-3 appears. So there will be some operations after the type-1 (unless it's the very last operation of the whole input and there is no type-3). In that case, the day doesn't end, but there may be no queries after that edge; so interval empty if no later operations. That's fine.
Thus we set L = j+1 and R = last_op_index[min(day[j]+k-1, max_day)] if day[j]+k-1 <= max_day else q. But need to be careful: if the edge is inserted at index j and there is a query at index j+1 that is still on the same day, it should see the edge. So L=j+1 is correct.
But wait: Could there be a type-2 query that occurs before any type-1 on the same day? That's fine.
Now, we need to also consider that the edge might be active for queries that occur at the same index as the edge? Not possible. So fine.
Now, what about type-3 operations? They don't affect connectivity directly. They only mark day boundaries.
Thus, we have all intervals.
Now, we can apply standard offline connectivity with segment tree.
Implementation details:
-
We'll build a segment tree over indices 1..q. But our intervals are from L to R inclusive. We'll add each edge to the segment tree covering [L, R].
-
Then we perform a DFS over the segment tree, maintaining DSU with rollback. At each node, we apply all edges stored there (union the endpoints). Then if the node's interval is a single point (leaf), we process that operation: if it's type-2, we query the DSU to get the size of the component containing the given person, and record answer. Else (type-1 or type-3), do nothing.
-
After processing children (or leaf), we rollback the unions performed at this node (by popping from stack the number of changes made since entering the node).
The DSU needs to support:
-
find(u): with path compression? But path compression is not easily rollbackable. So we use union by size/rank without path compression; we store parent array and size array. find uses while loops to follow parent (without compression) so O(log n) worst-case (since union by size ensures depth O(log n)). That's acceptable given total operations ~ 10^7.
-
union(u, v): find roots ru, rv. If ru == rv, do nothing and push a marker indicating no change. Else, attach smaller to larger; push changes onto stack: we need to record that we changed parent[small] and size[large]. Usually we push a tuple (changed node, previous parent, previous size of large root). Or we can push both modifications: (small, old_parent), (large, old_size). Since we need to revert both.
-
For rollback: pop changes from stack and restore.
-
Also we need to quickly get component size for a node: after find root, return size[root]. Since DSU is not compressed, find may take O(log n). That's okay.
Now, need to be careful about indices: n up to 100k, so DSU arrays of size n+1.
Segment tree representation:
We can use a vector<vector> tree where tree[node] stores edges (as pairs) assigned to that node. Build a segment tree with size = 1 << (ceil(log2(q)))? Or we can use iterative segment tree? Easier: recursion.
Define a function add_edge(node, l, r, ql, qr, edge_id). Standard.
We need to process all operations. We'll store queries: for each index i, if type=2, we store the person x, and also an answer index to output later (since we need to output in order). Since we are doing offline, we can store the queries order and then print answers in the order of input.
Plan:
-
Read all operations. We'll store arrays:
- op_type[i] (1..q)
- if op_type[i]==1: x1[i], y1[i]
- if op_type[i]==2: person[i]
-
Compute day[i] for each i as described. Also compute max_day = the maximum day encountered (the day of last operation). Actually we need an array last_op_per_day.
Implementation:
Initialize cur_day = 1. vector day(q+1); // 1-indexed int max_day = 1; for i in 1..q: day[i] = cur_day; if op_type[i]==3: cur_day++; // after processing? Actually we set day[i] before processing op? According to earlier, day[i] is the day on which the operation occurs. For type-3, the operation occurs on the current day (the day that ends). So it should be day[i] = cur_day before increment. Then after processing, cur_day++. So we set day[i] = cur_day; then if op_type[i]==3: cur_day++. After loop, the final cur_day may be max_day+1. The days that appear are 1..cur_day-1. So max_day_used = cur_day-1.
Now compute first_op and last_op arrays of size max_day_used+2. Since we know max_day_used, we can allocate vector first(max_day_used+2, INF?), last(max_day_used+2, 0). Then iterate i=1..q: d = day[i]; if (first[d] == 0) first[d] = i; last[d] = i;
Now process
-