「题解」「JOISC2014」历史研究 Historical Research

JOISC2014 Day1 T3。回滚莫队例题。

题目链接：JOISC2014 D1T3、LOJ 2874。

未完待续

题目

题目描述

IOI 国历史研究的大牛——JOI 教授，最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活，开始着手调查日记中记载的事件。
日记中记录了连续  天发生的事件，每天发生一件事件。
事件有种类之分。第 \(N\) 天发生的事件的种类用一个整数 \(X _ i\) 表示，\(X _ i\) 越大，事件的规模就越大。
JOI 教授决定用如下的方法分析这些日记：

1. 选择日记中连续的一些天作为分析的时间段；
2. 事件种类 \(t\) 的重要度为 \(t\) 与这段时间内重要度为 \(t\) 的事件数的乘积；
3. 计算出所有事件种类的重要度，输出其中的最大值。

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

数据范围

子任务编号	分值	附加条件
1	5	\(N,Q\leq 100\)
2	10	\(N,Q\leq 5000\)
3	25	没有 \(i,j(1\leq i\leq Q,1\leq j\leq Q,i\ne j)\)，使得 \(A _ i\leq A _ j\leq B _ j\leq B _ i\)。
4	60	无

时空限制

题解

思路

回滚莫队板子题。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e5+5;
const int MAXSQRTN=317+5; //\sqrt{n} 的最大值
const int MAXQ=1e5+5;

int n,q;
int a[MAXN];
int pos[MAXN]; //所在块的编号
int L[MAXSQRTN],R[MAXSQRTN]; //各个块的左右端点

struct querys{
	int l,r,id;
	inline querys(reg int l=0,reg int r=0,reg int id=0):l(l),r(r),id(id){
		return;
	}
	inline bool operator<(const querys& a)const{ //排序
		if(pos[l]!=pos[a.l])
			return l<a.l;
		return r<a.r;
	}
};

querys Q[MAXQ];

inline void build(void){ //初始化块信息
	reg int size=sqrt(n);
	reg int tot=n/size;
	for(reg int i=1;i<=tot;++i){
		L[i]=(i-1)*size+1;
		R[i]=i*size;
	}
	if(R[tot]<n){
		++tot;
		R[tot]=n;
		L[tot]=R[tot-1]+1;
	}
	for(reg int i=1;i<=tot;++i)
		for(reg int j=L[i];j<=R[i];++j)
			pos[j]=i;
	return;
}

vector<int> V;
int __cnt[MAXN]; //该数组用于块内暴力求解
int T[MAXN]; //桶
ll ans[MAXQ];

inline void add(reg int x,reg ll &ans){
	++T[x];
	ans=max(ans,1ll*V[x-1]*T[x]); //统计答案
	return;
}

inline void del(reg int x){
	--T[x];
	return;
}

int main(void){
	n=read(),q=read();
	build();
	for(reg int i=1;i<=n;++i){
		a[i]=read();
		V.push_back(a[i]);
	}
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	for(reg int i=1;i<=n;++i)
		a[i]=lower_bound(V.begin(),V.end(),a[i])-V.begin()+1;
	for(reg int i=1;i<=q;++i){
		static int l,r;
		l=read(),r=read();
		Q[i]=querys(l,r,i);
	}
	sort(Q+1,Q+q+1);
	reg int l=1,r=0;
	ll Ans=0,tmp;
	int LastB=0;
	for(reg int i=1;i<=q;++i){
		if(pos[Q[i].l]==pos[Q[i].r]){ //块内暴力
			ll Ans=0;
			for(reg int j=Q[i].l;j<=Q[i].r;++j){
				++__cnt[a[j]];
				Ans=max(Ans,1ll*V[a[j]-1]*__cnt[a[j]]);
			}
			for(reg int j=Q[i].l;j<=Q[i].r;++j)
				--__cnt[a[j]];
			ans[Q[i].id]=Ans;
			continue;
		}
		if(pos[Q[i].l]!=LastB){ //块编号不同，删除信息
			while(r>R[pos[Q[i].l]])
				del(a[r--]);
			while(l<R[pos[Q[i].l]]+1)
				del(a[l++]);
			Ans=0;
			LastB=pos[Q[i].l];
		}
		while(r<Q[i].r)
			add(a[++r],Ans);
		reg int __l=l;
		tmp=Ans;
		while(__l>Q[i].l)
			add(a[--__l],tmp);
		ans[Q[i].id]=tmp;
		while(__l<l) //回滚
			del(a[__l++]);
	}
	for(reg int i=1;i<=q;++i)
		printf("%lld\n",ans[i]);
	return 0;
}