生活随笔
收集整理的這篇文章主要介紹了
BZOJ 4241 分块
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
思路：
考慮分塊
f[i][j]表示從第i塊開頭到j(luò)的最大值
cnt[i][j]表示從第i塊開始到序列末尾j出現(xiàn)了多少次
邊角余料處理一下就好啦~
//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=
100050;
int n,q,Block,a[N],block[N],cpy[N],u;
int xx,yy,cnt[
333][N],top,stk[N],num[N];
typedef long long ll;ll f[
333][N],ans;
int main(){scanf("%d%d",&n,&q),Block=
sqrt(n);for(
int i=
1;i<=n;i++)scanf(
"%d",&a[i]),block[i]=(i-
1)/Block+
1,cpy[i]=
a[i];sort(cpy+
1,cpy+
1+n),u=unique(cpy+
1,cpy+
1+n)-cpy-
1;for(
int i=
1;i<=n;i++)a[i]=lower_bound(cpy+
1,cpy+
1+u,a[i])-
cpy;for(
int i=
1;i<=block[n];i++
){ll now=
0;for(
int j=lower_bound(block+
1,block+
1+n,i)-block;j<=n;j++
)cnt[i][a[j]]++,now=max(now,(ll)cnt[i][a[j]]*cpy[a[j]]),f[i][j]=
now;}while(q--
){scanf("%d%d",&xx,&yy),ans=f[block[xx]+
1][yy],top=
0;int temp=lower_bound(block+
1,block+
1+n,block[yy])-
block;for(
int i=temp;i<=yy;i++)num[a[i]]++,stk[++top]=
a[i];temp=lower_bound(block+
1,block+
1+n,block[xx]+
1)-
block;for(
int i=xx;i<temp;i++
){num[a[i]]++,ans=max(ans,(ll)(cnt[block[xx]+
1][a[i]]-cnt[block[yy]][a[i]]+num[a[i]])*
cpy[a[i]]);stk[++top]=
a[i];}temp=lower_bound(block+
1,block+
1+n,block[yy])-
block;for(
int i=temp;i<=yy;i++
)ans=max(ans,(ll)(cnt[block[xx]+
1][a[i]]-cnt[block[yy]][a[i]]+num[a[i]])*
cpy[a[i]]);for(
int i=
1;i<=top;i++)num[stk[i]]=
0;printf("%lld\n",ans);}
} ?
?
轉(zhuǎn)載于:https://www.cnblogs.com/SiriusRen/p/6532021.html
總結(jié)
以上是生活随笔為你收集整理的BZOJ 4241 分块的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
