链接

　　http://www.lydsy.com/JudgeOnline/problem.php?id=4241

题解

　　是我 SB ，是我 SB 。 　　一开始找区间里一个数出现了多少次的时候我用了 vector +二分， TLE 了也很正常。 　　分块+预处理的操作很显然，问题是处理两边多出来的那些数的时候怎样快速统计这些数出现了多少次。 　　这个我以前学的是用 N 个vector存下每个数的出现位置，用的时候二分下就行了。但是这道题那样做会 TLE ，题解里说的是，可以对块做个前缀和， cnt[i][j] 表示前 i 个块里j的出现次数。 　　时间复杂度 O(NN−−√)

代码

//分块 #include <cstdio> #include <algorithm> #include <cmath> #define maxn 100010 #define ll long long using namespace std; int N, M, a[maxn], tmp[maxn], size, ndtot, pos[maxn], cnt[320][maxn], tong[maxn]; ll imp[maxn], f[2000][2000]; int read(int x=0) { char c=getchar(); while(c<48 or c>57)c=getchar(); while(c>=48 and c<=57)x=(x<<1)+(x<<3)+c-48, c=getchar(); return x; } void init() { int i, j; ll ans; N=read(), M=read(); for(i=1;i<=N;i++)tmp[i]=a[i]=read(); sort(tmp+1,tmp+N+1); for(i=1;i<=N;i++)a[i]=lower_bound(tmp+1,tmp+N+1,a[i])-tmp; size=sqrt(N); for(i=1;i<=N;i++)pos[i]=i/size; for(i=1;i<=N;i++)cnt[pos[i]][a[i]]++; for(i=1;i<=pos[N];i++)for(j=1;j<=N;j++)cnt[i][j]+=cnt[i-1][j]; for(i=size;i<=N;i+=size) { for(j=1;j<=N;j++)imp[j]=0; ans=0; for(j=i;pos[j]!=pos[N];j++) { imp[a[j]]+=tmp[a[j]]; ans=max(ans,imp[a[j]]); if(pos[j+1]!=pos[j])f[pos[i]][pos[j]]=ans; } } } void gao(int l, int r) { int i, bl=pos[l]+1, br=pos[r]-1; ll ans=f[bl][br]; for(i=l;i<=r and pos[i]==pos[l];i++) { if(!tong[a[i]] and bl<=br) tong[a[i]]=cnt[br][a[i]]-cnt[bl-1][a[i]]; tong[a[i]]++; } if(pos[l]^pos[r])for(i=r;pos[i]==pos[r];i--) { if(!tong[a[i]] and bl<=br) tong[a[i]]=cnt[br][a[i]]-cnt[bl-1][a[i]]; tong[a[i]]++; } for(i=l;i<=r and pos[i]==pos[l];i++) ans=max(ans,(ll)tong[a[i]]*tmp[a[i]]), tong[a[i]]=0; if(pos[l]^pos[r])for(i=r;pos[i]==pos[r];i--) ans=max(ans,(ll)tong[a[i]]*tmp[a[i]]), tong[a[i]]=0; printf("%lld\n",ans); } int main() { int l, r; init(); while(M--) { l=read(), r=read(); gao(l,r); } return 0; }