传送门
一口大锅（
斜率的确是有单调性 并且可以进行凸优化的 明明是证出来的 为什么自己就不相信呢（
我们发现对于当前点作为扩展的右端点 那么他前面至多有20个点会影响到这一段区间的或值 我们可以预处理记录出来这些节点的位置 很明显 答案随着右端点越向右是非严格递增的 所以直接取最右端的节点即可
我们列出方程 ![f[i][k]= max(f[j][k-1]+ x ,f[i][k])](https://img-blog.csdnimg.cn/20181220085040756)
因为答案随着段数增加非严格递增 分析一波段数少的可以记录答案就结束啦
有关于单调性的证明如下。
我们可以将原始的问题转化成 我们每次选择两个位置进行合并 代价为这两段的&
我们需要进行n-k次合并 并且要最小化&
这个显然是有单调性的 因为 我们少合并一次就可以减少代价 并且这个代价必定是单调的 因为 最开始的&只是小段的& 随着合并的段数长度增加 这一段的或值显然是非严格递增的 那么&的值显然也是非严格递增的
这样的话就证完了。
一个小问题 ： log运算非常慢（ 会因为这玩意T掉 所以那nlg个区间或值预处理出来比较好
附代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 2002122500
#define ll long long
using namespace std;
int a[100010],p[100010][21],fr[21],l[21],lg[100010];
ll f[100010],tot;int qaq[100010][21];int g[100010];
int n,k;
struct ST
{
int f[100010][18];
void build()
{
for(int i=1;i<=n;i++) f[i][0]=a[i];
for(int i=1;i<18;i++)
for(int j=1;j+(1<<i-1)<=n;j++)
f[j][i]=f[j][i-1]|f[j+(1<<i-1)][i-1];
}
int query(int l,int r)
{
int k=lg[r-l+1];
return f[l][k]|f[r-(1<<k)+1][k];
}
}st;
void find(int x)
{
p[x][0]=x;qaq[x][0]=a[x];int cnt=0;
for(int i=0;i<=20;i++)
if((!(a[x]&(1<<i)))&&fr[i]) p[x][++cnt]=fr[i],qaq[x][cnt]=st.query(fr[i],x);
p[x][++cnt]=1;qaq[x][cnt]=st.query(1,x);
}
bool check(int mid)
{
for(int i=1;i<=n;i++) f[i]=-inf,g[i]=inf;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=20&&p[i][j];j++)
{
//printf("%d %d %d
",i,j,p[i][j]);
ll tmp=qaq[i][j]+mid+f[p[i][j]-1];
if(tmp>f[i]||(tmp==f[i] && g[p[i][j]-1] +1 <g[i]))
g[i]=g[p[i][j]-1]+1,f[i]=tmp;
}
}
//printf("%d %d %d
",f[n],g[n],mid);
return g[n]<=k;
}
int main()
{
//freopen("orSimple.in","r",stdin);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),tot+=a[i];
st.build();l[0]=1;int i;
for(i=1;i<18;i++)
{
l[i]=(1<<i);//printf("%d %d
",i,l[i]);
if(l[i]>=n) break;
for(int j=l[i-1];j<l[i];j++) lg[j]=i-1;
}
for(int j=l[i-1];j<=n;j++) lg[j]=i-1;
int l,r;
for(int i=1;i<=n;i++)
{
find(i);
for(int j=0;j<=20;j++)
if(a[i]&(1<<j)) fr[j]=i;
}
l=-inf;r=0;ll ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) l=mid+1,ans=f[n]-(ll)mid*k;
else r=mid-1;
}
printf("%lld
",ans);
return 0;
}
/**
21 9
3 4 1 4 8 10 9 38 83 3 28 4 2 1 14 41 31 41 39 5 2
*/