提出 #69910029

---

ソースコード 拡げる

/*
*            /$$           /$$
*           |__/          |__/
*  /$$$$$$$$ /$$ /$$$$$$$$ /$$  /$$$$$$
* |____ /$$/| $$|____ /$$/| $$ /$$__  $$
*    /$$$$/ | $$   /$$$$/ | $$| $$  \ $$
*   /$$__/  | $$  /$$__/  | $$| $$  | $$
*  /$$$$$$$$| $$ /$$$$$$$$| $$|  $$$$$$$
* |________/|__/|________/|__/ \____  $$
*                                   | $$
*                                   | $$
*                                   |__/
*/
//hj23308保佑我
//Missile保佑我
/*
* 醒了在梦里挣扎，不觉黯淡了朝霞
*/
/*
* 我很高兴你没有忘了我，但是我现在更希望你已经忘了我了。
* 希望在你的记忆中，我只是尘土一撮，从你的全世界路过，然后四散飞扬不留下一点痕迹，而你要不回头的往前走。
* 我更希望我只是从你的全世界路过，只是路过
*/
/*
* 只是我在十字路口守了太久，守到黄沙如雨掩埋一切痕迹，才发现自己等的人已经离开了。
*/
/*
* 听我的 别回头 回头就可能会泪流满面，会被黄沙掩埋，所以即使痛苦也要向前走
*/
/*
* 我听到了「天行健」的回响，这是一个伟大斗士的不息自强；
* 我听到了「破万法」的回响，这是一个黑道打手的守护欲望；
* 我看见了「生生不息」的激荡，这是一个骗子的伟大乐章！
*/
/*
* 我用虚假的面具照顾着细腻的感情；
* 我以华丽的衣物下藏着腐烂的血肉；
* 当我摘下面具，褪去衣物，即便是我最亲近的人，也无法直视我
*/
#include<bits/stdc++.h>
using namespace std;
mt19937 engine(chrono::steady_clock().now().time_since_epoch().count());
const int MAXN=2e5+5;
const int N=(1<<30)-1;
int n;
int tot,a[MAXN],b[32*MAXN];
struct TreeB {
	#define Ls(u) (ls[u])
	#define Rs(u) (rs[u])
	int idx,ls[400*MAXN],rs[400*MAXN],sum[400*MAXN];
	TreeB() {
		sum[0]=-1;
	}
	void pushUp(int u)
	{
		sum[u]=max(sum[Ls(u)],sum[Rs(u)]);
	}
	void Modify(int &u,int l,int r,int pos,int val)
	{
		if(!u) u=++idx,sum[u]=-1;
		if(l==r) {
			sum[u]=max(sum[u],val);
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid) Modify(Ls(u),l,mid,pos,val);
		else Modify(Rs(u),mid+1,r,pos,val);
		pushUp(u);
	}
	int Query(int u,int l,int r,int L,int R)
	{
		if(!u) return -1;
		if(L<=l&&r<=R) return sum[u];
		int mid=(l+r)>>1,Ans=-1;
		if(L<=mid) Ans=max(Ans,Query(Ls(u),l,mid,L,R));
		if(mid+1<=R) Ans=max(Ans,Query(Rs(u),mid+1,r,L,R));
		return Ans;
	}
	#undef Ls
	#undef Rs
}treeB;
struct TreeA {
	#define Ls(u) (u<<1)
	#define Rs(u) (u<<1|1)
	int root[4*MAXN];
	void Modify(int u,int l,int r,int posA,int posB,int val)
	{
		treeB.Modify(root[u],1,tot,posB,val);
		if(l==r) return;
		int mid=(l+r)>>1;
		if(posA<=mid) Modify(Ls(u),l,mid,posA,posB,val);
		else Modify(Rs(u),mid+1,r,posA,posB,val);
	}
	int Query(int u,int l,int r,int xL,int xR,int yL,int yR)
	{
		if(xL>xR||yL>yR) return -1;
		if(xL<=l&&r<=xR) return treeB.Query(root[u],1,tot,yL,yR);
		int mid=(l+r)>>1,Ans=-1;
		if(xL<=mid) Ans=max(Ans,Query(Ls(u),l,mid,xL,xR,yL,yR));
		if(mid+1<=xR) Ans=max(Ans,Query(Rs(u),mid+1,r,xL,xR,yL,yR));
		return Ans;
	}
}treeA;
void modify(int id,vector<int>&Q)
{
	int res=a[id];
	vector<int>P;
	P.emplace_back(id);
	for(auto pos:Q) {
		if((res|a[pos])!=res) P.emplace_back(pos);
		res|=a[pos];
	}
	swap(P,Q);
}
int calc(int val)
{
	return lower_bound(b+1,b+tot+1,val)-b;
}
void Init()
{
	vector<int>Q;
	b[++tot]=0;
	for(int i=1;i<=n;i++) {
		modify(i,Q);
		int res=a[i];
		b[++tot]=a[i];
		for(auto pos:Q) {
			res|=a[pos];
			b[++tot]=res;
		}
	}
	sort(b+1,b+tot+1);
	tot=unique(b+1,b+tot+1)-b-1;
}
int solve()
{
	treeA.Modify(1,0,n,0,1,0);
	int Ans=0;
	vector<int>Q;
	for(int i=1;i<=n;i++) {
		modify(i,Q);
		int res=a[i],last=i+1;
		for(auto pos:Q) {
			int val=treeA.Query(1,0,n,pos,last-1,1,calc(res))+1;
			if(val!=0) {
				treeA.Modify(1,0,n,i,calc(res),val);
				if(i==n) Ans=max(Ans,val);
			}
			res|=a[pos];
			last=pos;
		}
		int val=treeA.Query(1,0,n,0,last-1,1,calc(res))+1;
		if(val!=0) {
			treeA.Modify(1,0,n,i,calc(res),val);
			if(i==n) Ans=max(Ans,val);
		}
	}
	return Ans;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	Init();
	cout<<solve()<<"\n";
	return 0;
}

提出情報

ジャッジ結果