题解：AT_arc207_c [ARC207C] Combine to Make Non-decreasing

/*

		2025.11.14

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=200005,inf=0x3f3f3f3f;
int n,ans=1,cnt;
int f[MAXN][55],a[MAXN],lg2[MAXN];
int st[MAXN][25];
vector<int>fr[MAXN],to[MAXN];
vector<PP>g[MAXN];
unordered_map<int,multiset<int,greater<int> > >orz;
inline int gt(int l,int r){int t=lg2[r-l+1];return st[l][t]|st[r-(1<<t)+1][t];}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n;memset(f,-0x3f,sizeof(f));
	lg2[1]=0;
	for(int i=2;i<MAXN;i++)lg2[i]=lg2[i/2]+1;
	for(int i=1;i<=n;i++)cin>>a[i],st[i][0]=a[i];
	for(int i=1;i<=20;i++)for(int j=1;j+(1<<i)-1<=n;j++)st[j][i]=st[j][i-1]|st[j+(1<<i-1)][i-1];
	for(int i=1;i<=n;i++){
		int x=i-1;to[i].pb(i-1);
		while(x<n){
			int l=x+1,r=n;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(gt(i,mid)==gt(i,x+1))l=mid;
				else r=mid-1;
			}
			x=l;to[i].pb(x);
		}
		x=i+1;fr[i].pb(0);
		while(x>1){
			int l=1,r=x-1;
			while(l<r){
				int mid=(l+r)>>1;
				if(gt(mid,i)==gt(x-1,i))r=mid;
				else l=mid+1;
			}
			fr[i].pb(gt(x-1,i));x=l;
		}
	}
	f[0][0]=0;fr[0].pb(0);
	for(int i=0;i<=n;i++){
		for(auto j:g[i]){
			if(j.fi==1)orz[j.se.fi].insert(j.se.se);
			else orz[j.se.fi].erase(orz[j.se.fi].find(j.se.se));
		}
		for(int j=1;j<fr[i].size();j++)if(orz[fr[i][j]].size())f[i][j]=(*(orz[fr[i][j]].begin()));
		if(i==n)break;
		for(int j=1;j<to[i+1].size();j++){
			int tf=-inf,tmp=gt(i+1,to[i+1][j]);
			for(int _=0;_<fr[i].size();_++)if(fr[i][_]<=tmp)tf=max(tf,f[i][_]);
			if(tf>=0)g[to[i+1][j-1]+1].pb({1,{tmp,tf+1}}),g[to[i+1][j]+1].pb({0,{tmp,tf+1}});
		}
	}
	for(int i=1;i<=40;i++)ans=max(ans,f[n][i]);
	cout<<ans;
	return 0;
}