LOC 2020.11.20 - Prob. 1
(C=2^{k}mod(a+b+c))
#include <cstdio>
typedef long long LL;
int A, B, C, K;
int Qkpow( int base, int indx, int mod ){
int res = 1;
while( indx ){
if( indx & 1 ) res = ( LL )res * base % mod;
base = ( LL )base * base % mod;
indx >>= 1;
}
return res;
}
int main( ){
int TC; scanf( "%d", &TC ); while( TC -- > 0 ){
scanf( "%d%d%d%d", &A, &B, &C, &K );
printf( "%lld
", ( LL )C * Qkpow( 2, K, A + B + C ) % ( A + B + C ) );
}
return 0;
}
LOC 2020.11.20 - Prob. 2
我先行否决 naive 的线段树。
输入暗示连边？
那就连吧。
考虑每一个连通块 (S)，如果连通块是个树，就只能选 (|S|-1) 个点。
如果存在环，那么每个数都取得到。
那么可以的情况就是询问区间包含的不是一棵树。
#include <cstdio>
const int MAXN = 2e5 + 5;
template<typename _T> _T MIN( const _T x, const _T y ){ return x > y ? y : x; }
template<typename _T> _T MAX( const _T x, const _T y ){ return x > y ? x : y; }
struct pointS{
int one, ano;
pointS( int O = 0, int A = 0 ){ one = A; ano = A; }
} pntS[MAXN];
struct starS{
int to, nx;
starS( int T = 0, int N = 0 ){ to = T; nx = N; }
} as[MAXN * 2];
int N, K, Q;
int totE;
int firS[MAXN], furS[MAXN], enS[MAXN], mxV[MAXN], mnV[MAXN], vis[MAXN];
void pushEdge( const int u, const int v ){ as[++ totE] = starS( v, firS[u] ); firS[u] = totE; furS[u] ++; }
void DFS( const int u, int &mxVt, int &mnVt, int &edgeS, int &nodeS ){
mxVt = MAX( mxVt, u ); mnVt = MIN( mnVt, u );
edgeS += furS[u]; nodeS ++; vis[u] = 1;
for( int i = firS[u]; i; i = as[i].nx ){
int v = as[i].to;
if( vis[v] ) continue;
DFS( v, mxVt, mnVt, edgeS, nodeS );
}
}
int main( ) {
scanf( "%d%d", &N, &K );
for( int i = 1; i <= K; ++ i ){
scanf( "%d%d", &pntS[i].one, &pntS[i].ano );
pushEdge( pntS[i].one, pntS[i].ano );
pushEdge( pntS[i].ano, pntS[i].one );
}
for( int i = 1; i <= N; ++ i ) enS[i] = N + 1;
for( int i = 1; i <= N; ++ i ){
if( vis[i] ) continue;
int mxVt = 1, mnVt = N, edgeS = 0, nodeS = 0;
DFS( i, mxVt, mnVt, edgeS, nodeS ); edgeS >>= 1;
if( edgeS == nodeS - 1 ) enS[mnVt] = mxVt;
}
for( int i = N - 1; i; -- i ) enS[i] = MIN( enS[i], enS[i + 1] );
scanf( "%d", &Q );
while( Q -- > 0 ){
int queL, queR;
scanf( "%d%d", &queL, &queR );
if( enS[queL] > queR ) printf( "Yes
" );
else printf( "No
" );
}
return 0;
}
LOC 2020.11.20 - Prob. 3 / CF396C On Changing Tree
哇哦。
喜闻乐见的 DS 题。
大约是届一下 ( exttt{lazy tag}) 的思想。
对于一个节点 (u)，只有在路径 ((1,u)) 上的修改才会产生影响。
这个询问有够简单，差个分即可。
修改就子树加 (x)，再加个 (k)（除根节点）。
树剖，完了。
#include <cstdio>
#define mod ( 1000000007 )
typedef long long LL;
const int MAXN = 3e5 + 5;
template<typename _T>
void read( _T &x ){
x = 0; char c = getchar( ); _T f = 1;
while( c < '0' || c > '9' ){ if( c == '-' ) f = -1; c = getchar( ); }
while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar( ); }
x *= f;
}
template<typename _T>
void write( _T x ){
if( x < 0 ){ putchar( '-' ); x = -x; }
if( x > 9 ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T> void swapp( _T &x, _T &y ){ int w = x; x = y; y = w; }
struct starS{
int to, nx;
starS( int T = 0, int N = 0 ){ to = T; nx = N; }
} as[MAXN * 2];
struct nodeS{
int val, add;
nodeS( int V = 0, int A = 0 ){ val = V; add = A; }
} nodes[MAXN * 4];
int N, M;
int sjc, cnt;
int firS[MAXN], posL[MAXN], posR[MAXN], top[MAXN], son[MAXN], dep[MAXN], fur[MAXN], fa[MAXN];
void pushEdge( const int u, const int v ){ as[++ cnt] = starS( v, firS[u] ); firS[u] = cnt; }
void oneSearch( const int u, const int lst ){
fa[u] = lst; dep[u] = dep[lst] + 1; fur[u] = 1;
for( int i = firS[u]; i; i = as[i].nx ){
int v = as[i].to;
oneSearch( v, u );
fur[u] += fur[v];
if( fur[v] > fur[son[u]] ) son[u] = v;
}
}
void anotherSearch( const int u, const int nTp ){
top[u] = nTp; posL[u] = ++ sjc;
if( son[u] ) anotherSearch( son[u], nTp );
for( int i = firS[u]; i; i = as[i].nx ){
int v = as[i].to;
if( v == son[u] ) continue;
anotherSearch( v, v );
}
posR[u] = sjc;
}
void Spr( const int x, const int l, const int r ){
if( ! nodes[x].add ) return;
int mid = ( l + r ) >> 1;
nodes[x << 1].val = ( nodes[x << 1].val + ( LL )nodes[x].add * ( mid - l + 1 ) % mod ) % mod;
nodes[x << 1 | 1].val = ( nodes[x << 1 | 1].val + ( LL )nodes[x].add * ( r - mid ) % mod ) % mod;
nodes[x << 1].add = ( nodes[x << 1].add + nodes[x].add ) % mod;
nodes[x << 1 | 1].add = ( nodes[x << 1 | 1].add + nodes[x].add ) % mod;
nodes[x].add = 0;
}
void Upt( const int x ){ nodes[x].val = ( nodes[x << 1].val + nodes[x << 1 | 1].val ) % mod; }
void Modify( const int x, const int l, const int r, const int segL, const int segR, const int segW ){
if( l > segR || r < segL ) return;
if( l >= segL && r <= segR ){
nodes[x].val = ( nodes[x].val + ( LL )segW * ( r - l + 1 ) % mod ) % mod;
nodes[x].add = ( nodes[x].add + segW ) % mod;
return;
}
int mid = ( l + r ) >> 1;
Spr( x, l, r );
Modify( x << 1, l, mid, segL, segR, segW );
Modify( x << 1 | 1, mid + 1, r, segL, segR, segW );
Upt( x );
}
int Query( const int x, const int l, const int r, const int segL, const int segR ){
if( l > segR || r < segL ) return 0;
if( l >= segL && r <= segR ) return nodes[x].val;
int mid = ( l + r ) >> 1; Spr( x, l, r );
return ( Query( x << 1, l, mid, segL, segR ) + Query( x << 1 | 1, mid + 1, r, segL, segR ) ) % mod;
}
int QueryP( int u, int v ){
int res = 0;
while( top[u] != top[v] ){
if( dep[top[u]] < dep[top[v]] ) swapp( u, v );
res = ( ( res + Query( 1, 1, N, posL[top[u]], posL[u] ) ) % mod + mod ) % mod;
u = fa[top[u]];
}
if( dep[u] >= dep[v] ) swapp( u, v );
res = ( ( res + Query( 1, 1, N, posL[u], posL[v] ) ) % mod + mod ) % mod;
return res;
}
int main( ){
read( N );
for( int i = 2, lst; i <= N; ++ i ){ read( lst ); pushEdge( lst, i ); }
oneSearch( 1, 0 ); anotherSearch( 1, 1 );
read( M );
while( M -- > 0 ){
int opt, u, x, k;
read( opt );
if( opt == 1 ){
read( u ); read( x ); read( k );
Modify( 1, 1, N, posL[u], posL[u], x );
Modify( 1, 1, N, posL[u] + 1, posR[u], -k );
}
else{ read( u ); write( QueryP( 1, u ) ); putchar( '
' ); }
}
return 0;
}
LOC 2020.11.20 - Prob. 4
不想做了。