F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4241 >> 和某博客写的差不多,为什么错了
LMB @ 2018-08-25 16:27:43
[ Quote ] [ Edit ] [ Delete ] 1#
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN=int(1e5)+111;

int cnt[MAXN],blo[MAXN],block,n,m,a[MAXN],v[MAXN],newn,maxblock,qnum=1;
ll ans=0;

struct Query{
int l,r,id;
ll ans;
}q[MAXN];

inline bool cmp1(Query a,Query b){
return blo[a.l]==blo[b.l]?a.r<b.r:a.l<b.l;
}

inline bool cmp2(Query a,Query b){
return a.id<b.id;
}

inline int ID(int x){
return lower_bound(v+1,v+1+newn,x)-v;
}

inline void add(int pos){
++cnt[ID(a[pos])];
ans=max(ans,1ll*(++cnt[ID(a[pos])])*a[pos]);
}

inline void roll(int pos){
--cnt[ID(a[pos])];
}

inline ll query(int l,int r){
int cnt2[MAXN];
ll ret=0;
for (register int i=l;i<=r;i++)
cnt2[ID(a[i])]=0;
for (register int i=l;i<=r;i++){
ret=max(ret,1ll*(++cnt2[ID(a[i])])*a[i]);
}
return ret;
}

inline int sol(int qnum,int blockid){
int L=min(block*blockid,n)+1;
register int i,l=L,r=L-1;
for (register int j=1;j<=n;j++) cnt[j]=0;
for (i=qnum;blo[q[i].l]==blockid;i++){
if (blo[q[i].l]==blo[q[i].r]){
q[i].ans=query(q[i].l,q[i].r);
continue;
}
while (r<q[i].r) add(++r);
ll tmp=ans;
while (l>q[i].l) add(--l);
q[i].ans=ans;
while (l<L) roll(l++);
ans=tmp;
}
return i;
}

inline int read(){
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)){
if (ch=='-') f=-1;
ch=getchar();
}
while (isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}

int main(){
n=read(),m=read(),block=sqrt(n);
for (register int i=1;i<=n;i++){
v[i]=a[i]=read();
blo[i]=(i-1)/block+1;
}
maxblock=blo[n];
sort(v+1,v+1+n);
newn=unique(v+1,v+1+n)-(v+1);
for (register int i=1;i<=m;i++){
q[i].l=read(),q[i].r=read();
q[i].id=i;
}
sort(q+1,q+1+m,cmp1);
for (register int i=1;i<=maxblock;i++){
qnum=sol(qnum,i);
}
sort(q+1,q+1+m,cmp2);
for (register int i=1;i<=m;i++)
printf("%lld\n",q[i].ans);
return 0;
}
LMB @ 2018-08-25 16:27:56
[ Quote ] [ Edit ] [ Delete ] 2#
萌新求帮助QAQ
[Top] [Previous Page] [Next Page]

HOME Back