CSAcademy Or Problem

傳送門

一口大鍋（

斜率的確是有單調性 并且可以進行凸優化的 明明是證出來的 為什么自己就不相信呢（

我們發現對于當前點作為擴展的右端點 那么他前面至多有20個點會影響到這一段區間的或值 我們可以預處理記錄出來這些節點的位置 很明顯 答案隨著右端點越向右是非嚴格遞增的 所以直接取最右端的節點即可

我們列出方程?狀態是nk轉移log 顯然可以進行凸優化

因為答案隨著段數增加非嚴格遞增 分析一波段數少的可以記錄答案就結束啦

?

有關于單調性的證明如下。

我們可以將原始的問題轉化成 我們每次選擇兩個位置進行合并 代價為這兩段的&

我們需要進行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\n",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\n",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\n",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\n",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
*/

?