[洛谷 4168][Violet 6] 蒲公英【普通分块】

  • 2018-02-12
  • 0
  • 0

Problem:

时间限制: 2000MS    空间限制: 512MB

题目背景

亲爱的哥哥:
你在那个城市里面过得好吗?
我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说!它把人们的房子和田地搞坏,还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……
最近村子里长出了一大片一大片的蒲公英。一刮风,这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面,让哥哥看看就好了呢!
哥哥你要快点回来哦!
爱你的妹妹 Violet

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

“蒲公英吗……”

题目描述

在乡下的小路旁种着许多蒲公英,而我们的问题正是与这些蒲公英有关。
为了简化起见,我们把所有的蒲公英看成一个长度为n的序列 (a1 , a2 .. an),其中 ai 为一个正整数,表示第i棵蒲公英的种类编号。
而每次询问一个区间 [ l , r ],你需要回答区间里出现次数最多的是哪种蒲公英,如果有若干种蒲公英出现次数相同,则输出种类编号最小的那个。

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

输入输出格式

输入格式:
第一行两个整数 m , n ,表示有 n 株蒲公英,m 次询问。
接下来一行 n 个空格分隔的整数 ai ,表示蒲公英的种类
再接下来 m 行每行两个整数 l0 , r0 ​,我们令上次询问的结果为 x(如果这是第一次询问, 则 x=0)。
令 l = (l0 + x - 1) mod n + 1 , r = (r0 + x - 1) mod n + 1 ,如果 l > r,则交换 l , r 。
最终的询问区间为 [ l , r ]。

输出格式:
输出m 行。每行一个整数,表示每次询问的结果。

输入输出样例

输入样例#1:

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

输出样例#1:

1 
2 
1

说明

对于 20% 的数据,保证 1 ≤ n , m ≤ 3000 。
对于 100% 的数据,保证 1 ≤ n ≤ 40000 , 1 ≤ m ≤ 50000 , 1 ≤ ai ≤ 109

Solution:

# 蛤?洛谷上难度竟然有 NOI/NOI+/CTSC。。吓人的吧。。 #

这道题是分块的经典问题——区间众数问题 (Range Mode Query, RMQ)。

区间众数不满足可合并性,故树状数组线段树无法对其进行维护,不能做到单次 O(logn)

而暴力的单次复杂度为 O(n),所以需要分块根号平衡的思想将复杂度变成单次 O(n0.5)

首先对 a[] 进行离散化,并按每块大小为 n0.5,将区间分为 n0.5 块。

对每一块块内每个数的个数,这一步复杂度为 O(n)

对其求前缀和,复杂度为 O(n0.5) * O(值域) = O(n0.5*值域) = O(n1.5)

对每一块求出块内众数,复杂度同样为 O(n0.5) * O(值域) = O(n1.5)

根据众数的以下性质

  • 对于可重集合 A 和 B,若 A 中众数为 a,则 A ∪ B 的众数只可能为 a 或某个 b ∈ B

我们可以枚举 i, j,从块内众数推出第 i ~ j 块的众数,复杂度为 O(n0.5*n0.5*n0.5) = O(n1.5)

然后查询时,[l, r] 的众数只可能出现在中间完整块的众数和两边零散部分的所有数中。

这些数的数量不会超过 2n0.5,所以只要暴力枚举统计即可,单次复杂度为 O(n0.5)

注意储存这些数的数组空间不能忽略前面的常数 2 !!!

总复杂度为 O(n1.5+mn0.5),但常数较大,有待优化。

Code: O(n1.5+mn0.5) [21085K, 5832MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

template<typename T>
inline void getint(T &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int n, m, a[40002], blocksz, blockcnt, l, r, ans;
int bl[40002], disc[40002];
int cnt[202][40002], sum[202][40002], mas[202][202];
int qnum[402], topq, qcnt[40002];

inline int query(int l, int r){
	topq = 0, memset(qcnt, 0, sizeof(qcnt));
	if(bl[l] == bl[r]){
		for(register int i = l; i <= r; i++)
			if(++qcnt[a[i]] == 1) qnum[++topq] = a[i];
	}
	else{
		for(register int i = bl[l] * blocksz; i >= l; i--)
			if(++qcnt[a[i]] == 1) qnum[++topq] = a[i];
		for(register int i = (bl[r] - 1) * blocksz + 1; i <= r; i++)
			if(++qcnt[a[i]] == 1) qnum[++topq] = a[i];
		for(register int i = 1; i <= topq; i++)
			qcnt[qnum[i]] += sum[bl[r] - 1][qnum[i]] - sum[bl[l]][qnum[i]];
		if(bl[l] + 1 < bl[r]){
			int &midmas = mas[bl[l] + 1][bl[r] - 1];
			if(qcnt[midmas] == 0){
				qnum[++topq] = midmas;
				qcnt[midmas] = sum[bl[r] - 1][midmas] - sum[bl[l]][midmas];
			}
		}
	}
	int id = 0;
	for(register int i = 1; i <= topq; i++)
		if(qcnt[qnum[i]] > qcnt[id] || (qcnt[qnum[i]] == qcnt[id] && qnum[i] < id))
			id = qnum[i];
	return disc[id];
}

int main(){
	getint(n), getint(m);
	blocksz = (int)ceil(sqrt(n)), blockcnt = (n - 1) / blocksz + 1;
	for(register int i = 1; i <= n; i++) bl[i] = (i - 1) / blocksz + 1;
	for(register int i = 1; i <= n; i++) getint(a[i]), disc[i] = a[i];
	sort(disc + 1, disc + n + 1);
	int d = unique(disc + 1, disc + n + 1) - disc - 1;
	for(register int i = 1; i <= n; i++)
		a[i] = lower_bound(disc + 1, disc + d + 1, a[i]) - disc;
	// Discretization
	for(register int i = 1; i <= n; i++) cnt[bl[i]][a[i]]++;
	for(register int i = 1; i <= blockcnt; i++)
		for(register int j = 1; j <= d; j++)
			sum[i][j] = sum[i - 1][j] + cnt[i][j];
	for(register int i = 1; i <= blockcnt; i++){
		mas[i][i] = 0;
		for(register int j = 1; j <= d; j++)
			if(cnt[i][j] > cnt[i][mas[i][i]]) mas[i][i] = j;
	}
	for(register int i = 1; i < blockcnt; i++)
		for(register int j = i + 1; j <= blockcnt; j++){
			int &curmas = mas[i][j];
			curmas = mas[i][j - 1];
			int mxmas = sum[j][mas[i][j]] - sum[i - 1][mas[i][j]];
			for(register int k = (j - 1) * blocksz + 1; k <= j * blocksz; k++){
				int kmas = sum[j][a[k]] - sum[i - 1][a[k]];
				if(kmas > mxmas || (kmas == mxmas && a[k] < curmas))
					curmas = a[k], mxmas = kmas;
			}
		}
	for(register int i = 1; i <= m; i++){
		int l_, r_;
		getint(l_), getint(r_);
		l = (l_ + ans - 1) % n + 1, r = (r_ + ans - 1) % n + 1;
		if(l > r) swap(l, r);
		ans = query(l, r);
		printf("%d\n", ans);
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai