【bzoj 4241】歴史研究ブロック
2556 ワード
PoPoQQQ大神の題解:
http://blog.csdn.net/popoqqq/article/details/47809173
最初は自分でチームを作る方法を考えていたが、複雑さが間違っていたことに気づき、ネット上でオンラインのやり方を見つけた.
ブロック化後、mx[i][j]がiブロック目からjブロック目までの答えを表し、cnt[i][j]が前iブロック数jの個数を表し、先離散化に注意する.
そして検索するたびに、ブロック外の部分を単独で処理し、ブロック内の部分に直接答えを書けばいいです.
http://blog.csdn.net/popoqqq/article/details/47809173
最初は自分でチームを作る方法を考えていたが、複雑さが間違っていたことに気づき、ネット上でオンラインのやり方を見つけた.
ブロック化後、mx[i][j]がiブロック目からjブロック目までの答えを表し、cnt[i][j]が前iブロック数jの個数を表し、先離散化に注意する.
そして検索するたびに、ブロック外の部分を単独で処理し、ブロック内の部分に直接答えを書けばいいです.
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#define maxn 100100
using namespace std;
struct yts1
{
int x,id;
}a[maxn];
int b[maxn],bel[maxn];
int n,m,block,tot;
int L[400],R[400];
long long mx[400][400];
int cnt[400][maxn];
long long ans;
int num[maxn];
int st[maxn],top;
bool cmp(yts1 x,yts1 y)
{
return x.x<y.x;
}
long long calc(int l,int r)
{
long long ans=0;
top=0;
for (int i=l;i<=r;i++)
{
if (!num[b[i]]) st[++top]=b[i];
num[b[i]]++;
ans=max(ans,(long long)num[b[i]]*a[b[i]].x);
}
while (top) num[st[top--]]=0;
return ans;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i].x);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
b[a[1].id]=1;
for (int i=2;i<=n;i++) if (a[i].x==a[i-1].x) b[a[i].id]=b[a[i-1].id]; else b[a[i].id]=i;
block=sqrt(n);tot=(n-1)/block+1;
for (int i=1;i<=n;i++)
{
bel[i]=(i-1)/block+1;
if (!L[bel[i]]) L[bel[i]]=i;
R[bel[i]]=i;
}
for (int i=1;i<=n;i++) cnt[bel[i]][b[i]]++;
for (int i=2;i<=tot;i++)
for (int j=1;j<=n;j++)
cnt[i][j]+=cnt[i-1][j];
for (int i=1;i<=tot;i++)
{
long long ans=0;
memset(num,0,sizeof(num));
for (int j=L[i];j<=n;j++)
{
num[b[j]]++;
ans=max(ans,(long long)num[b[j]]*a[b[j]].x);
if (j==R[bel[j]]) mx[i][bel[j]]=ans;
}
}
memset(num,0,sizeof(num));
for (int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
ans=0;
if (bel[l]==bel[r]) printf("%lld
",calc(l,r));
else
{
ans=mx[bel[l]+1][bel[r]-1];
top=0;
for (int i=l;i<=R[bel[l]];i++)
if (!num[b[i]]) st[++top]=b[i],num[b[i]]=cnt[bel[r]-1][b[i]]-cnt[bel[l]][b[i]];
for (int i=L[bel[r]];i<=r;i++)
if (!num[b[i]]) st[++top]=b[i],num[b[i]]=cnt[bel[r]-1][b[i]]-cnt[bel[l]][b[i]];
for (int i=l;i<=R[bel[l]];i++) num[b[i]]++;
for (int i=L[bel[r]];i<=r;i++) num[b[i]]++;
while (top)
{
ans=max(ans,(long long)a[st[top]].x*num[st[top]]);
num[st[top--]]=0;
}
printf("%lld
",ans);
}
}
return 0;
}