ZROI#1014
在某位置插入一个数,查询一段区间内所有数异或一个值之后的最大值,这看起来非常的数据结构,事实上这就是一道数据结构题…
题解是怎样的的呢?
$std$ 是这种写法 $:$ 对时间分块后用可持久化 $Trie$ 树维护.
不会,咋办?莫慌,我们有万能的 $vector$.
在位置 $pos$ 插入一个数 $x$ 就
1 | v.insert ( v.begin () + pos - 1 , x ) |
$-1$ 的原因是 $vector$ 的下标从 $0$ 开始.
查询 $[l,r]$ 中所有数异或一个 $x$ 的最大值就 $:$
1 | for (vector < int > :: iterator it = v.begin () + l - 1 ; it != v.begin () + r ; ++ it) |
为什么初始是 $v.begin () + l - 1$ 而结束就是 $v.begin () + r$ 呢?
因为左闭右开,其实还是因为下标从 $0$ 开始,一个道理.
你可能疑惑,这怎么可能过啊,明明就是 $\Theta(n^2)$.
确实…但 $vector$ 谜一样速度谁也说不清…之前还有 $vector$ 爆踩平衡树板子的操作呢.
当然,这样做你要略微卡卡常.
$Code:$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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
struct ios {
inline char gc(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char ch,sgn; ch = gc(), sgn = 0;
for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';}
for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0');
sgn&&(x=-x); return *this;
}
} io ;
const int inf = 0x7f7f7f7f ;
vector < int > v ;
int main () {
int lastans = 0 , ans ;
int T , x , y , k ;
bool opt , online ;
io >> T >> online ;
while ( T -- ) {
io >> opt >> x >> y ;
if ( online ) { x ^= lastans ; y ^= lastans ; }
if ( ! opt ) v.insert ( v.begin () + x - 1 , y ) ;
else {
io >> k ; ans = - inf ; if ( online ) k ^= lastans ;
for (auto it = v.begin () + x - 1 ; it != v.begin () + y ; ++ it)
ans = max ( ans , (int)( *it ^ k ) ) ;
printf ("%d\n" , lastans = ans ) ;
}
}
return 0 ;
}