NOI Online 2022

P8251 [NOI Online 2022 提高组] 丹钓战

给出长度为 \(n\) 的数列，每个元素是一个二元组 \((a_i,b_i)\)。同时有一个栈 \(S\)，向栈中加入元素 \((a_i,b_i)\) 时会一直弹出满足 \(a_i=a_j\) 或 \(b_i\geq b_j\) 的栈顶元素 \((a_j,b_j)\)，然后将其加入 \(S\) 中。

若一个二元组加入 \(S\) 后满足 \(S\) 仅有其一个元素，则称其为 "成功的"。

有 \(q\) 个询问，每次询问区间 \([l,r]\) 的二元组依次入栈，会有几个是 "成功的"。询问独立。

\(n,q\leq 5\times 10^5\)。

我们模拟题意先花费 \(\Theta(n)\) 的时间对整个数列进行一次操作，那么元素 \(x_i\) 入栈后分为两种情况：

此时 \(S\) 仅有 \(x_i\) 一个元素，那么无论询问取哪个区间，\(x_i\) 都是成功的。
此时 \(S\) 有多于一个元素，设此时 \(S\) 中 \(x_i\) 下方阻挡它成功的元素为 \(x_j\)，\(j，那么 \(x_i\) 在询问时成功当且仅当 \(x_j\) 不在询问区间中。

所以在模拟时我们可以维护出一个 \(\mathrm{f}[i]=j\)，若 \(x_i\) 成功则 \(\mathrm{f}[i]=0\)。

询问转化为询问一个区间中有多少元素小于区间左端点。可以主席树维护。

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

P8252 [NOI Online 2022 提高组] 讨论

给出 \(n\) 个集合，求这 \(n\) 个集合是否存在两个集合是交叉关系。

\(n\leq 10^6\)，所有集合中的元素个数 \(m\leq 2\times 10^6\)，元素的值域为 \(n\)。

设 \(A,B\) 满足交叉关系则 \(A\cap B\neq\emptyset\)，\(A\nsubseteq B\) 且 \(B\nsubseteq A\)。也就是存在交且不包含。

我们按照集合大小从大到小遍历，维护一个 \(\mathrm{map}[x]\) 表示元素 \(x\) 当前所遍历到的最小的所属集合，初始为 \(0\)。

设当前集合为 \(S_i\)，若 \(\forall x\in S_i,\ \mathrm{map}[x]=0\)，那么这表示 \(S_i\) 与之前的所有集合都没有交。

若 \(\forall x\in S_i,\ \mathrm{map}[x]\) 都相等，那么这表示 \(S_i\) 中的所有元素都被另一个更大的集合所包含，意味着 \(S_i\) 被之前的一个集合包含了。

否则若 \(\mathrm{map}[x]\) 中有不同的，我们随意取出两个，设这两个跟 \(S_i\) 有交的集合为 \(A,B\)，\(|A|\geq|B|\)，那么 \(S_i,B\) 就是一组解。

证明，显然 \(A,B\) 要么没有交，要么 \(A\) 包含 \(B\)。所以对 \(S_i\) 中任意的满足 \(\mathrm{map}[x]\neq B\) 的 \(x\)，都满足 \(x\notin B\)，所以 \(S_i,B\) 是一组解。

然后我们在每次遍历后对 \(\forall x\in S_i\)，将 \(\mathrm{map}[x]\) 变为 \(S_i\) 即可维护 \(\mathrm{map}\)。

时间复杂度 \(O(n\log n+m)\)。若使用值域类的排序可以降到线性。

CODE - T1：

# include 
# include 
# include 
# include 

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


using namespace std;

const int N = 5e5 + 225;

struct Node{ int ls , rs , v; }t[ N << 5 ];
# define ls( u ) t[ u ] . ls
# define rs( u ) t[ u ] . rs
# define val( u ) t[ u ] . v
int root[ N ] , nod;

int n , q;

int insert( int u , int p , int l , int r , int x ){
	u = ++ nod , t[ u ] = t[ p ] , ++ val( u );
	if( l == r ) return u;
	int mid = l + r >> 1;
	if( x <= mid ) ls( u ) = insert( ls( u ) , ls( p ) , l , mid , x );
	else rs( u ) = insert( rs( u ) , rs( p ) , mid + 1 , r , x );
	return u;
}

int query( int p , int q , int l , int r , int L , int R ){
	if( L <= l && r <= R ) return val( q ) - val( p );
	int mid = l + r >> 1 , res = 0;
	if( L <= mid ) res += query( ls( p ) , ls( q ) , l , mid , L , R );
	if( R > mid ) res += query( rs( p ) , rs( q ) , mid + 1 , r , L , R );
	return res;
}

struct Element{ int a , b , id; }S[ N ] , a[ N ];
int tp;

void input(){
	n = IO :: read() , q = IO :: read();
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] . a = IO :: read();
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] . b = IO :: read();
}

void solve(){
	for( int i = 1 ; i <= n ; i ++ ){
		Element x = a[ i ];
		while( ( S[ tp ] . a == x . a || S[ tp ] . b <= x . b ) && tp > 0 ) tp --;
		if( tp ) root[ i ] = insert( root[ i ] , root[ i - 1 ] , 0 , n , S[ tp ] . id );
		else root[ i ] = insert( root[ i ] , root[ i - 1 ] , 0 , n , 0 );
		S[ ++ tp ] = { x . a , x . b , i };
	}
	for( int i = 1 ; i <= q ; i ++ ){
		int l = IO :: read() , r = IO :: read();
		printf( "%d\n" , query( root[ l - 1 ] , root[ r ] , 0 , n , 0 , l - 1 ) );
	} 
}

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

CODE - T2：

# include 
# include 
# include 
# include 
# include 

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

using namespace std;

const int N = 2e6 + 225;

vector < int > S[ N ];
# define pb push_back

int n;
int xS[ N ] , idx[ N ] , fidx[ N ] , M[ N ];

inline bool comp( int x , int y ){ return S[ x ] . size() > S[ y ] . size(); }

void Solve(){
	sort( idx + 1 , idx + n + 1 , comp );
	for( int i = 1 ; i <= n ; i ++ ){
		int x = idx[ i ] , f = 0 , col;
		for( int j = 0 ; j < S[ x ] . size() ; j ++ )
			if( M[ S[ x ][ j ] ] ){ f = 1 , col = M[ S[ x ][ j ] ]; break; }
		if( ! f ){
			for( int j = 0 ; j < S[ x ] . size() ; j ++ ) M[ S[ x ][ j ] ] = x;
			continue;
		}
		int af = 0;
		for( int j = 0 ; j < S[ x ] . size() ; j ++ ){
			if( M[ S[ x ][ j ] ] != col ){
				int y;
				if( idx[ col ] > idx[ M[ S[ x ][ j ] ] ] ) y = col;
				else y = M[ S[ x ][ j ] ];
				printf( "YES\n%d %d\n" , x , y );
				af = 1;
				break;
			}
		}
		if( af ) return;
		for( int j = 0 ; j < S[ x ] . size() ; j ++ ) M[ S[ x ][ j ] ] = x;
	}
	printf( "NO\n" );
}

void Init(){
	for( int i = 1 ; i <= n ; i ++ ){
		for( int j = 0 ; j < S[ i ] . size() ; j ++ ) M[ S[ i ][ j ] ] = 0;
		S[ i ] . clear();
	}
}

void Input(){
	n = IO :: read();
	for( int i = 1 ; i <= n ; i ++ ){
		int k = IO :: read();
		for( int j = 1 ; j <= k ; j ++ ) S[ i ] . pb( IO :: read() );
		idx[ i ] = i;
	}
}

int main(){
	int T = IO :: read();
	while( T -- ){
		Input();
		Solve();
		Init();
	}
	return 0;
}

NOI Online 2022

相关

标签