Post 89

Veröffentlicht am

要不是没带笔我就写作业了。

所以今天成为了本学期开学以来第一次放弃文化课来学OI，hhhhhh

补完了线段树合并的锅，其实就是调了调bug。

然后还剩点时间，有没带笔，就看了看联赛T2难度爆零的一道题。

前排置顶特大喜讯：高二那一届自招直接取消了。

马上就可以退役啦，开心~~

[POI2013]LAN-Colorful Chain

题意

给定一个$1e6$的序列，给定$1e6$的询问，每个询问包含$s_i,l_i$

问你$l_i$长度的$s_i$这个串出现了几次。

sb洛谷智障翻译。要不是做水题就用LOJ和BZOJ

题解

本来想用高级一点的SA随便做。

只需要后缀排序后二分即可。

结果发现$\sum l_i$是没有限制的。这样就不能对那些询问串直接建SA了。

然而由于都是一样的字符。

所以我们预处理每个后缀最长相同字符前缀长度$h_i$，指针模拟即可，由于有单调右移，这个复杂度是$O(n)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void pre()
{
 int r = 1;
 for(int i = 1 ; i <= n ; ++i)
 {
	 r = std::max(r , i);
	 if(i != r) {
		 h[i] = r - l + 1;
		 continue;
	 }
	 while(r < n) if(s[r + 1] == s[i]) ++ r;
 }
}

至于后缀首字母是什么，$O(1)$得到即可。。

然后后缀排序。然后用线段树维护$h_{sa_i}$

然后对于一个询问$(s_i,l_i)$，我们二分出合法的后缀区间。（一个显然的平凡性质，后缀排序后对于一个给定的串作为模式串匹配的后缀集合排序后是连续的，反证法即可证明）。

记：$c_i^{l_i}$表示一个长度为$l_i$的字符为$c_i$串。

证明：设询问是$(ci,l_i)$,假设排序后不是连续的，即$\exists s_k , LCP(c_i^{l_i},s_k) < L \and (LCP(s{k-1},ci^{l_i}) >= L \or LCP(s{k+1},c_i^{l_i}) >= L) $

此时第$L$个字符与字典序排序矛盾，因此原命题成立。

当然这个一句话证明有点不是太严谨，$k-1$和$k+1$不一定满足上述条件。

从字典序的定义出发，首先第一个字符是$s_i$，开头比$s_i$小的都在前面，大的都在$s_i$后面。

所以开头是$s_i$的构成一个连续区间$[l,r]$。

将$[l,r]$按照$[1,n]$的方法归纳证明，得到结论：

对于一个给定的相同前缀$S$，其匹配后缀必为连续区间。

以上可能是我神志不清的潮废话

然后线段树查询区间和就完成了一次询问。。。。。

所以SA上二分一个区间，再线段树查询一个区间和。

仔细想想真的需要线段树吗？静态查询一个区间和应该用啥？

数组！

$sumi = \sum\limits{j=1}^{i}h_{sa_j}$

复杂度是$O(nlogn+mlogn+m)$

二分出区间这个东西挺麻烦。

我这真的是在做联赛T2难度的题？

当然不是，我读错题了。。。

白写了这么多：

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
int seg[maxn<<2] , n , m , p[maxn] , s[maxn] , l[maxn] , h[maxn] ;
long long sum[maxn];
//h is the longest same letter of a suffix...
namespace SA
{
	 int sa[maxn] , rk[maxn] , c[maxn] , pos[maxn] , ct , m;
	 inline void Sort()
	 {
		 for(int i = 1 ; i <= m ; ++i)
			 c[i] = 0;
		 for(int i = 1 ; i <= ct ; ++i)
			 ++c[rk[pos[i]]];
		 for(int i = 1 ; i <= m ; ++i)
			 c[i] += c[i - 1];
		 for(int i = ct ; i >= 1 ; --i)
			 sa[c[rk[pos[i]]]--] = pos[i];
	 }
	 inline void SA()
	 {
		 m = ct = n;
		 for(int i = 1 ; i <= n ; ++i)
			pos[i] = i , rk[i] = s[i];
		 Sort();
		 for(int k = 1 ; k <= n ; k <<= 1)
		 {
			 ct = 0 ;
			 for(int i = n - k + 1 ; i <= n ; ++i) pos[++ct] = sa[i];
			 for(int i = 1 ; i <= n ; ++i)
				 if(sa[i] > k)
					 pos[++ct] = sa[i] - k;
			 Sort();
			 std::swap(rk,pos);
			 rk[sa[1]] = ct = 1;
			 for(int i = 2 ; i <= n ; ++i) //pos is the rank value by sort !!!
				 rk[sa[i]] = (pos[sa[i]] == pos[sa[i-1]] && pos[sa[i]+k] == pos[sa[i-1]+k]) ? ct : ++ct;
			 if((m = ct) == n) break;
		 }
	 }
	 inline void pre()
	 {
		 int r = 1;
		 for(int i = 1 ; i <= n ; ++i)
		 {
			 r = std::max(r , i);
			 if(i != r) {
				 h[i] = r - l + 1;
				 continue;
			 }
			 while(r < n) if(s[r + 1] == s[i]) ++ r;
		 }
	 }
}

一看输出只有一个数，然后看了遍题。

原来是恰好$m$个$(s_i,l_i)$的字串有多少个。

这不是sb题吗？？直接双指针开始扫，即时判断当前字符加入，如果超了一直移动左指针，否则移动右指针并更新数组，为了避免大量暴力重复扫描，用变量记录有多少个满足了，$m$个满足时$Ans += 1$。答案最大是n。

说的更清晰一点。

按照右端点分类，每个右端点最多有一个符合答案。

需要注意到的是，由于每个字符都是给定数目的，因此当一个右端点与左端点形成的字串某个字符超过数目的时候，左端点向右移动直到满足条件位置这个贪心做法是正确的：

对于新的右端点$r$，如果左端点保持不动，则每个字符数目只会增加不会下降，所以多的字符还是不符合答案，假如都没有大于，则需要更多字符，此时移动左端点没有意义。因此左端点有单调性。

真的懒得给普及题写一个形而上的符号系统证明了

然后就是指针模拟的一堆细节。。。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
int cnt[maxn] , cur , ans , ln[maxn] , n , m , c[maxn] , l[maxn], s[maxn];

void print()
{
	for(int i = 1 ; i <= n ; ++i)
		printf("%d ",cnt[i]);
	putchar(10);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d",&l[i]);
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d",&c[i]);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&s[i]);
	for(int i = 1 ; i <= m ; ++i)
		ln[c[i]] = std::max(ln[c[i]] , l[i]);
//	for(int i = 1 ; i <= n ; ++i)
//		printf("%d ",ln[i]);
//	putchar(10);

	int l = 1 , r = 0; // [l,r]
	while(r < n)
	{
		++r;
		++cnt[s[r]];
		if(cnt[s[r]] == ln[s[r]]) ++cur;
		else if(cnt[s[r]] == ln[s[r]] + 1) --cur;
		if(cur == m) ++ ans;
//		print();
		if(cnt[s[r]] > ln[s[r]])
		{
			while(cnt[s[r]] > ln[s[r]])
			{
				--cnt[s[l]];
				if(cnt[s[l]] == ln[s[l]]) ++cur;
				else if(cnt[s[l]] == ln[s[l]] - 1) --cur;
				++l;
//				print();
				if(cur == m) ++ans;
			}
		}
	}
	printf("%d",ans);
}

然后看了一道贪心构造题，太神仙不会写搜索，写挂，加上闻之喜讯，换了道题。

[POI2014]KUR-Couriers

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半

说明

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半 n,m\leq 500000n,m≤500000

题解

想到分治就很简单了吧。

对值域分治，用一种数据结构快速查询一个权值区间的数的个数。不断缩小范围。使用权值线段树。显然一个数的个数超过一半那它的父区间也超过一半，并且数惟一。

由于需要查询区间又因为个数满足可减性，因此可持久化权值线段树即可。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500055
int tot , a[maxn] , rt[maxn] , seg[maxn<<5] , lc[maxn<<5] , rc[maxn<<5] , n , m;

inline void pushup(int x){
	seg[x] = seg[lc[x]] + seg[rc[x]];
}

inline void cpy(int x , int y){
	lc[x] = lc[y] , rc[x] = rc[y] , seg[x] = seg[y];
}

void ins(int&p , int pre , int pos , int l , int r)
{
	p = ++tot;
	cpy(p , pre);
	if(l == r){
		seg[p] ++;
		return ;
	}
	int mid = l + r >> 1;
	if(pos <= mid) ins(lc[p] , lc[pre] , pos , l , mid);
	else ins(rc[p] , rc[pre] , pos , mid + 1 , r);
	pushup(p);
}

void build(int l , int r , int& p)
{
	p = ++tot;
	if(l == r) return;
	int mid = l + r >> 1;
	build(l , mid , lc[p]);
	build(mid + 1 , r , rc[p]);
}

int query(int ir , int il , int l , int r , int ct)
{
	if(l == r) return l;
	int cnt1 = seg[lc[ir]] - seg[lc[il]] , cnt2 = seg[rc[ir]] - seg[rc[il]];
	int mid = l + r >> 1;
//	printf("QUERY : %d %d %d %d %d\n",cnt1 , cnt2, l ,r , ct);
	if(cnt1 > ct) return query(lc[ir] , lc[il] , l ,mid, ct);
	else if(cnt2 > ct) return query(rc[ir] , rc[il] , mid + 1 ,r , ct);
	return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]);
	build(1 , n , rt[0]);
	for(int i = 1 ; i <= n ; ++i)
		ins(rt[i] , rt[i-1] , a[i] , 1 , n);
	for(int i = 1 ; i <= m ; ++i)
	{
		int l , r;
		scanf("%d%d",&l,&r);
		printf("%d\n",query(rt[r] , rt[l-1] , 1 , n , r - l + 1 >> 1));
	}
}