【BZOJ4241】历史研究

Description

IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。

日记中记录了连续N天发生的时间，大约每天发生一件。

事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示，Xi越大，事件的规模就越大。

JOI教授决定用如下的方法分析这些日记：

1. 选择日记中连续的一些天作为分析的时间段

2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)

3. 计算出所有事件种类的重要度，输出其中的最大值

现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

Input

第一行两个空格分隔的整数N和Q，表示日记一共记录了N天，询问有Q次。

接下来一行N个空格分隔的整数X1...XN，Xi表示第i天发生的事件的种类

接下来Q行，第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi，表示第i次询问的区间为[Ai,Bi]。

Output

输出Q行，第i行(1<=i<=Q)一个整数，表示第i次询问的最大重要度

Sample Input

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

Sample Output

9
8
8
16
16

HINT

1<=N<=10^5

1<=Q<=10^5

1<=Xi<=10^9 (1<=i<=N)

题解：第一眼看题都感觉是莫队吧？然而听说这题卡莫队。

这题的本质是一个带权的区间众数问题，如果你会做区间众数，那么这道题也不难（当然不会做也无所谓）。

先分块，假设[a,b]是[l,r]中一段连续的整块，那么[l,r]中的带权众数∈（[a,b]中的众数 U [l,a)和(b,r]中的所有数）。那么我们预处理出任意两个块(a,b)之间的带权众数（方法：枚举左边的块，在暴力扫一遍右边的所有块，用桶记录一下，维护个最大值），以及[1,a]中所有数出现的次数。处理询问时，先直接拿出中间整块的众数，再枚举两边小块的所有数即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int maxn=100010;

int n,m,nm,B;

ll ans;

struct node

{

	int val,org;

}num[maxn];

int v[maxn],ref[maxn],st[maxn],s[400][maxn];

ll mx[400][400];

bool cmp(node a,node b)

{

	return a.val<b.val;

}

int rd()

{

	int ret=0;	char gc=getchar();

	while(gc<'0'||gc>'9')	gc=getchar();

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret;

}

int main()

{

	n=rd(),m=rd();

	B=int(sqrt(double(n)));

	int i,j,k,a,b,c,d;

	for(i=0;i<n;i++)	num[i].val=rd(),num[i].org=i;

	sort(num,num+n,cmp);

	for(ref[0]=-1,i=0;i<n;i++)

	{

		if(num[i].val>ref[nm])	ref[++nm]=num[i].val;

		v[num[i].org]=nm;

	}

	for(i=0;i<n;i++)	s[i/B][v[i]]++;

	for(i=1;i*B<n;i++)	for(j=1;j<=nm;j++)	s[i][j]+=s[i-1][j];

	for(i=0;i*B<n;i++)

	{

		for(j=i;j*B<n;j++)

		{

			mx[i][j]=mx[i][j-1];

			for(k=j*B;k<j*B+B&&k<n;k++)	st[v[k]]++,mx[i][j]=max(mx[i][j],(ll)st[v[k]]*ref[v[k]]);

		}

		memset(st,0,sizeof(st));

	}

	for(i=1;i<=m;i++)

	{

		a=rd()-1,b=rd()-1,c=a/B,d=b/B,ans=0;

		if(c==d)

		{

			for(j=a;j<=b;j++)	st[v[j]]++,ans=max(ans,(ll)st[v[j]]*ref[v[j]]);

			for(j=a;j<=b;j++)	st[v[j]]=0;

			printf("%lld\n",ans);

			continue;

		}

		ans=mx[c+1][d-1];

		for(j=a;j<c*B+B;j++)	st[v[j]]=s[d-1][v[j]]-s[c][v[j]];

		for(j=d*B;j<=b;j++)	st[v[j]]=s[d-1][v[j]]-s[c][v[j]];

		for(j=a;j<c*B+B;j++)	st[v[j]]++,ans=max(ans,(ll)st[v[j]]*ref[v[j]]);

		for(j=d*B;j<=b;j++)	st[v[j]]++,ans=max(ans,(ll)st[v[j]]*ref[v[j]]);

		for(j=a;j<c*B+B;j++)	st[v[j]]=0;

		for(j=d*B;j<=b;j++)	st[v[j]]=0;

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

【BZOJ4241】历史研究分块

【BZOJ4241】历史研究

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

【BZOJ4241】历史研究 分块

【BZOJ4241】历史研究

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

【BZOJ4241】历史研究分块