$i$-th of the $N\,(N\le 2\times 10^5)$ containers will arrive at the port at time $A_i$ and depart from the port at time $B_i$ (all $A_i$ and $B_i$ are distinct and $1 \le A_i, B_i \le 2N$). There are two spots to store containers. In each spot, you can put any number of containers vertically. When a container arrives, you have to store it in one of these spots. If there are some containers already on the spot, you have to put the new container on top of the old ones. When you want to take away a container, you have to take one from the top of one of the spots. You have to find out the number of ways you can choose spots for each of the containers.
First of all, if there are two different containers $i$ and $j$ such that $A_i < A_j < B_i < B_j$, they can't be put in the same spot. So we can add an edge between them (graph is on nodes from $1$ to $N$), which tells us that they must be assigned to different spots. After adding the edges properly, let's assume that the graph is bipartite and connected (if it's not bipartite, then there is no way to choose spots for them). Then if we choose the spot for one container, then others' will be determined automatically. Since there are two ways to choose the spot for first one, the answer is 2.
But can we always assign the boxes if the graph is bipartite? Yes. Because the bipartite graph can be divided into two independent sets of vertices, and there's no edge between two vertices from the same independent set. Which means that every pair is either completely disjoint or contained in one another. You can now see this as some sort of balanced bracket sequence — if you put opening bracket at the As and closing at the Bs.
What happenes when the graph is not connected and has multiple components (again, all of which are bipartite)? The answer will then be $2^{\texttt{#components}}$. All that remains is that we need to check if the graph is bipartite or not and if it's bipartite, find the number of connected components. To do that, we will use segment tree to build a slightly different kind of graph. This graph has two kinds of edges -- some edges will have 0 as weight meaning that the nodes at the two endpoints must have same color (same spot. From now on, if I say, ``$i$-th node's color is white'', that means that the $i$-th container is assigned to spot 1, and black, if I want to assign it to spot 2) and some edges will have 1, meaning that they must have different colors.
Make a new array $M$ and for each $i$, set $M_{B_i} := i$. Now make a merge sort tree (if you don't know it, it's essentially a segment tree where each node has a list, and elements in that list are sorted in some particular order) on this array (unassigned indices are ignored) where every node $u$, that covers $[l,r]$ has a list $L_u$ of indices $i$ such that $i \in M[l,r]$. And the indices $i$, in some list $L_u$, are sorted in increasing order of $A_i$. You can build this tree in $O(N \log N)$ time.
Now for each $i$, pick the $O(\log N)$ relevant nodes in the segment tree for the range $[A_i, B_i]$, let's denote the set of these nodes with $S$. For each $u \in S$, add an edge with weight 1 between $i$ and $L_{u,0}$, and find the maximum $k$ (binary search) such that $A_{L_{u,k}} < A_i$ and note down somewhere that we should add an edge with weight 0 between $L_{u,0}$ and $L_{u,i}$ for all $i \le k$. If we do this $N$ times, time complexity of this part will be $N \log^2 N$. But instead of doing binary search, we will just maintain a pointer for the maximum $k$ we have encountered so far for a particular node (because, note that each time it's just a prefix). After the updates, we will add all the 0-edges in one go. A pointer for some node $u$, which covers range $[l,r]$ will move at most $r-l+1$ times, and as the sum of all $r-l+1$ is $O(N \log N)$, this part of our solution will use $O(N \log N)$ time (also will add $O(N \log N)$ edges overall).
Now that we have our graph with 0/1 edges, we need to determine if we can color them properly or not and find number of connected components (notice that connectivity of this graph and the first graph is same). Obviously you can run bfs/dfs at this point, but if you implement the graph using $N$ vectors, you are done for. \texttt{std::vector}s are unimaginably slow. It screwed me over several times. There is one technique to implement graphs without vectors as adjacency lists. I'll just put the code here, it's pretty self explanatory:
struct edge { int to, next; } e[N]; int head[N], tot; void addedge(int from, int to) { e[++tot] = {to, head[from]}; head[from] = tot; e[++tot] = {from, head[to]}; head[to] = tot; } ... for(int i = head[u]; i; i = e[i].next) { int v = e[i].to; // v is a node in the adjacency list of u }
This may or may not pass, I didn't check. There is another way of checking whether a graph is bipartite or not -- using disjoint set union. Extra benefit of this method is that the checking is online (although we don't need it to be online for this problem, it's just a cool trick), meaning you can keep adding edges, and you can check if the graph is bipartite or not after every addition.
It's almost the same as the normal dsu, but in addition to that, you keep track of another value $d[u]$ for each node, which denotes the value of the edge between $u$ and $par[u]$ in the dsu tree (the tree which you can create from the $par[\ldots]$ array), and if you take the xor of all edges from $u$ to the representative of $u$'s connected component, you'll get $u$'s actual color. When uniting two nodes $u$ and $v$, by an edge of weight $w$ (let's denote $u$ and $v$'s representative with $r_u$ and $r_v$ respectively, and denote the xor sum of path from $u$ to its rep and $v$ to its rep with $c_u$ and $c_v$ resp.), we set $par[r_u] = r_v$ and $d[r_u] = c_v \oplus c_v \oplus w$. And if $u$ and $v$ are already in the same connected component, we need to check the xor values of path from $u$ to its representative and $v$ to its representative are same (if $w$ is 0) or not (otherwise). Also we need to adjust the $\texttt{find}$ function accordingly for path compression. I'll put the code for reference (I haven't done the merge small to large heuristic, thus it's $N \log N$. But if you do both -- the path compression and the size based heuristic, then you'll get $\alpha(N)N$ time. Also, Note that, you must do path compression, otherwise the overall time complexity will be $N \log^2 N$.)
int find(int u) { if(par[u] == u) return u; int p = find(par[u]); d[u] ^= d[par[u]]; return par[u] = p; } bool unite(int u, int v, int w) { int ru = find(u), rv = find(v); if(ru == rv) { return (d[u] ^ d[v]) == w; } else { d[ru] = w ^ d[u] ^ d[v]; par[ru] = rv; return true; } }
*sorry for the grammar and spelling mistakes