这一题我还是不会做QAQ 一开始想了一想，好像可以上莫队 嗯，怎么维护修改呢 我们可以对数值进行分块啊，那么每次就只需要 n√ 的时间就可以维护好了 (⊙v⊙)嗯，看起来是一个十分优越的做法 时间复杂度就是莫队* n√ ，也就是 n√∗nn√ ,大概是 n2 这就跟暴力没什么区别嘛，就名字好听了一点
于是继续想。。 什么都没想出来。。 于是。。。
看了两眼，又会了
大概就是维护 前i个块数字为j出现了多少次以及第i个块到第j个块的答案 如果你是零碎的地方，你就暴力算 零碎的答案是 n√ 的 至于为什么是对的。。我觉得这个很好理解就懒得写了 感觉看代码应该很快能看懂
#include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const LL N=100005; LL n,q; struct qq { LL x,id; }s[N]; LL b[N];//离散后的这个值在原值里面是多少 LL a[N];//离散后的序列 bool cmp (qq a,qq b){return a.x<b.x;} LL L[N],R[N],belong[N],cnt; void prepare ()//预处理分块 { LL nn=sqrt(n);L[1]=1;cnt=1; for (LL u=1;u<=n;u++) { belong[u]=cnt; if (u%nn==0) { R[cnt]=u; cnt++; L[cnt]=u+1; } } cnt=belong[n]; R[cnt]=n; return ; } LL cnt1; void init () { scanf("%lld%lld",&n,&q); for (LL u=1;u<=n;u++) {scanf("%lld",&s[u].x);s[u].id=u;} sort(s+1,s+1+n,cmp); cnt1=1;a[s[1].id]=1;b[1]=s[1].x; for (LL u=2;u<=n;u++) { if (s[u].x!=s[u-1].x) cnt1++; a[s[u].id]=cnt1;b[cnt1]=s[u].x; } } LL lalal[350][N];//前i个块数字为j出现了多少次 LL ans[350][350];//第i个块到第j个块的答案 LL ooo[N];//某个数字出现了多少次 LL mymax (LL x,LL y) {return x>y?x:y;} void ready () { for (LL u=1;u<=n;u++) lalal[belong[u]][a[u]]++; for (LL u=2;u<=cnt;u++) for (LL i=1;i<=cnt1;i++) lalal[u][i]+=lalal[u-1][i]; for (LL u=1;u<=cnt;u++) { memset(ooo,0,sizeof(ooo)); LL Ans=0; for (LL i=L[u];i<=n;i++) { ooo[a[i]]++; Ans=mymax(Ans,b[a[i]]*ooo[a[i]]); if (belong[i]!=belong[i+1]) ans[u][belong[i]]=Ans; } } } void solve () { memset(ooo,0,sizeof(ooo)); while (q--) { LL l,r; scanf("%lld%lld",&l,&r); if (belong[l]==belong[r]) { LL Ans=0; for (LL u=l;u<=r;u++) ooo[a[u]]++; for (LL u=l;u<=r;u++) Ans=mymax(Ans,ooo[a[u]]*b[a[u]]),ooo[a[u]]=0; printf("%lld\n",Ans); } else { LL Ans=ans[belong[l]+1][belong[r]-1]; for (LL u=l;u<=R[belong[l]];u++)ooo[a[u]]++; for (LL u=L[belong[r]];u<=r;u++)ooo[a[u]]++; for (LL u=l;u<=R[belong[l]];u++) { Ans=mymax(Ans,b[a[u]]*(lalal[belong[r]-1][a[u]]-lalal[belong[l]][a[u]]+ooo[a[u]])); ooo[a[u]]=0; } for (LL u=L[belong[r]];u<=r;u++) { Ans=mymax(Ans,b[a[u]]*(lalal[belong[r]-1][a[u]]-lalal[belong[l]][a[u]]+ooo[a[u]])); ooo[a[u]]=0; } printf("%lld\n",Ans); } } } int main() { init(); prepare(); ready(); solve(); return 0; }不知道为什么，居然跑了80s,这已经不是暴力了好不好QAQ
