2022.1 写题记录(2022.1 question writing record)

P2709 小B的询问

莫队的板子题。

维护一个 \(c_i\) 为 \(i\) 的出现次数,如果 \(c_i \gets c_i\pm1\) 的话,\(c_i^2\) 的值完全平方公式展开一下就可得减去 \(2c_i+1\) 或加上 \(2c_i-1\)。

然后莫队维护一下就好了,时间复杂度\(O(n^{1.5})\)。

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cmath>

typedef long long ll;

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 = 5e4 + 225;

int n , m , w;
int siz;
int cnt[ N ] , a[ N ];
ll ans[ N ];
ll sum;

struct Query{
	int l , r , id , pos;
}q[ N ];

inline bool comp( Query u , Query v ){
	return u . pos == v . pos ? u . r < v . r : u . pos < v . pos;
}

inline void del( int u ){
	-- cnt[ a[ u ] ];
	sum -= 2 * cnt[ a[ u ] ] + 1;
}

inline void add( int u ){
	++ cnt[ a[ u ] ];
	sum += 2 * cnt[ a[ u ] ] - 1;
}

void solve(){
	int l = 1 , r = 0;
	sort( q + 1 , q + m + 1 , comp );
	for( int i = 1 ; i <= m ; i ++ ){
		while( l < q[ i ] . l ) del( l ++ );
		while( l > q[ i ] . l ) add( -- l );
		while( r < q[ i ] . r ) add( ++ r );
		while( r > q[ i ] . r ) del( r -- );
		ans[ q[ i ] . id ] = sum;
	}
	for( int i = 1 ; i <= m ; i ++ ) printf( "%lld\n" , ans[ i ] );
}

void input(){
	n = IO :: read() , m = IO :: read() , w = IO :: read();
	siz = sqrt( n ) * 0.9;
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] = IO :: read();
	for( int i = 1 ; i <= m ; i ++ )
		q[ i ] . l = IO :: read() , q[ i ] . r = IO :: read() , q[ i ] . id = i , q[ i ] . pos = ( q[ i ] . l - 1 ) / siz + 1;
}

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

P7764 [COCI2016-2017#5] Poklon

还是莫队。

当一次指针移动对答案有贡献的时候,就是移动前该值为 \(2\) 或移动后该值为 \(2\),按情况加减就好。

哦这个还要离散化的。

时间复杂度 \(O(n^{1.5})\)。

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cmath>
# include <vector>

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;

int n , m , w;
int siz;
int cnt[ N ] , a[ N ];
int ans[ N ];
int sum;
vector< int > re;

struct Query{
	int l , r , id , pos;
}q[ N ];

inline bool comp( Query u , Query v ){
	return u . pos == v . pos ? u . r < v . r : u . pos < v . pos;
}

inline void del( int u ){
	if( cnt[ a[ u ] ] == 2 ) -- sum;
	-- cnt[ a[ u ] ];
	if( cnt[ a[ u ] ] == 2 ) ++ sum;
}

inline void add( int u ){
	if( cnt[ a[ u ] ] == 2 ) -- sum;
	++ cnt[ a[ u ] ];
	if( cnt[ a[ u ] ] == 2 ) ++ sum;
}

void solve(){
	sort( re . begin() , re . end() );
	re . erase( unique( re . begin() , re . end() ) , re . end() );
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] = lower_bound( re . begin() , re . end() , a[ i ] ) - re . begin();
	int l = 1 , r = 0;
	sort( q + 1 , q + m + 1 , comp );
	for( int i = 1 ; i <= m ; i ++ ){
		while( l < q[ i ] . l ) del( l ++ );
		while( l > q[ i ] . l ) add( -- l );
		while( r < q[ i ] . r ) add( ++ r );
		while( r > q[ i ] . r ) del( r -- );
		ans[ q[ i ] . id ] = sum;
	}
	for( int i = 1 ; i <= m ; i ++ ) printf( "%d\n" , ans[ i ] );
}

void input(){
	n = IO :: read() , m = IO :: read();
	siz = sqrt( n ) * 0.9;
	re . push_back( -1 );
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] = IO :: read() , re . push_back( a[ i ] );
	for( int i = 1 ; i <= m ; i ++ )
		q[ i ] . l = IO :: read() , q[ i ] . r = IO :: read() , q[ i ] . id = i , q[ i ] . pos = ( q[ i ] . l - 1 ) / siz + 1;
}

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

P3398 仓鼠找sugar

这题是需要判断树上两条路径是否相交。

记两条路径分别为 \(p_1(u,v)\),\(p_2(x,y)\),它们各自的 \(LCA\) 为 \(f_{p_1},f_{p_2}\)。

那么必定会有 \(f_{p_1}\) 在 \(p_2\) 上或 \(f_{p_2}\) 在 \(p_1\) 上。

其实我也不会证这个东西的正确性…不过这个是对的。

那么判某个点是否在一条路径上的话,这样想,如果这个点到路径两端点的距离和这个路径的长度相等的话,这个点就在这个路径上了。

然后距离就用深度差分一下,树剖一个 \(LCA\) 就水过了。

\(O(n\log n)\)。

其实一开始想的是用树剖链改链查的方式打标记,先将 \(p_1\) 打上标记,再查询 \(p_2\) 是否有标记即可。

这样子是 \(O(n\log^2 n)\)。

# include <iostream>
# include <cstdio>
# include <cmath>

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;
	}
}

const int N = 6e5 + 225;

using namespace std;

// -- Graph -- 

# define E( u ) head[ u ]
# define u( u ) edge[ u ] . frm
# define v( u ) edge[ u ] . to
# define nxt( u ) edge[ u ] . nxt
# define forE( u , i ) for( int i = head[ u ] ; i ; i = edge[ i ] . nxt )

struct Edge{		
	int nxt , to;
}edge[ N << 1 ];
	
int head[ N ] , eg;
	
inline void add_edge( int u , int v ){
	edge[ ++ eg ] = { head[ u ] , v } , head[ u ] = eg;
}

// -- Graph -- 

int n , q , cnt , rt;
int idx[ N ] , dep[ N ] , siz[ N ] , ch[ N ] , fa[ N ] , tp[ N ]; 

void dfs1( int u , int fath ){
	fa[ u ] = fath , dep[ u ] = dep[ fath ] + 1 , siz[ u ] = 1;
	forE( u , i ){
		int v = v( i );
		if( v == fath ) continue;
		dfs1( v , u );
		siz[ u ] += siz[ v ];
		if( siz[ ch[ u ] ] < siz[ v ] ) ch[ u ] = v;
	}
}

void dfs2( int u , int top ){
	idx[ u ] = ++ cnt;
	tp[ u ] = top;
	if( ch[ u ] ) dfs2( ch[ u ] , top );
	forE( u , i ){
		int v = v( i );
		if( v == fa[ u ] || v == ch[ u ] ) continue;
		dfs2( v , v );
	}
}

int lca( int u , int v ){
	while( tp[ u ] != tp[ v ] ){
		if( dep[ tp[ u ] ] < dep[ tp[ v ] ] ) swap( u , v );
		u = fa[ tp[ u ] ];
	}
	return dep[ u ] < dep[ v ] ? u : v;	
}

int dis( int u , int v ){
	int f = lca( u , v );
	return abs( dep[ f ] - dep[ u ] ) + abs( dep[ f ] - dep[ v ] );
}

void solve(){
	for( int i = 1 ; i <= q ; i ++ ){
		int u = IO :: read() , v = IO :: read();
		int p = IO :: read() , q = IO :: read();
		
		int f1 = lca( u , v ) , f2 = lca( p , q );
		
		/*int disuv = dis( u , v );
		int dispq = dis( p , q );
		
		int fuv = lca( u , v ) , fpq = lca( p , q );
		int disfpquv = dis( fpq , u ) + dis( fpq , v );
		int disfuvpq = dis( fuv , p ) + dis( fuv , q );*/
		if( dis( u , v ) == dis( u , f2 ) + dis( v , f2 ) || dis( p , q ) == dis( p , f1 ) + dis( q , f1 ) ) printf( "Y\n" );
		else printf( "N\n" );
	}
}

void input(){
	n = IO :: read() , q = IO :: read();
	for( int i = 1 ; i <= n - 1 ; i ++ ){
		int u = IO :: read() , v = IO :: read();
		add_edge( u , v );
		add_edge( v , u );
	}	
}

int main(){
	input();
	dfs1( 1 , 0 );
	dfs2( 1 , 1 );
	solve();
	return 0;
}
————————

P2709 small B’s inquiry

Mo’s board problem.

Maintain the occurrence times of a \ (c_i \) as \ (I \). If \ (c_i \ gets c_i \ PM1 \), expand the square formula of the value of \ (c_i ^ 2 \) to subtract \ (2c_i + 1 \) or add \ (2c_i-1 \).

Then, it’s good for Mo team to maintain it. The time complexity \ (O (n ^ {1.5}) \).

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cmath>

typedef long long ll;

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 = 5e4 + 225;

int n , m , w;
int siz;
int cnt[ N ] , a[ N ];
ll ans[ N ];
ll sum;

struct Query{
	int l , r , id , pos;
}q[ N ];

inline bool comp( Query u , Query v ){
	return u . pos == v . pos ? u . r < v . r : u . pos < v . pos;
}

inline void del( int u ){
	-- cnt[ a[ u ] ];
	sum -= 2 * cnt[ a[ u ] ] + 1;
}

inline void add( int u ){
	++ cnt[ a[ u ] ];
	sum += 2 * cnt[ a[ u ] ] - 1;
}

void solve(){
	int l = 1 , r = 0;
	sort( q + 1 , q + m + 1 , comp );
	for( int i = 1 ; i <= m ; i ++ ){
		while( l < q[ i ] . l ) del( l ++ );
		while( l > q[ i ] . l ) add( -- l );
		while( r < q[ i ] . r ) add( ++ r );
		while( r > q[ i ] . r ) del( r -- );
		ans[ q[ i ] . id ] = sum;
	}
	for( int i = 1 ; i <= m ; i ++ ) printf( "%lld\n" , ans[ i ] );
}

void input(){
	n = IO :: read() , m = IO :: read() , w = IO :: read();
	siz = sqrt( n ) * 0.9;
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] = IO :: read();
	for( int i = 1 ; i <= m ; i ++ )
		q[ i ] . l = IO :: read() , q[ i ] . r = IO :: read() , q[ i ] . id = i , q[ i ] . pos = ( q[ i ] . l - 1 ) / siz + 1;
}

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

P7764 [COCI2016-2017#5] Poklon

Or mo.

When a pointer movement contributes to the answer, the value is \ (2 \) before the movement or \ (2 \) after the movement. Add or subtract as appropriate.

Oh, this one needs to be discretized.

Time complexity \ (O (n ^ {1.5}) \).

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cmath>
# include <vector>

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;

int n , m , w;
int siz;
int cnt[ N ] , a[ N ];
int ans[ N ];
int sum;
vector< int > re;

struct Query{
	int l , r , id , pos;
}q[ N ];

inline bool comp( Query u , Query v ){
	return u . pos == v . pos ? u . r < v . r : u . pos < v . pos;
}

inline void del( int u ){
	if( cnt[ a[ u ] ] == 2 ) -- sum;
	-- cnt[ a[ u ] ];
	if( cnt[ a[ u ] ] == 2 ) ++ sum;
}

inline void add( int u ){
	if( cnt[ a[ u ] ] == 2 ) -- sum;
	++ cnt[ a[ u ] ];
	if( cnt[ a[ u ] ] == 2 ) ++ sum;
}

void solve(){
	sort( re . begin() , re . end() );
	re . erase( unique( re . begin() , re . end() ) , re . end() );
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] = lower_bound( re . begin() , re . end() , a[ i ] ) - re . begin();
	int l = 1 , r = 0;
	sort( q + 1 , q + m + 1 , comp );
	for( int i = 1 ; i <= m ; i ++ ){
		while( l < q[ i ] . l ) del( l ++ );
		while( l > q[ i ] . l ) add( -- l );
		while( r < q[ i ] . r ) add( ++ r );
		while( r > q[ i ] . r ) del( r -- );
		ans[ q[ i ] . id ] = sum;
	}
	for( int i = 1 ; i <= m ; i ++ ) printf( "%d\n" , ans[ i ] );
}

void input(){
	n = IO :: read() , m = IO :: read();
	siz = sqrt( n ) * 0.9;
	re . push_back( -1 );
	for( int i = 1 ; i <= n ; i ++ ) a[ i ] = IO :: read() , re . push_back( a[ i ] );
	for( int i = 1 ; i <= m ; i ++ )
		q[ i ] . l = IO :: read() , q[ i ] . r = IO :: read() , q[ i ] . id = i , q[ i ] . pos = ( q[ i ] . l - 1 ) / siz + 1;
}

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

P3398 hamster looking for sugar

This problem is to judge whether the two paths on the tree intersect.

Note that the two paths are \ (p_1 (U, V) \), \ (p_2 (x, y) \), and their respective \ (LCA \) is \ (f_ {p_1}, f_ {p_2} \).

Then there must be \ (f_{p_1} \) on \ (p_2 \) or \ (f_{p_2} \) on \ (p_1 \).

In fact, I won’t prove the correctness of this thing But this is right.

If you decide whether a point is on a path, think like this. If the distance from the point to the points at both ends of the path is equal to the length of the path, the point is on the path.

Then, the distance is differentiated by depth, and the water passes after a \ (LCA \) tree section.

\(O(n\log n)\)。

In fact, at the beginning, I wanted to mark with the method of tree section chain instead of chain query. First mark \ (p_1 \), and then query whether \ (p_2 \) has a mark.

This is \ (O (n \ log ^ 2 n) \).

# include <iostream>
# include <cstdio>
# include <cmath>

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;
	}
}

const int N = 6e5 + 225;

using namespace std;

// -- Graph -- 

# define E( u ) head[ u ]
# define u( u ) edge[ u ] . frm
# define v( u ) edge[ u ] . to
# define nxt( u ) edge[ u ] . nxt
# define forE( u , i ) for( int i = head[ u ] ; i ; i = edge[ i ] . nxt )

struct Edge{		
	int nxt , to;
}edge[ N << 1 ];
	
int head[ N ] , eg;
	
inline void add_edge( int u , int v ){
	edge[ ++ eg ] = { head[ u ] , v } , head[ u ] = eg;
}

// -- Graph -- 

int n , q , cnt , rt;
int idx[ N ] , dep[ N ] , siz[ N ] , ch[ N ] , fa[ N ] , tp[ N ]; 

void dfs1( int u , int fath ){
	fa[ u ] = fath , dep[ u ] = dep[ fath ] + 1 , siz[ u ] = 1;
	forE( u , i ){
		int v = v( i );
		if( v == fath ) continue;
		dfs1( v , u );
		siz[ u ] += siz[ v ];
		if( siz[ ch[ u ] ] < siz[ v ] ) ch[ u ] = v;
	}
}

void dfs2( int u , int top ){
	idx[ u ] = ++ cnt;
	tp[ u ] = top;
	if( ch[ u ] ) dfs2( ch[ u ] , top );
	forE( u , i ){
		int v = v( i );
		if( v == fa[ u ] || v == ch[ u ] ) continue;
		dfs2( v , v );
	}
}

int lca( int u , int v ){
	while( tp[ u ] != tp[ v ] ){
		if( dep[ tp[ u ] ] < dep[ tp[ v ] ] ) swap( u , v );
		u = fa[ tp[ u ] ];
	}
	return dep[ u ] < dep[ v ] ? u : v;	
}

int dis( int u , int v ){
	int f = lca( u , v );
	return abs( dep[ f ] - dep[ u ] ) + abs( dep[ f ] - dep[ v ] );
}

void solve(){
	for( int i = 1 ; i <= q ; i ++ ){
		int u = IO :: read() , v = IO :: read();
		int p = IO :: read() , q = IO :: read();
		
		int f1 = lca( u , v ) , f2 = lca( p , q );
		
		/*int disuv = dis( u , v );
		int dispq = dis( p , q );
		
		int fuv = lca( u , v ) , fpq = lca( p , q );
		int disfpquv = dis( fpq , u ) + dis( fpq , v );
		int disfuvpq = dis( fuv , p ) + dis( fuv , q );*/
		if( dis( u , v ) == dis( u , f2 ) + dis( v , f2 ) || dis( p , q ) == dis( p , f1 ) + dis( q , f1 ) ) printf( "Y\n" );
		else printf( "N\n" );
	}
}

void input(){
	n = IO :: read() , q = IO :: read();
	for( int i = 1 ; i <= n - 1 ; i ++ ){
		int u = IO :: read() , v = IO :: read();
		add_edge( u , v );
		add_edge( v , u );
	}	
}

int main(){
	input();
	dfs1( 1 , 0 );
	dfs2( 1 , 1 );
	solve();
	return 0;
}