历史研究（洛谷AT_joisc2014_c 歴史の研究）

题目描述

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

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

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

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

• 选择日记中连续的几天[L,R]作为分析的时间段；

• 定义事件A的重要度W为A*T，其中T为该事件在区间[L,R]中出现的次数。

现在，您需要帮助教授求出所有事件中重要度最大的事件是哪个，并输出其重要度。

注意：教授有多组询问。

输入格式

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

接下来一行N个空格分隔的整数表示每天的事件种类。

接下来Q行，每行给出L,R表示一组询问。

输出格式

输出共有Q行，每行一个整数，表示对应的询问的答案。

样例

样例输入

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

样例输出

9
8
8
16
16

回滚莫队的复习

注意几个要点

• 输入数据范围为1e9，但输入个数只有1e5，需用离散化预处理

• 什么时候考虑回滚莫队：当add（或del）能方便处理而del（或add）不能方便处理时，考虑用回滚
  （这样回滚只用处理add（或del））

• 输入时一定要初始化id

• 回滚莫队的排序：先按查询的l所属的块升序排，再按查询的r升序排

• l，r的初值设置一定要交叉（例如l=1，r=0），从而保证区间中的元素个数为0

• 求解答案时如果l与r在同一块内，直接暴力求最值

• 不在同一块内，先滚区间（把l和r滚到与问题区间相同），再采用回滚

• 通过memcpy和设的变量来暂时存储数组和答案（为回滚做准备）

• 每次求解答案时有关数组和变量都要清0
  （这里有一个小问题：用memset每次清空数组会T，但其实每次只需要把上一次用过的范围清空就好，时间复杂度要低点，我也不知道怎么证）
  具体如下：

while (i<j&&q[i].r<=right)//在同一块内直接暴力 
	{
		ans=0;
		for (int k=q[i-1].l;k<=q[i-1].r;k++) ch[a[k]]=0;
               //memset(ch,0,sizeof(ch));--------会T
		for (int k=q[i].l;k<=q[i].r;k++) add(a[k]);
		h[q[i].id]=ans;
		i++;
	} 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int sq,n,m,a[maxn],b[maxn],bl[maxn],l,r,ch[maxn],back[maxn];
ll ans,h[maxn];
struct pp{
	int l,r,id;
}q[maxn];
void dis()
{
	sort(b+1,b+1+n);
	int cnt=unique(b+1,b+1+n)-(b+1);
	for (int i=1;i<=n;i++)
	  {
	  	a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
	  	bl[i]=(i-1)/sq+1;
	  }
}
bool cmp(pp u,pp v)
{
	if (bl[u.l]!=bl[v.l]) return bl[u.l]<bl[v.l];
	return u.r<v.r;
}
void add(int x)
{
	ch[x]++;
	ans=max(ans,(ll)b[x]*ch[x]);
}
int main()
{
	n=read();m=read();
	for (int i=1;i<=n;i++) 
	  a[i]=b[i]=read();
	sq=sqrt(n);dis();//离散化 
	for (int i=1;i<=m;i++) 
	  q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	for (int i=1;i<=m;)
	  {
	  	int j=i;
	  	while (bl[q[j].l]==bl[q[i].l]&&j<=m) j++;
	  	int right=bl[q[i].l]*sq;
	  	while (i<j&&q[i].r<=right)//在同一块内直接暴力 
		  {
		  	ans=0;
			for (int k=q[i-1].l;k<=q[i-1].r;k++) ch[a[k]]=0;
		  	for (int k=q[i].l;k<=q[i].r;k++) add(a[k]);
		  	h[q[i].id]=ans;
			i++;
		   } 
		r=right;l=right+1;//此时询问的r一定大于right，询问的l一定小于等于right 
		ans=0;
		for (int k=q[i-1].l;k<=q[i-1].r;k++) ch[a[k]]=0; 
		while (i<j)
		  {
		  	while (q[i].r>r) add(a[++r]);
		  	ll tmp=ans;
		  	memcpy(back,ch,sizeof(back));
		  	while (q[i].l<l) add(a[--l]);
			h[q[i].id]=ans;
			//回滚
			ans=tmp;l=right+1;
			memcpy(ch,back,sizeof(ch));
			i++;
		  }
	  }
	for (int i=1;i<=m;i++) printf("%lld\n",h[i]);
	return 0;
 } 

完结撒花！φ(゜▽゜*)♪