网站修改后怎么上传,济南网络员,惠州的企业网站建设,百度认证考试description
戳我看题目(づ#xffe3;3#xffe3;)づ╭❤#xff5e;
solution
异或和最大 ——关联线性基 线性基#xff1a; 原序列的每一个数都能由线性基里若干个数异或得到线性基里若干个数的异或结果不可能为0 如果直接线段树合并线性基时间复杂度是无法接受
离…description
戳我看题目(づ3)づ╭❤
solution
异或和最大 ——关联线性基 线性基 原序列的每一个数都能由线性基里若干个数异或得到线性基里若干个数的异或结果不可能为0 如果直接线段树合并线性基时间复杂度是无法接受
离线下来考虑分治
一样的只在左区间或右区间的分治下去处理考虑询问跨越了中点midmidmid的
处理[l,mid][l,mid][l,mid]区间每个点的后缀线性基[mid1,r][mid1,r][mid1,r]区间每个点的前缀线性基
暴力合并线性基即可
code
#include cstdio
#include cstring
#define maxn 500005
int n, Q;
int a[maxn], ql[maxn], qr[maxn], p[maxn];
int left[maxn], right[maxn], ans[maxn];struct node {int f[20];void insert( int x ) {for( int i 19;~ i;i -- )if( ( 1 i ) x ) {if( ! f[i] ) { f[i] x; break; }else x ^ f[i];}}void clear() {memset( f, 0, sizeof( f ) );}}base[maxn];int merge( node x, node y ) { //线性基合并 int num 0;for( int i 19;~ i;i -- )x.insert( y.f[i] );for( int i 19;~ i;i -- )if( ( num ^ x.f[i] ) num ) num ^ x.f[i];return num;
}void solve( int L, int R, int l, int r ) {if( L R || l r ) return;if( l r ) {for( int i L;i R;i )ans[p[i]] a[l];return;}int mid ( l r ) 1, lenl 0, lenr 0;//暴力重构区间[l,r]的线性基base[mid].clear(); //不要忘记清空了 base[mid].insert( a[mid] );for( int i mid - 1;i l;i -- )base[i] base[i 1], base[i].insert( a[i] );for( int i mid 1;i r;i )base[i] base[i - 1], base[i].insert( a[i] );for( int i L;i R;i ) {int id p[i];if( ql[id] mid ) {if( qr[id] mid ) //完全在左区间 递归处理 left[ lenl] id;elseans[id] merge( base[ql[id]], base[qr[id]] );}else //完全在右区间 递归处理 right[ lenr] id;}for( int i 1;i lenl;i ) p[L i - 1] left[i];for( int i 1;i lenr;i ) p[L lenl i - 1] right[i];solve( L, L lenl - 1, l, mid );solve( L lenl, L lenl lenr - 1, mid 1, r );
}int main() {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, ql[i], qr[i] );p[i] i;}solve( 1, Q, 1, n );for( int i 1;i Q;i )printf( %d\n, ans[i] );return 0;
}
