自动搬运

查看原文

来自洛谷，原作者为

	i_am_not_feyn 志士幽人莫怨嗟，古来材大难为用

搬运于2025-08-24 22:51:26，当前版本为作者最后更新于2023-10-17 14:53:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

个人认为 CSP 应该并不会考什么复杂的 DS，这道题的难度基本上都在实现上了。

首先观察一个序列合法的条件。

注意到操作并不会使得某一个一开始存在的二进制位消失，并且要求最后的序列全为一个数，那么显然这个数就是整个序列的或。

下文中令四元组 $(l1,r1,l2,r2)$ 表示一次操作。

令这个数为 $mx$，若序列中没有 $mx$ 则显然是非法的。假定有两个 $mx$ 在序列中的位置分别为 $i,i+1$，那么可以通过 $(i,i+1,i+1,i+2)$ 或者 $(i,i+1,i-1,i)$ 使得 $mx$ 向两边扩展，最终使得序列全为 $mx$。

若有一个 $mx$ 的位置为 $i$，且右边有一区间 $[i+1,r]$ 的或等于 $mx$，则可以通过 $(i,r-1,i+1,r)$ 使得 $i+1$ 的位置为 $mx$，转化为上述情况。区间在左边也是同理的。

故而一个序列是合法的当且仅当可以找到一个 $mx$ 和一个不包含这个 $mx$ 的或为 $mx$ 的区间。

对于原序列的每个位置 $i$ 作为某个区间的 $mx$ 时，这个区间 $[L_i,R_i]$ 的或应该为 $a_i$，$L_i$ $R_i$ 是容易求出的。若要使这个区间合法，那么可以求出 $l_i$ 表示最大的 $l$ 使得 $[l,i)$ 的或包含了 $a_i$，$r_i$ 同理。令当前询问的区间为 $[l',r']$，则有以下两种情况 $i$ 会做出 $\min(r',R_i)-\max(l',L_i)+1$ 的贡献。

1. $l_i\ge L_i,l_i\ge l'$
2. $r_i\le R_i,r_i\le r'$

只考虑 1 的情况，2 的话倒着再做一遍就是。接下来就是没有脑子的套路了。

显而易见的，将 $l_i<L_i$ 的 $i$ 踢出去不考虑，把 $l$ 后往前扫描线一下，每次扫到一个新的 $l$ 就将 $l_i=l$ 的 $i$ 加进线段树中。现在线段树中的节点均满足 1 的条件，只需要在 $i\in[l,r']$ 中找到最优解即可。

由于不好处理 $\max(l,L_i)$，考虑将所有的 $i$ 按照是否小于 $l$ 插入 AB 线段树中。由于 $l$ 是逐渐变小的，那么 A 是要支持删除的。

A 中元素的贡献是 $\min(r',R_i)-l'+1$，那么只用维护区间中 $i$ 的 $R$ 最大值即可，删除就是单点赋值为 0。

B 中元素的贡献是 $\min(r',R_i)-L_i+1$，由于不带修，则可以直接维护每个 $r'$ 的答案。在 $[i,R_i]$ 的区间插入 $-L_i+1$，在 $(R_i,n]$ 的区间插入 $R_i-L_i+1$，每次就是单点查询两种情况的最大值，标记永久化即可。

时间是 $O(n\log n)$ 的，由于这个解法没啥脑子基本上就是大力分讨，常数颇高，但是 7s 的时限还是稳过的。

code

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+50,M=8e6+50,inf=1e9+7;

namespace IO {
//IO 由于是贺别人的所以不是很能放出来
} // IO
using namespace IO;

int T,Tid,n,q,a[N],m=30,Ans[N];

struct ask
{
	int l,r,id;
	
	friend bool operator<(ask a,ask b)
	{
		return a.l<b.l;
	}
}Q[N];

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)

class sukwants
{
	public:
		int mx[M],d,val,L,R,ans;
		
		void add(int x,int l,int r)
		{
			if(l==r)return void(mx[x]=val);
			if(d<=mid)add(ls,l,mid);
			else add(rs,mid+1,r);
			mx[x]=max(mx[ls],mx[rs]);
		}
		
		void find(int x,int l,int r)
		{
			if(L<=l&&R>=r)return void(ans=max(ans,mx[x]));
			if(L<=mid)find(ls,l,mid);
			if(R>mid)find(rs,mid+1,r);
		}
		
		void add(int a,int b){d=a,val=b;add(1,1,n);}
		int find(int l,int r){L=l,R=r;ans=0;find(1,1,n);return ans;}
}sgt;

class sukwats
{
	public:
		int val[M],w[M],L,R,d,ans;
		
		void Insert(int x,int l,int r)
		{
			if(L<=l&&R>=r)return void(val[x]=max(val[x],d));
			if(L<=mid)Insert(ls,l,mid);
			if(R>mid)Insert(rs,mid+1,r);
		}
		
		void Add(int x,int l,int r)
		{
			if(L<=l&&R>=r)return void(w[x]=max(w[x],d));
			if(L<=mid)Add(ls,l,mid);
			if(R>mid)Add(rs,mid+1,r);
		}
		
		void find(int x,int l,int r)
		{
			ans=max(ans,max(val[x],w[x]+d));
			if(l==r)return;
			return (d<=mid)?find(ls,l,mid):find(rs,mid+1,r);
		}
		
		void insert(int l,int r,int v){L=l,R=r,d=v;Insert(1,1,n);}
		void add(int l,int r,int v){L=l,R=r,d=v;Add(1,1,n);}
		int find(int x){d=x;ans=0;find(1,1,n);return ans;}
}sgc;
		
void dfs(int x,int l,int r)
{
	sgt.mx[x]=0;sgc.val[x]=sgc.w[x]=-inf;
	if(l!=r)dfs(ls,l,mid),dfs(rs,mid+1,r);
}

int L[N],R[N],rel[N],rer[N],fir[2][32],las[2][32];

class shabi_ds
{
	public:
		int a[N],L[N],R[N],re[N];
		vector<int>in[N],out[N];
		
		void clear()
		{
			for(int i=1;i<=n;i++)vector<int>().swap(in[i]),vector<int>().swap(out[i]);
		}
		
		void pre()
		{
			sort(Q+1,Q+1+q);dfs(1,1,n);clear();
			for(int i=1;i<=n;i++)if(re[i]>=L[i])in[re[i]].push_back(i),out[L[i]].push_back(i);
		}
		
		void solve()
		{
			pre();int pos=q;
			for(int i=n;i>=1;i--)
			{
				for(auto x:in[i])sgt.add(x,R[x]);
				for(auto x:out[i])
				{
					sgt.add(x,0),sgc.add(x,R[x],-L[x]+1),sgc.insert(R[x],n,R[x]-L[x]+1);
				}
				while(pos&&Q[pos].l==i)
				{
					int x=min(Q[pos].r,sgt.find(Q[pos].l,Q[pos].r)),y=sgc.find(Q[pos].r);
					Ans[Q[pos].id]=max(Ans[Q[pos].id],max(x-i+1,y)),pos--;
				}
			}
		}
}A,B;

void init()
{
	for(int i=1;i<=n;i++)L[i]=1,R[i]=n,rel[i]=rer[i]=i;
	for(int i=0;i<=m;i++)fir[1][i]=0,las[1][i]=n+1;
	for(int ty=0,i=1;i<=n;i++,ty^=1)for(int j=0;j<=m;j++)
	if((a[i]>>j)&1)rel[i]=min(rel[i],fir[ty^1][j]),fir[ty][j]=i;
	else fir[ty][j]=fir[ty^1][j],L[i]=max(L[i],fir[ty][j]+1);
	for(int ty=0,i=n;i>=1;i--,ty^=1)for(int j=0;j<=m;j++)
	if((a[i]>>j)&1)rer[i]=max(rer[i],las[ty^1][j]),las[ty][j]=i;
	else las[ty][j]=las[ty^1][j],R[i]=min(R[i],las[ty][j]-1);
	for(int i=1;i<=n;i++)
	{
		A.L[i]=L[i],A.R[i]=R[i],A.re[i]=rel[i];
		B.R[n-i+1]=n-L[i]+1,B.L[n-i+1]=n-R[i]+1,B.re[n-i+1]=n-rer[i]+1;
	}
}

void sol()
{
	read(n);read(q);
	for(int i=1;i<=n;i++)read(a[i]),A.a[i]=B.a[n-i+1]=a[i];
	for(int i=1;i<=q;i++)read(Q[i].l),read(Q[i].r),Q[i].id=i,Ans[i]=1;
	init();A.solve();
	for(int i=1;i<=q;i++)Q[i].l=n-Q[i].l+1,Q[i].r=n-Q[i].r+1,swap(Q[i].l,Q[i].r);
	B.solve();
	for(int i=1;i<=q;i++)write(Ans[i]);
}

main()
{
	read(T),read(Tid);
	while(T--)sol();
}