HDU 6579 Operation

现在看了看以前的题感觉好妙啊。。多校的时候好像是找出原题直接做的。。

为了回答询问,可以贪心地做前缀的线性基。由于只有 append 操作,可以方便地维护这个。

对于 $1\sim i$ 的线性基,我们可以对每个位置记一个编号,表示能够选择这一位的最靠右的数编号是什么。

在插入一个数到线性基的时候,从高到低位考虑,如果这个数比这个位置上的数更靠右且这个数可以更新这一位,我们可以把这个数和线性基中这个数字交换一下,再更新编号,然后继续向低位更新。

考虑正确性,对于一个位置,它显然只会被比它的编号高的数更新到(否则这个数会和更新它的数交换,然后这个数去更新更低的位置)。而且由于我们是从高到低位贪的,最后查询答案也只需要从高到低位查询一下这个位置的编号是否不小于 $l$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 418254373
const double eps = 8e-10;
int n , m;
int A[MAXN];

int b[MAXN][31] , p[MAXN][31];

void ins( int ps , int x , int idx ) {
for( int i = 29 ; i >= 0 ; -- i ) if( x & ( 1 << i ) ) {
if( !b[ps][i] ) { b[ps][i] = x , p[ps][i] = idx; return; }
if( p[ps][i] < idx )
swap( idx , p[ps][i] ) , swap( x , b[ps][i] );
x ^= b[ps][i];
}
}

int que( int l , int r ) {
int ret = 0;
for( int i = 29 ; i >= 0 ; -- i ) if( ( ~ret & ( 1 << i ) ) && b[r][i] && p[r][i] >= l )
ret ^= b[r][i];
return ret;
}

void solve() {
cin >> n >> m;
rep( i , 1 , n ) {
scanf("%d",A + i);
memcpy( b[i] , b[i - 1] , sizeof b[i] );
memcpy( p[i] , p[i - 1] , sizeof p[i] );
ins( i , A[i] , i );
}
int op , l , r , x , last = 0;
rep( i , 1 , m ) {
scanf("%d",&op);
if( op == 0 ) {
scanf("%d%d",&l,&r);
l = ( l ^ last ) % n + 1 , r = ( r ^ last ) % n + 1;
if( l > r ) l ^= r ^= l ^= r;
printf("%d\n",last = que( l , r ) );
}
else {
scanf("%d",&x);
x ^= last;
++ n;
memcpy( b[n] , b[n - 1] , sizeof b[n] );
memcpy( p[n] , p[n - 1] , sizeof p[n] );
ins( n , x , n );
}
}
}

signed main() {
// freopen("input","r",stdin);
// freopen("fuckout","w",stdout);
int T;cin >> T;while( T-- ) solve();
// solve();
}

文章作者: yijan
文章链接: https://yijan.co/hdu-6579-operation/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog