Post 25

Veröffentlicht am | Edited on

多幸运 在最美的年纪 遇见你 没有遗憾和可惜

调出一道分块的较高难度的一道题（用了3小时以上）

原因是什么呢？经过各种造数据，对拍，二分错误位置，精确定位，精确数据分析后，终于发现是变量名写错了！

img

原来写成了vector数组比较（怪不得一开始不但WA还TLE）。。

这种睿智的错误出一次不少时间就浪费掉，导致现在我还是机房垫底水平。。。

我们一起来看看这道题。

[Violet]蒲公英

题目背景

亲爱的哥哥：

你在那个城市里面过得好吗？

我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……

最近村子里长出了一大片一大片的蒲公英。一刮风，这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面，让哥哥看看就好了呢！

哥哥你要快点回来哦！

爱你的妹妹 Violet

Azure 读完这封信之后微笑了一下。

“蒲公英吗……”

题目描述

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为n的序列 (a_1,a_2..a_n)(a1,a2..an)，其中 a_iai 为一个正整数，表示第i棵蒲公英的种类编号。

而每次询问一个区间 [l,r]，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的

输入输出格式

输入格式：

第一行两个整数 n,m ，表示有n株蒲公英，m 次询问。

接下来一行n个空格分隔的整数 a_iai ，表示蒲公英的种类

再接下来m 行每行两个整数 l_0,r_0l0,r0，我们令上次询问的结果为 x（如果这是第一次询问， 则 x=0）。

令 $l=(l_0+x-1)\bmod n + 1,r=(r_0+x-1) \bmod n + 1$，如果 l>r，则交换 l,r 。

最终的询问区间为[l,r]。

输出格式：

输出m 行。每行一个整数，表示每次询问的结果。

输入输出样例

1
2
3
4
5
6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5
1
2
3
1 
2 
1

说明

对于 100% 的数据，保证 $1\le n \le 40000,1\le m \le 50000,1\le a_i \le 10^9$

题解

比起思路，我倒想记录下对于这种题该怎么综合调试。

首先，虽然题目要求强制在线，但如果你本地调试也“强制在线”，那就是个傻瓜。

然后对于这种暴力很好写的题，在发现程序出错后在15分钟内拼手速打出对拍加数据生成器。

拍出组你认为可调试的，比如对于这道题来说，n不要很大，不然实在难调，但是询问尽量多，可以更容易拍出错误的同时并不会增加调试难度。

对于出错的询问，就得看自己的观察力了。

说说这题的思路。

首先你需要先想到分块这种东西（想不到就爱莫能助了），发现一个区间是如何大段维护的，然后考虑怎么快速处理边角，这就是大体思路了。

Solve1

首先说一个比较好想的。

离散化，必须的。

我们对序列分块，分T块。

枚举整块区间$O(T^2)$，对于每个整块区间，将每个数出现的次数都存起来，是一个$O(n)$的复杂度。顺便统计每个区间的众数。

上述预处理的过程时空复杂度均为$O(nT^2)$

那么接下来我们如何处理每一个查询呢？设查询左右端点为$l$，$r$.

一个众数要么是其中内嵌最大整块区间，要么是边角的数，我们就可用“大段维护，边角暴力”来解决这个问题了。

我们只需要把边角的数扔进最大整块区间的桶里，扔的时候注意及时判断，最后扫一遍肯定是不行的（讲真一开始我想如何快速统计众数就差点没从整个扫一遍中找出做法来）

然后回答询问，然后把边角的数减掉就行了。这样每次最多就是两块，也就是说每次$O(n/T)$

这样做的时间复杂度是$O(nT^2+mn/T)$

求导求拐点，算出最优T大概是$^3\sqrt{n}$

此时空间复杂度可以接受，时间复杂度为$O(n^{\frac{5}{3}})$

没错就是莫队复杂度。。

这也是我能想出来的解法了，让我们看一个更神仙的解法

solve2

这次我们只处理出整段区间的众数。时间复杂度$O(nT)$

然后$O(n)$把每个离散化的元素用个vector桶把每个元素的位置都push进去

讲真这种方法牛逼就牛逼在这个vector的灵活的应用，它使得我们可以以$O(logn)$的时间完成对任意元素在一个区间里出现的次数。

如何想到这种方法是一个很有意思的问题，其实想到边角快速处理就已经接近了，只不过这个确实挺难想到。

然后后面的就好办了，每次暴力查询边角更新答案即可。

时间复杂度$O(nT+mn/Tlogn)$

这东西不是很会分析。。总之以后写分块定义两个变量，块大小和块数量，方便调块大小。

好像$T=\sqrt{nlogn}$取得最优值，为$O(n\sqrt{nlogn})$

第一种实在简单没写，写了第二种，由于忘了调块大小，所以跑的很慢。。。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 40005
#define maxm 50005
#define maxsqrt 205
std::vector<int> pos[maxn];
int n , m , base , lastans ,  tmp[maxn] , p[maxsqrt][maxsqrt] , c[maxsqrt][maxsqrt] , st[maxn] , L[maxn] , R[maxn] , v[maxn] , tot , b[maxn];
struct Node{
	int v, k;
	bool operator<(const Node& x)const{
		return v < x.v;
	}
}a[maxn];

inline int find(const std::vector<int> &val , int bndl , int bndr)
{
	int l = 0 , r = val.size() - 1 , ans1 = 0 , ans2 = 0;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(val[mid] <= bndr) ans1 = mid , l = mid + 1;
		else r = mid - 1;
	}
	l = 0 , r = val.size() - 1;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(val[mid] >= bndl) ans2 = mid , r = mid - 1;
		else l = mid + 1;
	}
	return ans1 - ans2 + 1;
}

inline void pre()
{
	base = std::sqrt(n);
	for(int i = 1 ; i <= base ; ++i)
		L[i] = (i-1) * base + 1, R[i] = i * base;
	if(R[base] < n) ++base , L[base] = R[base-1] + 1 , R[base] = n;
	for(int i = 1 ; i <= base ; ++i)
		for(int j = L[i] ; j <= R[i] ; ++j)
			st[j] = i;
	std::sort(a+1,a+n+1);
	for(int i = 1 ; i <= n ; ++i)
	{
		if(a[i].v == a[i-1].v) v[a[i].k] = tot , b[tot] = a[i].v;
		else v[a[i].k] = ++tot , b[tot] = a[i].v;
	}
	for(int i = 1 ; i <= n ; ++i)
		pos[v[i]].push_back(i);

	for(int i = 1 ; i <= base ; ++i)
	{
		int now = 0 , ans = 0;
		std::memset(tmp,0,sizeof(tmp));
		for(int j = i ; j <= base ; ++j)
		{
			for(int k = L[j] ; k <= R[j] ; ++k){
				++tmp[v[k]];
				if(tmp[v[k]] > now) now = tmp[v[k]] , ans = v[k];
				else if(tmp[v[k]] == now && v[k] < ans) ans = v[k];
			}
			c[i][j] = now , p[i][j] = ans;
		}
	}
}	

inline int query(int l , int r)
{
	if(st[l] == st[r])
	{
		int ans = 0 , now = 0;
		for(int i = l ; i <= r ; ++i)
		{
			int cur = find(pos[v[i]] , l , r);
			if(cur > now) now = cur , ans = v[i];
			else if(cur == now && v[i] < ans) ans = v[i];
		}
//		printf("equal %d %d %d ",l,r,now);
		return ans;
	}
	 int posl = 0 , posr = 0;
	 if(l != L[st[l]]) posl = L[st[l]+1];
	 else posl = l;
	 if(r != R[st[r]]) posr = R[st[r]-1];
	 else posr = r;
	 int ans = p[st[posl]][st[posr]] , now = c[st[posl]][st[posr]];
	 for(int i = l ; i < posl ; ++i)
	 {
		 int curnow = find(pos[v[i]] , l , r);
		 if(curnow > now){
			 now = curnow , ans = v[i];
		 }
		 else if(curnow == now && v[i] < ans) ans = v[i];
	 }
	for(int i = posr + 1 ; i <= r ; ++i){
		int curnow = find(pos[v[i]] , l , r);
		if(curnow > now){
			now = curnow , ans = v[i];
		}
		else if(curnow == now && v[i] < ans) ans = v[i];
	}
//	printf("NONEQUAL %d %d %d ",l,r,now);
	return ans;
}


int main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i].v) , a[i].k = i;
	pre();
	while(~--m)
	{
		int l , r;
		scanf("%d%d",&l,&r);
		l = (l + lastans - 1) % n + 1 , r = (r + lastans - 1) % n + 1;
		if(l > r) std::swap(l,r);
		printf("%d\n",lastans = b[query(l,r)]);
	}
}

看到篇不错的文章，作者省队水平？

https://czyhe.me/other/other/noip-mess/

开始学文化课。。

一定要明白如何解决下面这个问题：

给定一个序列长度为$n$，如何快速查找$m$次某一元素值在一个区间内出现的次数。$n,m \leq 100000$

方法是将序列离散化（如果值过大），然后用vector数组的下标当桶映射元素值，将每个元素的位置从左到右push进元素值相应的vector里，不难发现任意vector的下标都是从左到右递增的，因此可以分治查找。

时间复杂度$O((n+m)logn)$