Yijan's Blog HomeArchives
5.22 模拟赛

B 漏网之鱼

考虑求 $mex$ 这个操作，如果固定左端点，右端点不断向右移动时可以非常方便地维护这个操作。所以我们可以先固定左端点 $1$ ，向右求出每个 $[1,r]$ 的 $mex$ 值。

考虑对所有右端点维护左端点固定的时候的 $mex$ 值，现在考虑如果向右移动一次左端点，如果左端点从 $l$ 变成了 $l+1$ ，假设下一个 $a_l$ 的出现位置是 $p$ ，那么不难发现所有右端点在 $p$ 后面的区间都不会受到影响，而所有右端点在 $[l+1,r]$ 的答案会与 $a_l$ 取最小值。

如果有 $l=1,r=n$ ，我们只需要求出左端点从 $1$ 移动到 $n$ 时所有右端点用线段树维护的值的和就完事了。因为 $mex$ 函数明显单调递增，所以区间取 $\min$ 操作可以线段树。每次能取 $\min$ 的必然是一段区间，相当于是进行区间赋值操作。

但是当 $[l,r]$ 不固定，我们考虑把查询 $[l,r]$ 变成查询左右端点在 $[1,r]$ 的答案，减去左右端点在 $[1,l-1]$ 的答案，再减去左端点在 $[1,l-1]$ ，右端点在 $[l,r]$ 的答案。

考虑前两个询问怎么整，比如要查询 $[1,r]$ 的所有区间和，相当于对于左端点在 $[1,r]$ 的所有版本求出 $[1,r]$ 的区间的和。对于第二种操作，相当于是在 $[1,l-1]$ 的版本中查询 $[l,r]$ 的和。也就是说我们需要一棵求历史版本区间和的线段树。

为了方便，我们可以把区间取 $\min$ 操作变成区间加操作。具体来说，我们只有遇到值完全一样的区间才进行操作，这样就相当于是区间加法了。同时，如果这个节点最大值大于了取 $\min$ 的那个值，我们就 skip 这个区间。不难发现，每次操作我们都会合并一些段，总的合并次数是 $O(n)$ 的。

现在考虑怎么求历史版本和。我们考虑对于每个线段树节点维护一个形如 $f(t) = kt+b$ 的函数，其中 $t$ 是当前版本，$k,b$ 是我们维护的两个值。如果给这个节点上的区间集体 $+x$ ，相当于是给函数变成了 $f’(t) = kt+b+x(t-t_1)$ ，其中 $t_1$ 是当前的版本编号。于是我们可以把区间加变成了给 $k$ 加，给 $b$ 加，同时给区间打上区间赋值的标记。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
#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] , re[MAXN];
int buc[MAXN] , lst[MAXN] , nxt[MAXN];

struct que {
	int r , ll , rr , idx , c;
} Q[MAXN * 3] ; int cnt;
bool cmp( const que& a , const que& b ) {
	return a.r < b.r;
}

int kk[MAXN << 2] , bb[MAXN << 2] , tk[MAXN << 2] , tb[MAXN << 2] , T[MAXN << 2] , tg[MAXN << 2] , fk[MAXN << 2];
void pu( int rt ) {
	kk[rt] = kk[rt << 1] + kk[rt << 1 | 1] , bb[rt] = bb[rt << 1] + bb[rt << 1 | 1];
	T[rt] = max( T[rt << 1] , T[rt << 1 | 1] );
	fk[rt] = ( fk[rt << 1] & fk[rt << 1 | 1] & T[rt << 1] == T[rt << 1 | 1] );
}
inline void fuck( int rt , int c ) {
	T[rt] = tg[rt] = c , fk[rt] = 1;
}
void pd( int rt , int m ) {
	int ls = rt << 1 , rs = rt << 1 | 1;
	if( tk[rt] ) {
		kk[ls] += tk[rt] * ( m - ( m >> 1 ) ) , kk[rs] += tk[rt] * ( m >> 1 );
		tk[ls] += tk[rt] , tk[rs] += tk[rt];
		tk[rt] = 0;
	}
	if( tb[rt] ) {
		bb[ls] += tb[rt] * ( m - ( m >> 1 ) ) , bb[rs] += tb[rt] * ( m >> 1 );
		tb[ls] += tb[rt] , tb[rs] += tb[rt];
		tb[rt] = 0;
	}
	if( ~tg[rt] ) {
		fuck( ls , tg[rt] ) , fuck( rs , tg[rt] );
		tg[rt] = -1;
	}
}
void build( int rt , int l , int r ) {
	if( l == r ) { T[rt] = kk[rt] = re[l] , fk[rt] = 1; return; }
	int m = l + r >> 1;
	build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
	pu( rt );
}
int t1;
void chkmn( int rt , int l , int r , int L , int R , int c ) {
	if( L <= l && R >= r && T[rt] <= c ) return;
	if( L <= l && R >= r && fk[rt] ) {
		kk[rt] += ( c - T[rt] ) * ( r - l + 1 ) , bb[rt] -= t1 * ( c - T[rt] ) * ( r - l + 1 );
		tk[rt] += c - T[rt] , tb[rt] -= t1 * ( c - T[rt] );
		fuck( rt , c );
		return;
	} 
	pd( rt , r - l + 1 );
	int m = l + r >> 1;
	if( L <= m ) chkmn( rt << 1 , l , m , L , R , c );
	if( R > m ) chkmn( rt << 1 | 1 , m + 1 , r , L , R , c );
	pu( rt );
}
int query( int rt , int l , int r , int L , int R ) {
	if( L <= l && R >= r ) {
		return kk[rt] * t1 + bb[rt];
	}
	pd( rt , r - l + 1 );
	int m = l + r >> 1 , ret = 0;
	if( L <= m ) ret += query( rt << 1 , l , m , L , R );
	if( R > m ) ret += query( rt << 1 | 1 , m + 1 , r , L , R );
	return ret;
}
int ans[MAXN];
void solve() {
	int typ; cin >> typ;
	cin >> n;
	rep( i , 1 , n ) scanf("%lld",A + i) , A[i] = min( A[i] , n );
	int cur = 0;
	rep( i , 1 , n ) {
		++ buc[A[i]];
		while( buc[cur] ) ++ cur;
		re[i] = cur;
	}
	rep( i , 0 , n ) lst[i] = n + 1;
	per( i , n , 1 ) nxt[i] = lst[A[i]] , lst[A[i]] = i;
	cin >> q;
	int l , r;
	rep( i , 1 , q ) {
		scanf("%lld%lld",&l,&r);
		Q[++ cnt] = (que) { r , 1 , r , i , 1 };
		if( l != 1 ) {
			Q[++ cnt] = (que) { l - 1 , 1 , l - 1 , i , -1 };
			Q[++ cnt] = (que) { l - 1 , l , r , i , -1 };
		}
	}
	sort( Q + 1 , Q + 1 + cnt , cmp );
	cur = 1;
	memset( tg , -1 , sizeof tg );
	build( 1 , 1 , n );
	rep( i , 1 , n ) {
		t1 = i;
		while( cur <= cnt && Q[cur].r == i ) 
			ans[Q[cur].idx] += Q[cur].c * query( 1 , 1 , n , Q[cur].ll , Q[cur].rr ) , ++ cur;
		chkmn( 1 , 1 , n , i , nxt[i] - 1 , A[i] );
	}
	rep( i , 1 , q ) printf("%lld\n",ans[i]);
}

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

C 浑水摸鱼

考虑如何求本质不同子串数量。一种想法是后缀排序后求出 height数组即可。

后缀排序的过程中，我们需要比较两个后缀的大小关系。可以先二分出 LCP 的长度，然后比较 LCP 后一个位置的第一次出现位置谁更靠前即可。

而 height 数组就是后缀排序后相邻的 LCP 长度。

而 LCP 需要判断两个子串相同。考虑如何判断两个子串相同，可以使用一种奇妙的 hash 方式，具体来说，可以写出

其中 $nxt$ 为这个位置的字符下一次出现的位置，如果没有这个位置，那么 $nxt[i] = i$。

如果到一个区间 $[l,r]$ 上，就是求 $\sum_{nxt[i] \le r,l \le i \le r} (nxt[i] - i)\times P^i$ 。

由于需要在线求，可以主席树维护这个东西。

这题有点卡常，需要转成直接查后缀。而且得 stable_sort ，虽然不知道为什么这样会快很多。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "assert.h"
using namespace std;
#define MAXN 200006
//#define int long long
#pragma GCC optimize("Ofast")
#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 pos[MAXN];
int base = 191;
#define P 418254373

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

int T[MAXN * 20] , ls[MAXN * 20] , rs[MAXN * 20] , cnt = 0 , rt[MAXN];
void add( int& rt , int old , int l , int r , int p , int c ) {
//	if( l == 1 && r == n ) {
//		printf("%d %d\n",p,c);
//	}
	rt = ++ cnt , T[rt] = T[old] , ls[rt] = ls[old] , rs[rt] = rs[old];
	T[rt] = ( T[rt] + c ) % P;
	if( l == r ) return;
	int m = l + r >> 1;
	if( p <= m ) add( ls[rt] , ls[old] , l , m , p , c );
	else add( rs[rt] , rs[old] , m + 1 , r , p , c );
}
int L , R;
int que( int rt , int l , int r ) {
	if( L <= l ) return T[rt];
	int m = l + r >> 1;
	if( L <= m ) return ( que( ls[rt] , l , m ) + T[rs[rt]] ) % P;
	return que( rs[rt] , m + 1 , r );
}
void build( int& rt , int l , int r ) {
	if( !rt ) rt = ++ cnt;
	if( l == r ) return;
	int m = l + r >> 1;
	build( ls[rt] , l , m ) , build( rs[rt] , m + 1 , r );
}

int lst[MAXN] , pw[MAXN] , iv[MAXN];
int rnk[MAXN]; // ith suffix is rnk[i]

int has( int l , int r ) {
	L = l;
	return que( rt[r] , 1 , n ) * 1ll * iv[l] % P;
}

int getit( int x , int l ) {
	return *lower_bound( all( pos[x] ) , l ) - l;
}

inline bool cmp( int a , int b ) {
	int l = 0 , r = min( n - a , n - b );
	while( l <= r ) {
		int mid = l + r >> 1;
		if( has( a , a + mid ) == has( b , b + mid ) ) l = mid + 1;
		else r = mid - 1;
	}
	if( a + r + 1 > n || b + r + 1 > n ) return a > b;
	return getit( A[a + r + 1] , a ) < getit( A[b + r + 1] , b ); 
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%d",A + i) , pos[A[i]].pb( i );
	pw[0] = iv[0] = 1;
	rep( i , 1 , n ) pw[i] = pw[i - 1] * 1ll * base % P , iv[i] = Pow( pw[i] , P - 2 );
	build( rt[0] , 1 , n );
	rep( i , 1 , n ) {
		if( lst[A[i]] ) add( rt[i] , rt[i - 1] , 1 , n , lst[A[i]] , ( i - lst[A[i]] ) * 1ll * pw[lst[A[i]]] % P );
		else rt[i] = rt[i - 1];
		lst[A[i]] = i;
	}
	rep( i , 1 , n ) rnk[i] = i;
	stable_sort( rnk + 1 , rnk + 1 + n , cmp );
//	rep( i , 1 , n ) printf("%d\n",rnk[i]);
	ll ans = n * ( n + 1ll ) / 2;
	rep( i , 2 , n ) {
		int t = rnk[i] , p = rnk[i - 1];
		int l = 0 , r = min( n - t , n - p );
		while( l <= r ) {
			int mid = l + r >> 1;
			if( has( t , t + mid ) == has( p , p + mid ) ) l = mid + 1;
			else r = mid - 1;
		}
		ans -= r + 1;
	}
	cout << ans << endl;
}

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


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