# 2022.1 写题记录(2022.1 question writing record)-其他

## 2022.1 写题记录(2022.1 question writing record)

P2709 小B的询问

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

typedef long long ll;

namespace IO{
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

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

namespace IO{
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(){
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

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

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

namespace IO{
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(){
for( int i = 1 ; i <= n - 1 ; i ++ ){
int u = IO :: read() , v = IO :: read();
}
}

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{
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{
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(){
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{
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(){
for( int i = 1 ; i <= n - 1 ; i ++ ){
int u = IO :: read() , v = IO :: read();