历史研究(回滚莫队)
问题 C: 历史研究
时间限制: 1 Sec 内存限制: 128 MB
提交: 61 解决: 2
[提交] [状态] [命题人:admin]
题目描述
IOI 国历史研究的大牛——JOI 教授,最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活,开始着手调查日记中记载的事件。
日记中记录了连续N天发生的事件,每天发生一件事件。
事件有种类之分。第i天发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。
JOI 教授决定用如下的方法分析这些日记:
1.选择日记中连续的一些天作为分析的时间段;
2.事件种类t的重要度为t×(这段时间内重要度为t的事件数);
3.计算出所有事件种类的重要度,输出其中的最大值。
请制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。
输入
第一行两个空格分隔的整数N和Q,表示日记一共记录了N天,询问有Q次。
接下来一行N个空格分隔的整数X1,...Xn,Xi表示第i天发生的事件的种类。
接下来Q行,第i行有两个空格分隔整数Ai和Bi,表示第i次询问的区间为[Ai,Bi]。
输出
输出Q行,第i行一个整数,表示第i次询问的最大重要度。
样例输入
复制样例数据
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
样例输出
9
8
8
16
16
提示
想着没啥思路就写莫队,然后一直变换着t和wa,最后发现自己缺个知识点、、、
回滚莫队,一开始没看懂,后来发现这东西还真是名副其实的在滚、、
考虑一般莫队,复杂度是,但是这题要求区间最值,那,要维护区间最值的话,
只能是再套个其他的数据结构,复杂度就变成了,没法再优化,
区间最值问题要维护只能是级别的
这时候我们注意到,如果区间一直扩张的话,最值其实可以取到,
但是如果区间在缩小的话,那就没办法了,所以,如何避免区间缩小这种情况呢
由分块的sort,想到,对于l在同一个块内的r,其实是不断递增的,
如果不考虑l的话,那再好不过了(l定住,r不断向右递增,所以区间是扩大的)
现在考虑怎么消除l的影响,解决办法就是-------------------->
把l设置到下一块的开始,每次滚到应该在的位置,得到答案后,再滚回去(下一块的开始位置)
对于l,r在同一块内的,直接暴力for得到答案,而不必回滚了
这样就是回滚莫队了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
map<ll,int> vis;
int a[maxn],n,q,base;
int val[maxn],cnt[maxn],block[maxn];
struct node{
int l,r,id;
bool operator < (const node &b)const{
return block[l]^block[b.l]?block[l]<block[b.l]:r<b.r;
}
}Q[maxn];
ll out[maxn],ans;
ll Andrew(int l,int r,ll ans = 0){
static int vis[maxn];
for(int i=l;i<=r;i++)vis[a[i]] = 0;
for(int i=l;i<=r;i++)vis[a[i]]++,ans = max(ans,1ll*vis[a[i]]*val[i]);
return ans;
}
void Add(int x){
cnt[a[x]]++;
ans = max(ans,1ll*cnt[a[x]]*val[x]);
}
int main(){
scanf("%d%d",&n,&q);
base = sqrt(n);
for(int i=1,cnt = 0;i<=n;i++){
scanf("%d",&a[i]);
val[i] = a[i];
if(!vis.count(a[i])){
vis[a[i]] = ++cnt;
a[i] = vis[a[i]];
}
else
a[i] = vis[a[i]];
block[i] = (i-1)/base+1;
}
for(int i=1;i<=q;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id = i;
sort(Q+1,Q+1+q);
int l = 1,r = 0;
ll tans = 0;
for(int i=1,id=1;i<=q;id++){
int R = min(id*base+1,n),ql = R+1,qr = ql-1;
ans = 0;
memset(cnt,0,sizeof cnt);
while(i<=q&&block[Q[i].l] == id){
if(block[Q[i].l] == block[Q[i].r]){
out[Q[i].id] = Andrew(Q[i].l,Q[i].r);
i++;
continue;
}
while(qr<Q[i].r)Add(++qr);//r
ll cur = ans;
while(ql>Q[i].l)Add(--ql);//滚来~~
out[Q[i].id] = ans;
while(ql<R+1)cnt[a[ql]]--,ql++;//滚去、、
ans = cur;
i++;
}
}
for(int i=1;i<=q;i++)printf("%lld\n",out[i]);
return 0;
}