欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ 4241: 历史研究

程序员文章站 2022-05-27 19:07:23
...

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)

Source

JOI 2013~2014 春季training合宿 竞技1 By PoPoQQQ

Solution

  • 题意 : 多次询问区间中的 每个数*其出现次数 的最大值。

  • 我们可以离散化后做莫队,但是普通莫队是不可行的,因为删去最大值我们并不知道次大值。

  • 这是我们需要稍作修改——回滚莫队!

  • 同样将询问区间按左端点所属块为第一关键字、右端点为第二关键字从小到大排,

  • 每次我们将左指针置于块的最右端,每次重新移动即可。

  • 若询问的区间在同一块内就 O(n)O(\sqrt n) 暴力统计。

  • 总时间复杂度是 O(nn)O(n\sqrt n) 的。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long LL;
const int N=1e5+5;
struct data
{
	int l,r,id;
}c[N];
LL sum;
int a[N],b[N],bel[N],t[N],cnt[N];
LL ans[N];
inline int read()
{
	int X=0,w=0; char ch=0;
	while(!isdigit(ch)) w|=ch=='-',ch=getchar();
	while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	return w?-X:X;
}
inline bool cmp(data x,data y)
{
	return bel[x.l]<bel[y.l] || bel[x.l]==bel[y.l] && x.r<y.r;
}
inline LL max(LL x,LL y)
{
	return x>y?x:y;
}
inline int min(int x,int y)
{
	return x<y?x:y;
}
inline void add(int x)
{
	cnt[a[x]]++;
	sum=max(sum,(LL)cnt[a[x]]*b[a[x]]);
}
inline void del(int x)
{
	cnt[a[x]]--;
}
int main()
{
	int n=read(),q=read();
	int size=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		a[i]=b[i]=read();
		bel[i]=(i-1)/size+1;
	}
	sort(b+1,b+1+n);
	b[0]=unique(b+1,b+1+n)-(b+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+b[0],a[i])-b;
	for(int i=1;i<=q;i++) c[i].l=read(),c[i].r=read(),c[i].id=i;
	sort(c+1,c+1+q,cmp);
	for(int i=1,j=1;i<=n;i+=size)
	{
		sum=0;
		int up=min(n,i+size-1);
		int l=up+1,r=up;
		memset(cnt,0,sizeof(cnt));
		while(j<=q && bel[i]==bel[c[j].l])
		{
			if(bel[c[j].l]==bel[c[j].r])
			{
				LL val=0;
				for(int k=c[j].l;k<=c[j].r;k++) t[a[k]]=0;
				for(int k=c[j].l;k<=c[j].r;k++)
				{
					t[a[k]]++;
					val=max(val,(LL)t[a[k]]*b[a[k]]);
				}
				ans[c[j].id]=val;
				j++;
				continue;
			}
			while(r<c[j].r) add(++r);
			LL val=sum;
			while(l>c[j].l) add(--l);
			ans[c[j].id]=sum;
			while(l<=up) del(l++);
			sum=val;
			j++;
		}
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}
相关标签: 莫队算法