BZOJ4241: 历史研究

题解:

这题一看一些基本的方法都是不能做的了,再看看时限,果断觉得是分块.

然后觉得带一个$log$肯定是死活过不去的.

然后我们苦思一下不带$log$的算法.

首先分成$O(\sqrt{n})$块,然后$O(n\sqrt{n})$里面算出任意两块之间的答案.

然后对于剩下部分,我们用类似于暴力计算的方法一个一个加入当前集合并维护答案就行了.

这个可以通过事先记录前缀若干个块每个元素各有多少来高效进行.

于是做到了空间时间复杂度均为$O(n\sqrt{n})$.

代码:

#include<cmath>
#include<cstdio>
#include<cctype>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
 
#define N 100010
int a[N],b[N],_a[N];
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int pre[351][N];
int in[N];
 
ll f[351][351];
int be[351],en[351];
int temp[N],t[N],tclock;
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n=getint(),q=getint();
    int i,j,k;
    for(i=1;i<=n;++i)
        b[i]=a[i]=getint();
    sort(b+1,b+n+1);
    int _n=unique(b+1,b+n+1)-b-1;
    for(i=1;i<=n;++i)
        _a[i]=lower_bound(b+1,b+_n+1,a[i])-b;
     
    int m=int(sqrt(n));
    int num=n/m;
    for(i=1;i<=num;++i){
        memcpy(pre[i],pre[i-1],sizeof pre[i]);
        be[i]=(i-1)*m+1;
        en[i]=i*m;
        for(j=be[i];j<=en[i];++j){
            in[j]=i;
            ++pre[i][_a[j]];
        }
    }
    if(n%m){
        ++num;
        be[num]=(num-1)*m+1;
        en[num]=n;
        memcpy(pre[num],pre[num-1],sizeof pre[num]);
        for(j=be[num];j<=en[num];++j){
            in[j]=num;
            ++pre[num][_a[j]];
        }
    }
     
    ll ans;
    for(i=1;i<=num;++i){
        k=be[i];
        memset(temp,0,sizeof temp);
        ans=0;
        for(j=i;j<=num;++j){
            while(k<=en[j])
                ans=max(ans,(ll)a[k]*(++temp[_a[k]])),k++;
            f[i][j]=ans;
        }
    }
     
    int l,r;
    while(q--){
        l=getint();
        r=getint();
        if(in[r]-in[l]<=1){
            ++tclock;
            ans=0;
            for(i=l;i<=r;++i){
                temp[_a[i]]=(t[_a[i]]==tclock)?temp[_a[i]]+1:1;
                t[_a[i]]=tclock;
                ans=max(ans,(ll)a[i]*temp[_a[i]]);
            }
            printf("%lld\n",ans);
        }
        else{
            ++tclock;
            ans=f[in[l]+1][in[r]-1];
            for(i=l;i<=en[in[l]];++i){
                temp[_a[i]]=(t[_a[i]]==tclock)?temp[_a[i]]+1:pre[in[r]-1][_a[i]]-pre[in[l]][_a[i]]+1;
                t[_a[i]]=tclock;
                ans=max(ans,(ll)a[i]*temp[_a[i]]);
            }
            for(i=be[in[r]];i<=r;++i){
                temp[_a[i]]=(t[_a[i]]==tclock)?temp[_a[i]]+1:pre[in[r]-1][_a[i]]-pre[in[l]][_a[i]]+1;
                t[_a[i]]=tclock;
                ans=max(ans,(ll)a[i]*temp[_a[i]]);
            }
            printf("%lld\n",ans);
        }
    }
     
    return 0;
}