Kattis - bitwise Bitwise (RMQ+尺取+树上dfs)

题意：有一个长度为n的序列，让你把它分成k段，段内元素取or，段间取and，求能够得到的最大值。

这个算法是我和xz场上yy出来的，然而时间不够了没写出来，而且时间复杂度是$O(nlogn+nlogA)$的比官方题解都要低...（但是常数大了点）

设最大值为ans，我们假设S&ans=S，看看S能否用k条线段凑出来，则将原问题转化成了一个判定问题。从高到低一位一位地考虑，最多只需进行$O(logA)$次判定。

如何进行判定呢？

首先将原数组复制一倍接到后面，然后进行两次尺取。第一次求出每个左端点l所对应的能够覆盖S的最小的右端点r并把它作为一条线段放进数组里（能够覆盖S的意思是S的每一位上的1都可以在[l,r]区间里的某个元素中取到，可以用RMQ预处理区间or然后$O(1)$判断），第二次则对这些线段进行尺取，求出每条线段右边第一条和它不相交的线段，将每条线段与这样的线段连边，可以得到一棵树（或者森林，若为森林则将所有树和一个虚节点连边即可变成一棵树），只需要检查一下这棵树上是否有一个结点的l和与它距离为k的父亲结点的r的区间长度r-l+1是否小于n，从根节点dfs一遍即可。

代码：（我写了两份，第一份怕爆栈所以手写了数组模拟栈，第二份是普通的dfs）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=1e6+;

 int n,k,a[N],ST[N][],Log[N],nl,hd[N],ne,q[N],tp;

 void build() {

     for(int i=; i<=*n; ++i)ST[i][]=a[i];

     for(int k=; k<=Log[*n]; ++k)

         for(int i=; i+(<<k)-<=*n; ++i)

             ST[i][k]=ST[i][k-]|ST[i+(<<(k-))][k-];

 }

 int qry(int L,int R) {

     int k=Log[R-L+];

     return ST[L][k]|ST[R-(<<k)+][k];

 }

 struct D {int l,r;} line[N];

 struct E {int v,nxt;} e[N];

 struct ND {int u,dep;} sta[N];

 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}

 bool dfs() {

     sta[tp=]= {nl,};

     while(~tp) {

         int u=sta[tp].u,dep=sta[tp--].dep;

         q[dep]=u;

         if(dep>=k&&line[q[dep-k+]].r-line[u].l+<=n)return ;

         for(int i=hd[u]; ~i; i=e[i].nxt)sta[++tp]= {e[i].v,dep+};

     }

     return ;

 }

 bool ok(int S) {

     nl=;

     for(int i=,j=; i<=*n; ++i) {

         if(j<i)j=i;

         for(; j<=*n&&(qry(i,j)&S)!=S; ++j);

         if(j<=*n)line[nl++]= {i,j};

     }

     for(int i=; i<=nl; ++i)hd[i]=-;

     ne=;

     for(int i=,j=; i<nl; ++i) {

         for(; j<nl&&line[j].l<=line[i].r; ++j);

         addedge(j,i);

     }

     return dfs();

 }

 int solve() {

     int ret=;

     for(int i=; i>=; --i)if(ok(ret|(<<i)))ret|=<<i;

     return ret;

 }

 int main() {

     Log[]=-;

     for(int i=; i<N; ++i)Log[i]=Log[i>>]+;

     scanf("%d%d",&n,&k);

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)a[i+n]=a[i];

     build();

     printf("%d\n",solve());

     return ;

 }

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=1e6+;

 int n,k,a[N],ST[N][],Log[N],nl,hd[N],ne,q[N];

 void build() {

     for(int i=; i<=*n; ++i)ST[i][]=a[i];

     for(int k=; k<=Log[*n]; ++k)

         for(int i=; i+(<<k)-<=*n; ++i)

             ST[i][k]=ST[i][k-]|ST[i+(<<(k-))][k-];

 }

 int qry(int L,int R) {

     int k=Log[R-L+];

     return ST[L][k]|ST[R-(<<k)+][k];

 }

 struct D {int l,r;} line[N];

 struct E {int v,nxt;} e[N];

 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}

 bool dfs(int u,int dep) {

     q[dep]=u;

     if(dep>=k&&line[q[dep-k+]].r-line[u].l+<=n)return ;

     for(int i=hd[u]; ~i; i=e[i].nxt)if(dfs(e[i].v,dep+))return ;

     return ;

 }

 bool ok(int S) {

     nl=;

     for(int i=,j=; i<=*n; ++i) {

         if(j<i)j=i;

         for(; j<=*n&&(qry(i,j)&S)!=S; ++j);

         if(j<=*n)line[nl++]= {i,j};

     }

     for(int i=; i<=nl; ++i)hd[i]=-;

     ne=;

     for(int i=,j=; i<nl; ++i) {

         for(; j<nl&&line[j].l<=line[i].r; ++j);

         addedge(j,i);

     }

     return dfs(nl,);

 }

 int solve() {

     int ret=;

     for(int i=; i>=; --i)if(ok(ret|(<<i)))ret|=<<i;

     return ret;

 }

 int main() {

     Log[]=-;

     for(int i=; i<N; ++i)Log[i]=Log[i>>]+;

     scanf("%d%d",&n,&k);

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)a[i+n]=a[i];

     build();

     printf("%d\n",solve());

     return ;

 }

巴特西

Kattis - bitwise Bitwise (RMQ+尺取+树上dfs)

最新文章

热门文章