AB 太简单了，不写解法了。

CF1732C Sheikh

我们观察一下 \(f(l,r)=\mathrm{sum}(l,r)-\mathrm{xor}(l,r)\) 的性质。

考虑假如一个数 \(x\)，对 \(\mathrm{sum}\) 的贡献为 \(x\)，而对 \(\mathrm{xor}\) 的贡献小于等于 \(x\)，因为可能异或和中已经有位为 \(1\)。

所以固定 \(l\)，\(f(l,r)\) 单调递增，固定 \(r\) 也有此性质。

另一个显而易见的结论是假如不要求区间长度最小，\([L,R]\) 就是最终的答案，所以其实最大值已经确定为 \(f(L,R)\)，只需要找长度最小的区间满足 \(f(l,r)=f(L,R)\) 即可。

由此结论，我们可以完成 C1，对于 \(i\in [L,R]\)，先判断如果 \(j\) 取 \(R\) 也就是最大能不能达到 \(f(L,R)\)，若能二分出使 \(f(i,j)\) 最大的 \(j_{\min}\)，最后求出最小长度即可。

复杂度 \(O(Tnq\log n)\)，其中 \(q=1\).

接下来考虑 C2，\(q\) 和 \(n\) 同阶，所以我们一次询问要求做到 \(O(\log n)\) 以内。

不知道有多少人可能想到过一个错误的做法：初始区间为 \([L,R]\)，若左右端点能缩就缩。

我们规定 \(l_1=L\)，\(l_1\) 为 \(R\) 作为右端点时区间满足 \(f=f(L,R)\) 左端点的最大值。

它错的原因是没有考虑每一个 \(l\in[l_1,l_2]\) 所对应的最小 \(r\)，而是直接考虑了最大的 \(l=l_2\) 对应的最小 \(r\)，从而遗漏了一些情况。

那么假如我们枚举每一个 \(l\in[l_1,l_2]\)，然后二分的话，复杂度如何呢？

显然如果区间中 \(0\) 很多，一次询问就会被卡到 \(O(n\log n)\)，这是我们不能接受的。

如果排除 \(0\) 的干扰，考虑答案区间 \([l,r]\)，它满足加入 \(a_{l-1}\) 或 \(a_{r+1}\) 后值不变（前提时 \(L<l\leq r<R\)），说明 \(a_{l-1}\) 或 \(a_{r+1}\) 的二进制位在 \(\mathrm{xor}(l,r)\) 中都为 \(0\)，那么最多有多少个这样的数呢，我们考虑每一个未加入的数都是 \(2^k\)，约有 \(\log V\) 个。所以 \(l_2-l_1+1\) 是小于 \(\log V\) 的，复杂度就有了保证。

加上 \(0\) 的干扰，我们只需要预处理出每一个数前面和后面第一个非 \(0\) 数，然后枚举 \(l\in[l_1,l_2]\) 改成 \(l\) 从 \(L\) 及之后第一个非 \(0\) 数开始往后跳 \(l_2-l_1+1\) 次即可。

复杂度 \(O(Tq\log V\log n)\)，但显然跑不满。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}

const int N=1e5+5;
int T,n,q,a[N],sum[N],xsum[N];

int erfen1(int ll,int rr,int fmax){
	int l=ll,r=rr,mid;
	while(l<r){
		mid=l+r>>1;
		if(sum[mid]-sum[ll-1]-(xsum[mid]^xsum[ll-1])>=fmax)r=mid;
		else l=mid+1;
	}
	return l;
} 

int erfen2(int ll,int rr,int fmax){
	int l=ll,r=rr,mid;
	while(l<r){
		mid=l+r+1>>1;
		if(sum[rr]-sum[mid-1]-(xsum[rr]^xsum[mid-1])>=fmax)l=mid;
		else r=mid-1;
	}
	return l;
}

int nxt[N],pre[N];

signed main(){
	T=read();
	while(T--){
		n=read(),q=read();
		for(int i=1;i<=n;++i){
			a[i]=read();
			sum[i]=sum[i-1]+a[i];
			xsum[i]=(xsum[i-1]^a[i]);
		}
		int lst=0;
		for(int i=1;i<=n;++i){
			pre[i]=lst;
			if(!a[i])continue;
			lst=i;
		}
		lst=n+1;
		for(int i=n;i>=1;--i){
			nxt[i]=lst;
			if(!a[i])continue;
			lst=i;
		}
		while(q--){
			int L=read(),R=read();
			if(sum[R]==sum[L-1]){print(L),printf(" "),print(L),puts("");continue;}
			if(!a[L])L=nxt[L];
			if(!a[R])R=pre[R];
			int fmax=sum[R]-sum[L-1]-(xsum[R]^xsum[L-1]);
			int cnt=erfen2(L,R,fmax)-L+1,l=L,r=R,i=L;
			while(cnt--){
				if(sum[R]-sum[i-1]-(xsum[R]^xsum[i-1])<fmax)break;
				int j=erfen1(i,R,fmax);
				if(j-i<r-l)l=i,r=j;
				i=nxt[i];
				if(i>n)break;
			}
			print(l),printf(" "),print(r),puts("");
		}
	}
	return 0;
}