题目链接
题目解法
很牛逼的构造题
好像随也可以过
长度为 \(2^{k+1}\) 的序列的不同区间有 \(2^{2k+1}\) 个，值域是 \(4^k\)，所以一定有解
将 \(a\) 做一遍前缀和，那么问题转化成了找 \(s_{r1}\oplus s_{l1-1}=s_{r2}\oplus s_{l2-1}\)
先讲一讲具体做法：
按照前 \(k\) 位和后 \(k\) 位分组
从前往后扫序列，令 \(i\) 前一个和它前 \(k\) 位相同的数为 \(lst\)（没有就不考虑）
把 \(s_i\oplus s_{lst}\) 放进 \(map\)（其实就是后 \(k\) 位的异或值），如果 \(map\) 中已经有 \(s_i\oplus s_{lst}\)，那么就找到合法解
证明一下：
首先这样找到的解一定是合法的（相当于缩小了合法解集的范围，从而减少时间）
一共有 \(2^{k+1}+1=2^k+2^k+1\) 个前缀和
所以 \(lst\) 有值的 \(i\) 至少有 \(2^k+1\) 个
因为后 \(k\) 位取值最多有 \(2^k\) 个，根据鸽巢原理，一定有 \(2\) 个数相同
时间复杂度 \(O(2^k\log?)\)，\(map\) 带一个 \(\log\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=300000;
int pw2[20],lst[1<<17];
LL a[N],s[N];
vector<int> nums[N];
map<int,pii> mp;
int p[4];
void work(){
int k;read(k);int n=pw2[k+1];
F(i,1,n) read(a[i]);
F(i,1,n) s[i]=s[i-1]^a[i];
F(i,0,(1<<k)-1) lst[i]=-1;
mp.clear();
F(i,0,n){
int lb=s[i]&((1<<k)-1),hb=s[i]>>k;
if(lst[lb]!=-1){
int v=hb^(s[lst[lb]]>>k);
if(!mp.count(v)) mp[v]={lst[lb],i};
else{
p[0]=lst[lb],p[1]=i,p[2]=mp[v].first,p[3]=mp[v].second;
sort(p,p+4);
printf("%d %d %d %d\n",p[0]+1,p[1],p[2]+1,p[3]);return;
}
}
lst[lb]=i;
}
}
signed main(){
pw2[0]=1;
F(i,1,18) pw2[i]=pw2[i-1]*2;
int T;read(T);
while(T--) work();
return 0;
}