题目大意

给你一个长度为 $n$ 的序列，要求你求出最大的 $k$ 满足对于任意的 $i,j\in[1,n-k+1]$ 满足：

$a_i\mid a_{i+1}\mid\cdots \mid a_{i+k-1}=a_j\mid a_{j+1}\mid \cdots \mid a_{j+k-1}$

思路

如果 $k$ 满足条件，那么一定一下性质：

$a_i\mid a_{i+1}\mid \cdots \mid a_{i+k-1}=a_j\mid a_{j+1}\mid \cdots \mid a_{j+k-1}$

$a_{i+1}\mid a_{i+2}\mid \cdots \mid a_{i+k}=a_{j+1}\mid a_{j+2}\mid \cdots \mid a_{j+k}$

由或操作的性质可以得到：

$a_i\mid a_{i+1}\mid \cdots \mid a_{i+k}=(a_i\mid a_{i+1}\mid \cdots \mid a_{i+k-1})\mid (a_{i+1}\mid a_{i+2}\mid \cdots \mid a_{i+k})$

$a_j\mid a_{j+1}\mid \cdots \mid a_{j+k}=(a_j\mid a_{j+1}\mid \cdots \mid a_{j+k-1})\mid (a_{j+1}\mid a_{j+2}\mid \cdots \mid a_{j+k})$

所以可以得到：

$a_i\mid a_{i+1}\mid \cdots \mid a_{i+k}=a_j\mid a_{j+1}\mid \cdots \mid a_{j+k}$

也就是 $k$ 是有单调性的，可以直接二分求解。

因为思维不够数据结构来凑，所以直接只用线段树加二分轻松是用 $O(n\log^2 n)$ 通过此题。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
void io(){ios::sync_with_stdio(false);cin.tie(nullptr);}
template<typename T>void write(T x){if(x<0) cout<<'-', x=-x;if(x>9) write(x/10);cout<<(char)(x%10+48);}
const int N=2e5+5;
int n,a[N];
struct segtree{
	int s[N<<2];
	void build(int k,int l,int r,int a[]){
		if(l==r){
			s[k]=a[l];
			return ;
		}
		int mid=(l+r)/2;
		build(k*2,l,mid,a);
		build(k*2+1,mid+1,r,a);
		s[k]=s[k*2]|s[k*2+1];
	}
	int ask(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y){
			return s[k];
		}
		if(x>r||l>y){
			return 0;
		}
		int mid=(l+r)/2;
		return ask(k*2,l,mid,x,y)|ask(k*2+1,mid+1,r,x,y);
	}
}tree;
bool ck(int mid){
	int ans=tree.ask(1,1,n,1,mid);
	for(int i=2;i+mid-1<=n;i++){
		if(ans!=tree.ask(1,1,n,i,i+mid-1)){
			return 0;
		}
	}
	return 1;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    }
    tree.build(1,1,n,a);
    int ans=n,l=1,r=n;
    while(l<=r){
    	int mid=(l+r)/2;
    	if(ck(mid)){
    		ans=mid;
    		r=mid-1;
    	}
    	else{
    		l=mid+1;
    	}
    }
    cout<<ans<<'\n';
}
signed main(){io();
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}