[SHOI2008]堵塞的交通

给定一张 \(2\times C\) 的网格图，三种操作：

  1. 将网格上相邻的两点 \(u,v\) 连通。

  2. 将网格上相邻的两点 \(u,v\) 断开。

  3. 询问也许不相邻的两点 \(u,v\) 的连通性。

不强制在线。

蛤蛤，不强制在线的动态图连通性，上线段树分治！

我们在时间 \([1,m]\) 上建立线段树，每个节点维护一个 vector 来存若干条边，表示在该节点对应的时间区间中，这些边是存在的。

将操作离线，记录每条边出现的时间区间 \([l,r]_i\)，注意到最终也没有被断开的边其 \(r_i = m\)，将其插入到建立在时间上的线段树上，于是一条边存在的时间区间就对应了线段树上 \(\log\) 个节点。

考虑一个在时刻 \(t\) 上的询问，我们就可以在这颗线段树上递归到对应着时刻 \(t\) 的叶子节点，在向下递归的过程中用并查集将所有在线段树上经过的节点中存的边合并，最后询问一下连通性即可。

所以我们可以将线段树 \(\text{DFS}\) 一遍，统一处理所有的询问，每递归到一个叶子时，若叶子所对应的时刻是一个询问，那么就直接回答。注意到 \(\text{DFS}\) 时还会有回溯的操作，这时需要用到可撤销并查集，每回溯一次就将原来在并查集中的边撤销掉。

这个可撤销并查集就需要按秩合并，同时使用一个栈来维护加入的边，撤销时就从栈顶开始一个一个取出重置，时间复杂度也是 \(\log\) 级别的。

总时间复杂度 \(O(n\log^2n)\)。

Code:

# include 
# include 
# include 
# include 
# include 
# include 

# define pii pair< int , int >
# define pb push_back
# define mIt map< int , int > :: iterator

namespace IO{
	inline int read(){
		int res = 0 , ti = 1;
		char u = getchar();
		while( ! isdigit( u ) ){ if( u == '-' ) ti = -1; u = getchar(); }
		while( isdigit( u ) ) res = res * 10 + u - '0' , u = getchar();
		return res * ti;
	}
}

using namespace std;

const int N = 2e5 + 225;

int n , m;
map< int , int >s[ N ];

struct Operation{ int u , v, op; }o[ N ];

vector< pii >t[ N << 2 ];
# define ls( u ) u << 1
# define rs( u ) u << 1 | 1

int fa[ N ] , dep[ N ] , tp;
pii del[ N ];
int find( int u ){ return fa[ u ] == u ? u : find( fa[ u ] ); }
void merge( int u , int v ){
	u = find( u ) , v = find( v );
	if( u == v ) return;
	if( dep[ u ] < dep[ v ] ) swap( u , v );
	fa[ v ] = u;
	del[ ++ tp ] = make_pair( v , dep[ v ] ) , del[ ++ tp ] = make_pair( u , dep[ u ] );
	dep[ u ] = max( dep[ u ] , dep[ v ] + 1 );
}
 
void insert( int u , int l , int r , int L , int R , pii x ){
	if( L <= l && r <= R ){ t[ u ] . pb( x ); return; }
	int mid = l + r >> 1;
	if( L <= mid ) insert( ls( u ) , l , mid , L , R , x );
	if( R > mid ) insert( rs( u ) , mid + 1 , r , L , R , x );
}

void dfs( int u , int l , int r ){
	int cur = tp;
	for( int i = 0 ; i < t[ u ] . size() ; i ++ ) 
		merge( t[ u ][ i ] . first , t[ u ][ i ] . second );
	if( l >= r ){
		if( o[ l ] . op == 2 )
			if( find( o[ l ] . u ) == find( o[ l ] . v ) ) printf( "Y\n" );
			else printf( "N\n" );
		return;
	}
	int mid = l + r >> 1;
	dfs( ls( u ) , l , mid ) , dfs( rs( u ) , mid + 1 , r );
	while( tp > cur ) 
		fa[ del[ tp ] . first ] = del[ tp ] . first , dep[ del[ tp ] . first ] = del[ tp ] . second , tp --;
}

void solve(){
	for( int i = 1 ; i <= ( n << 1 ) ; i ++ ) fa[ i ] = i , dep[ i ] = 1;
	while( 1 ){
		char op[ 6 ];
		scanf( "%s" , op );
		if( op[ 0 ] == 'E' ) break;
		int u1 = IO :: read() , v1 = IO :: read() , u2 = IO :: read() , v2 = IO :: read();
		int u = ( u1 - 1 ) * n + v1 , v = ( u2 - 1 ) * n + v2;
		if( op[ 0 ] == 'O' ){
			o[ ++ m ] = { u , v , 0 };
			s[ u ][ v ] = m;
		}
		else if( op[ 0 ] == 'C' ){
			o[ ++ m ] = { u , v , 1 }; 
			insert( 1 , 1 , 1e5 , s[ u ][ v ] , m - 1 , make_pair( u , v ) );
			s[ u ] . erase( s[ u ] . find( v ) );
		}
		else o[ ++ m ] = { u , v , 2 };
	}
	for( int i = 1 ; i <= ( n << 1 ) ; i ++ )
		for( mIt it = s[ i ] . begin() ; it != s[ i ] . end() ; it ++ )
			insert( 1 , 1 , 1e5 , it -> second , m , make_pair( o[ it -> second ] . u , o[ it -> second ] . v ) );
	dfs( 1 , 1 , 1e5 );
}

void input(){ n = IO :: read(); }

int main(){
	input();
	solve();
	return 0;
}
题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签