[CSAcademy]Or Problem

题目大意：

一个长度为\(n(n\le2\times10^5)\)的序列\(A(0\le A_i<2^{20})\)，将其分为恰好\(m\)个连续段，设每一段的代价为这一段数字的或，总代价为每一段代价和。求最小代价和。

思路：

一个普通的DP思路是，对于每个数\(A_i\)，枚举每一位，找到上一个在这一位上为\(1\)的数\(A_k\)，\(A_{k+1\sim i}\)为最后一段。转移方程为\(f[i][j]=\max\{f[k][j-1]+\vee_{\ell=k+1}^i A_{\ell}\}\)。

使用带权二分可以去掉\(m\)段的状态。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}typedef long long int64;const int N=2e5+1,logN=18,logA=20;int n,st[N][logN],p[logA],g[N];int64 f[N];inline int lg2(const float &x) {    return ((unsigned&)x>>23&255)-127;}inline int calc(const int &l,const int &r) {    const int k=lg2(r-l+1);    return st[l][k]|st[r-(1<
        
         >j&1) p[j]=i;            if(!p[j]) continue;            const int64 tmp=f[p[j]-1]+calc(p[j],i)-c;            if(f[i]
         
          >1; solve(mid); if(g[n]>=m) { l=mid+1; ans=f[n]+1ll*m*mid; } else { r=mid-1; } } printf("%lld\n",ans); return 0;}