ECNU 3480. 没用的函数 [暴力]

题意：给你长度为n的序列，求最大的【L，R】的f(l,r):

题解：由于一个数的GCD最多只有logn个，所以对于当前的数，我们只需要维护最多32个GCD区间，并且这些区间是单调的，所以我们只需要找对于一个GCD取到的范围内最小的前缀和，就可以更新最大值了。

需要注意的是对于区间的GCD，大部分情况是长后缀的GCD要小于短后缀的GCD，除0以外，例如【3.6,12,0】区间，后缀GCD为 【3,6,12,0】 ，没有单调性，但由于0对答案不影响，所以直接特判就可以了。

AC代码：

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<set>
#include<stdlib.h>
#define N 1000005
using namespace std;
typedef long long ll;
ll sum[N];
ll rmq[N][25];
ll a[N];
ll mm[N];//最大的小于等于i的2^mm[i]
void initRMQ(ll n)
{
mm[0]=-1;
for(ll i=1;i<=n;i++)
{
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
rmq[i][0]=sum[i];
}
for(ll j=1;j<=mm[n];j++)
for(ll i=1;i+(1<<j)-1<=n;i++)
rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
}
ll RMQ(ll x,ll y)
{
ll k=mm[y-x+1];
return min(rmq[x][k],rmq[y-(1<<k)+1][k]);
}
set<ll>st,st2;
set<ll>::iterator it;
ll g[N];
int main()
{
ll n;
scanf("%lld",&n);
ll ans=0;
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]),sum[i+1]=sum[i]+a[i],ans=min(ans,a[i]*abs(a[i]));
initRMQ(n+1);
for(ll i=1;i<=n;i++)
{
if(a[i]==0)//0的存在会影响区间的单调性
{
ans=max(ans,0ll);
continue;
}
ll last=0;
for(it=st.begin();it!=st.end();it++)
{
ll now=*it;
ll gc=abs(__gcd(now,a[i]));
g[gc]=max(g[gc],g[now]);
st2.insert(gc);
}
st.clear();
for(it=st2.begin();it!=st2.end();it++)st.insert(*it);
st2.clear();
for(it=st.begin();it!=st.end();it++)
{
ll now=*it;
ans=max(ans,(sum[i+1]-RMQ(last+1,g[now]))*now);
last=g[now];
}
st.insert(abs(a[i]));
g[abs(a[i])]=max(g[abs(a[i])],i);
ans=max(ans,(sum[i+1]-RMQ(last+1,i))*abs(a[i]));
}
printf("%lldn",ans);
}

最后

以上就是结实花生为你收集整理的ECNU 3480. 没用的函数 [暴力]的全部内容，希望文章能够帮你解决ECNU 3480. 没用的函数 [暴力]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。