Yijan's Blog HomeArchives
10.19 模拟赛

contest

A 二次剩余

明显，当 $|x-m| \ge 320$ 的时候，这个二次函数的值必然大于了 $10^5$ ，但是 $k \le 10^5$ ，于是我们往两边枚举 $O(\sqrt n)$ 个，对于每个值维护一个堆即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 100006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , q;
int A[MAXN];
multiset<int> fk[MAXN];

int main() {
//	freopen("ex_two1.in","r",stdin);
	cin >> n >> q;
	rep( i , 1 , n ) {
		static int m , k;
		scanf("%d%d",&m,&k);
		fk[m].insert( k );
	}
	int tot = n;
	while( q-- ) {
		static int op , x , y;
		scanf("%d%d%d",&op,&x,&y);
		if( op == 1 ) fk[x].insert( y ) , ++ tot;
		else {
			rep( i , max( x - 320 , 1 ) , min( x + 320 , 100000 ) ) if( fk[i].size() ) {
				set<int>::iterator cur = fk[i].begin();
				for( ; cur != fk[i].end() ; ++ cur ) {
					if( ( x - i ) * 1ll * ( x - i ) + *cur > y ) break;
					-- tot;
				}
				fk[i].erase( fk[i].begin() , cur );
			}
		}
		printf("%d\n",tot);
	}
}

B 倍数区间

我们建出 ST 表后，可以二分每个点作为 $\gcd$ 的时候左边右边可以延伸到哪里。

不难发现可以倍增，于是后面那个操作的复杂度变成了 $O(n\log n)$ 。

建 ST 表的过程相当于连续取 $\gcd$ ，变化是 $O(\log n)$ 次的，于是复杂度也是 $O(\log n)$ 。

总复杂度 $O(n\log n)$ ，非常好写。

贴一下题解用栈实现的线性做法，看起来也很好写：

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
answer
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];
int G[MAXN][20];
int gcd( int a , int b ) {
	return !b ? a : gcd( b , a % b );
}
int que( int l , int r ) {
	int lg = 31 - __builtin_clz( r - l + 1 );
	return gcd( G[l][lg] , G[r - ( 1 << lg ) + 1][lg] );
}

int R[MAXN] , L[MAXN];
void solve() {
	cin >> n;
	rep( i , 1 , n ) {
		scanf("%d",A + i);
	}
	rep( i , 1 , n ) G[i][0] = A[i];
	rep( k , 1 , 19 ) {
		rep( i , 1 , n - ( 1 << k ) + 1 ) G[i][k] = gcd( G[i][k - 1] , G[i + ( 1 << k - 1 )][k - 1] );
	}
	rep( i , 1 , n ) {
		int cur = i;
		per( k , 19 , 0 ) if( G[cur][k] && G[cur][k] % A[i] == 0 ) {
			cur += ( 1 << k );
		}
		R[i] = cur - 1;
	}
	int as = 0;
	per( i , n , 1 ) {
		int cur = i;
		per( k , 19 , 0 ) if( cur - ( 1 << k ) + 1 > 0 && G[cur - ( 1 << k ) + 1][k] % A[i] == 0 ) cur -= ( 1 << k );
		L[i] = cur + 1;
		as = max( as , R[i] - L[i] );
	}
	vi re;
	rep( i , 1 , n ) if( as == R[i] - L[i] ) re.pb( L[i] );
	sort( all( re ) );
	re.erase( unique( all( re ) ) , re.end() );
	cout << re.size() << ' ' << as << endl;
	rep( i , 0 , re.size() - 1 ) printf("%d ",re[i]);
}

signed main() {
	//freopen("interval.in","r",stdin);
	//freopen("interval.out","r",stdin);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

C 飞翔的鸟

我们设 $F_{i,j}$ 表示经历了障碍的长度为 $n$ 的区间，从 $i$ 飞到 $j$ 的方案数，$G_{i,j}$ 表示没有经历障碍的。

于是我们可以分治下去，$F_{n,i,j} = \sum_k G_{\frac n 2,i,k} \times F_{\frac n 2 ,k,j}+F_{\frac n 2,i,k} \times G_{\frac n 2 ,k,j}$ （也就是一个矩乘的形式）。

注意单独转移一下最后的那一个，也就是判一下 $n$ 为奇数的时候。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 133
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 1000000007
int n , k , a , b;
int A[MAXN];

int F[MAXN][MAXN] , G[MAXN][MAXN] , g[MAXN][MAXN] , f[MAXN][MAXN];
void solve( int n ) {
	if( n == 0 ) {
		rep( i , 1 , k ) G[i][i] = 1;
		return;
	}
	solve( n / 2 );
	mem( f ) , mem( g );
	rep( i , 1 , k ) rep( j , 1 , k ) rep( t , 1 , k ) {
		g[i][j] = ( g[i][j] + G[i][t] * 1ll * G[t][j] ) % P;
		f[i][j] = ( f[i][j] + F[i][t] * 1ll * G[t][j] + G[i][t] * 1ll * F[t][j] ) % P;
	}
	memcpy( G , g , sizeof g );
	memcpy( F , f , sizeof f );
	if( n & 1 ) {
		rep( i , 1 , k ) rep( j , 1 , k ) G[i][j] = ( 1ll * g[i][j - 1] + g[i][j + 1] + g[i][j] ) % P;
		rep( i , 1 , k ) rep( j , 1 , k ) {
			F[i][j] = ( 1ll * f[i][j - 1] + f[i][j + 1] + f[i][j] ) % P;
			if( j < b && j > a ) F[i][j] = ( F[i][j] + 1ll * g[i][j - 1] + g[i][j + 1] + g[i][j] ) % P;
		}
	}
}

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

void solve() {
	cin >> n >> k >> a >> b;
	solve( n - 2 );
	memcpy( f , F , sizeof f );
	rep( i , 1 , k ) rep( j , 1 , k ) F[i][j] = ( f[i][j - 1] + 1ll * f[i][j + 1] + f[i][j] ) % P;
	cout << F[k / 2][k / 2] * 1ll * Pow( n - 2 , P - 2 ) % P << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

D ZYT的答案

套路题，考虑一条钥匙 - 答案路径，相当于是给开头在钥匙子树内，结尾在答案子树内的路径 $+1$ ，用经典套路转一下就是矩阵加，最后求全局最大值。

注意一下如果 $x=y$ 的情况，我们先把标记打到点上，然后对于每个点 $O(\deg)$ 枚举儿子，给从这个儿子到之前的儿子的路径，以及这个儿子到子树外的路径 $+1$ 即可。还需要判一下从 $x$ 走出的路径。

一种比较好写的做法是先给全局 $+1$ ，然后给每个儿子子树内的路径和子树外的路径 $-1$ ，这样会好写的多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 2000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];
vi G[MAXN];

int L[MAXN] , R[MAXN] , clo;
int g[MAXN][19] , dep[MAXN];
void dfs( int u , int f ) {
	L[u] = ++ clo;
	for( int v : G[u] ) if( v != f ) {
		dep[v] = dep[u] + 1;
		g[v][0] = u;
		rep( k , 1 , 18 ) if( g[g[v][k-1]][k-1] ) g[v][k] = g[g[v][k-1]][k-1]; else break;
		dfs( v , u );
	}
	R[u] = clo;
}

int work( int u , int v ) {
	per( k , 18 , 0 ) if( dep[g[u][k]] > dep[v] ) u = g[u][k];
	return u;
}

struct mdf {
	int x , l , r , c;
} Q[MAXN] ; int cnt = 0;

bool cmp( mdf a , mdf b ) {
	return a.x < b.x;
}

int T[MAXN << 2] , lz[MAXN << 2];
inline void pu( int rt ) {
	T[rt] = max( T[rt << 1] , T[rt << 1 | 1] );
}
inline void ad( int rt , int c ) {
	T[rt] += c , lz[rt] += c;
}
inline void pd( int rt ) {
	if( lz[rt] ) {
		ad( rt << 1 , lz[rt] ) , ad( rt << 1 | 1 , lz[rt] );
		lz[rt] = 0;
	}
}
void add( int rt , int l , int r , int L , int R , int c ) {
	if( L <= l && R >= r ) { ad( rt , c ); return; }
	pd( rt );
	int m = l + r >> 1;
	if( L <= m ) add( rt << 1 , l , m , L , R , c );
	if( R > m ) add( rt << 1 | 1 , m + 1 , r , L , R , c );
	pu( rt );
}

int ori[MAXN];
void afs( int u , int fa ) {
	if( ori[u] ) {
		int w = ori[u];
		Q[++ cnt] = (mdf) { 1 , L[u] , L[u] , w };
		Q[++ cnt] = (mdf) { L[u] + 1 , L[u] , L[u] , -w };
		Q[++ cnt] = (mdf) { R[u] + 1 , L[u] , L[u] , w };
		
		Q[++ cnt] = (mdf) { L[u] , 1 , L[u] - 1 , w };
		Q[++ cnt] = (mdf) { L[u] + 1 , 1 , L[u] - 1 , -w };
		Q[++ cnt] = (mdf) { L[u] , R[u] + 1 , n , w };
		Q[++ cnt] = (mdf) { L[u] + 1 , R[u] + 1 , n , -w };
	}
	int rr = 0;
	for( int v : G[u] ) if( v != fa ) {
		if( ori[u] ) {
			int w = ori[u];
			Q[++ cnt] = (mdf) { 1 , L[v] , R[v] , w };
			Q[++ cnt] = (mdf) { L[v] , L[v] , R[v] , -w };
			Q[++ cnt] = (mdf) { R[u] + 1 , L[v] , R[v] , w };
			
			Q[++ cnt] = (mdf) { L[v] , 1 , L[v] - 1 , w };
			Q[++ cnt] = (mdf) { R[v] + 1 , 1 , L[v] - 1 , -w };
			Q[++ cnt] = (mdf) { L[v] , R[u] + 1 , n , w };
			Q[++ cnt] = (mdf) { R[v] + 1 , R[u] + 1 , n , -w };
		}
		afs( v , u );
		rr = R[v];
	}
}

void solve() {
//	freopen("input","r",stdin) , freopen("fuckout","w",stdout);
	cin >> n >> m;
	rep( i , 2 , n ) {
		static int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , G[v].pb( u );
	}
	dep[1] = 1 , dfs( 1 , 1 );
	rep( i , 1 , m ) {
		static int u , v , w;
		scanf("%d%d%d",&u,&v,&w);
		if( u == v ) {
			ori[u] += w;
			continue;
		}
		if( L[u] > R[v] || L[v] > R[u] ) {
			Q[++ cnt] = (mdf) { L[v] , L[u] , R[u] , w };
			Q[++ cnt] = (mdf) { R[v] + 1 , L[u] , R[u] , -w };
		} else {
			if( L[u] < L[v] ) {
				int k = work( v , u );
				Q[++ cnt] = (mdf) { L[v] , 1 , L[k] - 1 , w };
				Q[++ cnt] = (mdf) { R[v] + 1 , 1 , L[k] - 1 , -w };
				Q[++ cnt] = (mdf) { L[v] , R[k] + 1 , n , w };
				Q[++ cnt] = (mdf) { R[v] + 1 , R[k] + 1 , n , -w };
			} else {
				int k = work( u , v );
				Q[++ cnt] = (mdf) { 1 , L[u] , R[u] , w };
				Q[++ cnt] = (mdf) { L[k] , L[u] , R[u] , -w };
				Q[++ cnt] = (mdf) { R[k] + 1 , L[u] , R[u] , w };
			}
		}
	}
	afs( 1 , 1 );
	sort( Q + 1 , Q + 1 + cnt , cmp );
	int cur = 1 , res = 0;
	rep( x , 1 , n ) {
		while( cur <= cnt && Q[cur].x == x ) {
			add( 1 , 0 , n + 1 , Q[cur].l , Q[cur].r , Q[cur].c );
			++ cur;
		}
		res = max( res , T[1] );
	}
	cout << res << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

文章作者: yijan
文章链接: https://yijan.co/1019-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！