歴史の研究 题解 回滚莫队

Demoe · 2020-08-21 20:14:24 · 题解

题目传送门

谷 \text{AT} 评测还没修好，跑到 \text{LOJ} 上交了一发，AC 记录。

题意

• 给定一个序列，多次询问区间 [l,r] 中 A \times T_A 的最大值。（T_A 表示 A 在区间中出现的次数。）

Sol

分析题目，可离线，插入方便删除难。

显然回滚莫队裸模板，甚至比模板题好写。

增量时每次维护 T_A，并不断更新。

每次增量复杂度 O(1)，整体复杂度 O((n+m)\sqrt n)。

对于本题，每次清空时只需最后将右端点滚回当前左端点块的右端点并沿途更新 T_A 即可。

注意点

全部开 \text{int} 会爆 0。（例 10^5 个 10^9 ）

全部开 \text{long long} 即可。

不卡常，常数巨大选手可过。

代码。

/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
ll n,m,a[N],b[N],len,l,r,sum,cnt[N],ans[N],lsh[N],qaq,qwq;
struct Question{ll l,r,id,pos;}q[N];
template <typename T> void rd(T &x){
    ll fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(ll x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}
bool cmp(Question x,Question y){
    if(x.pos!=y.pos) return x.pos<y.pos;
    return x.r<y.r;
}
ll solve(ll l,ll r){
    ll awa[N]={0},tot=0;
    for(ll i=l;i<=r;++i){awa[a[i]]++;tot=max(tot,awa[a[i]]*b[a[i]]);}
    return tot;
}
void update(ll x){cnt[a[x]]++;sum=max(sum,cnt[a[x]]*b[a[x]]);}
void erase(ll x){cnt[a[x]]--;}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);len=(ll)sqrt(n);
    for(ll i=1;i<=n;++i) rd(a[i]),lsh[i]=a[i];
    for(ll i=1;i<=m;++i) rd(q[i].l),rd(q[i].r),q[i].id=i,q[i].pos=(q[i].l-1)/len+1;
    sort(lsh+1,lsh+n+1);
    qaq=unique(lsh+1,lsh+n+1)-lsh-1;
    for(ll i=1;i<=n;++i) b[lower_bound(lsh+1,lsh+qaq+1,a[i])-lsh]=a[i],a[i]=lower_bound(lsh+1,lsh+qaq+1,a[i])-lsh;
    sort(q+1,q+m+1,cmp);
    for(ll i=1,j=1;j<=(n-1)/len+1;++j){
        ll br=min(j*len,n);l=br+1,r=br,sum=0;
        while(q[i].pos==j){
            if(q[i].r<=br){
                ans[q[i].id]=solve(q[i].l,q[i].r);++i;
                continue;
            }
            while(r<q[i].r) ++r,update(r);
            qwq=sum;
            while(l>q[i].l) --l,update(l);
            ans[q[i].id]=sum;
            while(l<=br) erase(l),l++;
            sum=qwq;++i;
        }
        while(r>br) erase(r),r--;
    }
    for(ll i=1;i<=m;++i) wr(ans[i]),puts("");
    return 0;
}