潍坊 网站建设,茶网站建设,如何做自己网站的访问记录,给网站做公正需要带什么传送门 一口大锅#xff08; 斜率的确是有单调性 并且可以进行凸优化的 明明是证出来的 为什么自己就不相信呢#xff08; 我们发现对于当前点作为扩展的右端点 那么他前面至多有20个点会影响到这一段区间的或值 我们可以预处理记录出来这些节点的位置 很明显 答案随着右端点…传送门 一口大锅 斜率的确是有单调性 并且可以进行凸优化的 明明是证出来的 为什么自己就不相信呢 我们发现对于当前点作为扩展的右端点 那么他前面至多有20个点会影响到这一段区间的或值 我们可以预处理记录出来这些节点的位置 很明显 答案随着右端点越向右是非严格递增的 所以直接取最右端的节点即可 我们列出方程 状态是nk转移log 显然可以进行凸优化 因为答案随着段数增加非严格递增 分析一波段数少的可以记录答案就结束啦 有关于单调性的证明如下。 我们可以将原始的问题转化成 我们每次选择两个位置进行合并 代价为这两段的 我们需要进行n-k次合并 并且要最小化 这个显然是有单调性的 因为 我们少合并一次就可以减少代价 并且这个代价必定是单调的 因为 最开始的只是小段的 随着合并的段数长度增加 这一段的或值显然是非严格递增的 那么的值显然也是非严格递增的 这样的话就证完了。 一个小问题 log运算非常慢 会因为这玩意T掉 所以那nlg个区间或值预处理出来比较好 附代码。 #includecstdio
#includecstring
#includealgorithm
#includecmath
#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 i1;in;i) f[i][0]a[i];for(int i1;i18;i)for(int j1;j(1i-1)n;j)f[j][i]f[j][i-1]|f[j(1i-1)][i-1];}int query(int l,int r){int klg[r-l1];return f[l][k]|f[r-(1k)1][k];}
}st;void find(int x)
{p[x][0]x;qaq[x][0]a[x];int cnt0;for(int i0;i20;i)if((!(a[x](1i)))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 i1;in;i) f[i]-inf,g[i]inf;for(int i1;in;i){for(int j0;j20p[i][j];j){//printf(%d %d %d\n,i,j,p[i][j]);ll tmpqaq[i][j]midf[p[i][j]-1];if(tmpf[i]||(tmpf[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 i1;in;i) scanf(%d,a[i]),tota[i];st.build();l[0]1;int i;for(i1;i18;i){l[i](1i);//printf(%d %d\n,i,l[i]);if(l[i]n) break;for(int jl[i-1];jl[i];j) lg[j]i-1;}for(int jl[i-1];jn;j) lg[j]i-1;int l,r;for(int i1;in;i){find(i);for(int j0;j20;j)if(a[i](1j)) fr[j]i;}l-inf;r0;ll ans;while(lr){int mid(lr)1;if(check(mid)) lmid1,ansf[n]-(ll)mid*k;else rmid-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
*/ 转载于:https://www.cnblogs.com/hanyuweining/p/10321914.html
