题解：CF1835C Twin Clusters

Petit_Souris · 2024-08-02 09:02:39 · 题解

这啥啊，我是真不会做。

设 n=2^{k+1}。

发现我们如果选出一组左端点和右端点都不相同的区间，那么一定可以构造出解：如果不交直接作为答案，否则把相交部分同时删掉不影响异或值相等。

把值域分成高 k 位和低 k 位。设前缀异或和为 s_{0},s_{1},\dots ,s_{n}，其中 s_0=0。对于一个值 v，如果我们能找到 x_1<y_1<x_2<y_2 满足 s_{x_1-1},s_{y_1} 高 k 位相同，s_{x_2-1} 和 s_{y_2} 高 k 位相同，且 s_{x_1-1}\oplus s_{y_1},s_{x_2-1}\oplus s_{y_2} 的低 k 位相同，那么一定可以通过 [x_1,y_1] 和 [x_2,y_2] 通过上一段中的构造方式得到答案。

考虑怎样找到这样的两个区间：设 p 为 i 前面第一个满足 s_{p}=s_{i} 的位置，那么我们取出所有 [p+1,i]，至少有 2^k+1 组这样的区间，所以其中必定有一对满足条件。拿个桶维护一下就行了，时间复杂度 \mathcal O(2^k)。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=1e6+9;
ll T,k,n,a[N],bin[N],pl[N],pr[N];
void solve(){
    k=read(),n=(2<<k);
    rep(i,1,n)a[i]=read();
    a[0]=0;
    rep(i,1,n)a[i]^=a[i-1];
    rep(i,0,n)bin[i]=pl[i]=pr[i]=-1;
    bin[0]=0;
    rep(i,1,n){
        if(~bin[a[i]>>k]){
            ll l=bin[a[i]>>k]+1,r=i,s=a[r]^a[l-1];
            if(!~pl[s])pl[s]=l,pr[s]=r;
            else {
                if(pr[s]<l)write(pl[s]),putchar(' '),write(pr[s]),putchar(' '),write(l),putchar(' '),write(r);
                else write(min(l,pl[s])),putchar(' '),write(max(l,pl[s])-1),putchar(' '),write(pr[s]+1),putchar(' '),write(r);
                putchar('\n');
                return ;
            }
        }
        bin[a[i]>>k]=i;
    }
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    T=read();
    while(T--)solve();
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}