题解：CF2170F Build XOR on a Segment

stone_heart · 2025-11-29 11:36:17 · 题解

这个题不用线性基，但如果知道线性基的话就比较好想。

读题发现每个数仅有 12bit，n 只有 10^4，时限有 5s，这里面一定有什么深意。

考虑 r=n 的时候怎么做。你知道线性基，然后你就知道每个数至多用 12 个数可以异或出来。于是你就可以维护对于数 x，用 i 个数异或出来，这 i 个数中最早出现的数的位置的最大值 pos_{x,i} 。询问 [l,n],x 的时候就从低到高扫描 pos_{x,i} 看是不是不小于 l，找到了输出 i 就行了。

于是你就可以把询问离线，右移 r 的时候维护只考虑前 r 个数时的 pos_{x,i}，每次用 a_r 暴力更新 pos_{x,i} 就行了。
这题就做完了。时间复杂度 O(nV\log{V})，其中 V 为值域。

早知道赛时不调 D 做这题了。

code:

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int pos[4096][13];

void Insert(int x, int r){
    pos[x][1]=r;
    for(int j=11;j>=1;j--)
        for(int i=0;i<4096;i++)
            pos[i^x][j+1]=max(pos[i^x][j+1], pos[i][j]);
}

int query(int x, int l){
    for(int i=1;i<=12;i++)
        if(pos[x][i]>=l)return i;
    return 0;
}

struct ques{
    int l, r, x, id;
}q[1000500];
bool cmp(ques q1, ques q2){
    return q1.r<q2.r;
}

int a[10050], n, Ans[1000500], Q;

void init(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d", &a[i]);
    scanf("%d", &Q);
    for(int i=1;i<=Q;i++){
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].x);
        q[i].id=i;
    }
    sort(q+1, q+Q+1, cmp);
}

int main(){

    init();
    for(int r=1, j=1;r<=n;r++){
        Insert(a[r], r);
        while(j<=Q && q[j].r <= r){
            Ans[q[j].id] = query(q[j].x, q[j].l);
            j++;
        }
    }

    for(int i=1;i<=Q;i++)printf("%d ", Ans[i]);

    return 0;

}