莫队的板子题。
维护一个 \(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;
}
这题是需要判断树上两条路径是否相交。
记两条路径分别为 \(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;
}