线段树动态开点，对于这题顺便挂个自己学校OJ
Tulip Festival
以及后面跟着的几个版本，用线段树动态开点都能过。
题意：给 n 个数字,m个操作
操作两种:
1 把p修改成x
2 查询 [l,r]区件类与 [l,r]区间异或和不相等的数字个数。
题解：把每个数字的下标放到一个数组，区间异或和直接用树状数组求出来(对于不会用树状数组求区间异或和的多去做做树状数组基础题)
然后每次查询区间里面的有个数字和异或值相等即可。
有一个版本只有200个相同值，这个直接用vector存，然后暴力查找就行了。但是后面出现了大量相同的数字，就不能暴力了。
查询区间类有多少个值，可以用树状数组最简洁，但是明显1e6个数，每个数开一个树状数组，长度为1e6明显炸了。
用线段树，如果直接开空间每个都要开nlogn个点，明显也会炸。但是自信一想，其中有很多点都是无用的，所有数加起来个数最多不到1e6个点，所以用线段树动态开点，最多不会超过nlogn个点。
线段树动态开点其实和普通的线段树其实差距不大。动态开点，就是把没有用的节点就不给他分配内存，字节当作空，这样每个数字最多最多开logn个点。动态开点建议用结构体写，这样可以方便一点。
结构体设置3个值一个是当前节点保存的值，左右儿子下标
举个例子，加入线段树总长度是 1 - 8,你在 1 1 插入一个值。
那么你就需要 1-8 1-4 1-2 1-1这几个点开空间，其他点直接不用管，查询的时候直接返回01
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const long long mod = 1e9 + 7;
const int maxn = 1e6 + 5 + 1e5;
const int INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;
void f() {
freopen("../1.in", "r", stdin);
freopen("../data.out", "w", stdout);
return;
}
int tot, n, m;
int a[maxn], bit[maxn];
unordered_map<int, int> mp;
int sum(int i) {
int ans = 0;
while (i > 0) {
ans ^= bit[i];
// debug(i);
i -= i & -i;
}
return ans;
}
void add(int i, int x) {
while (i <= n) {
bit[i] ^= x;
// debug(i);
i += i & -i;
}
}
struct node {
int x;
int chl, chr;
} tree[maxn * 50];
int tt;
void update(int a, int b, int l, int r, int k, int bol) {
if (b < l || a > r)return;
else if (a <= l && r <= b) {
if (bol)tree[k].x = 1;
else tree[k].x = 0;
} else {
if (b <= mid) {
if (tree[k].chl == 0) {
tree[k].chl = tt++;
}
update(a, b, l, mid, tree[k].chl, bol);
} else {
if (tree[k].chr == 0) {
tree[k].chr = tt++;
}
update(a, b, mid + 1, r, tree[k].chr, bol);
}
int sum = 0;
if (tree[k].chl != 0) {
sum += tree[tree[k].chl].x;
}
if (tree[k].chr != 0) {
sum += tree[tree[k].chr].x;
}
tree[k].x = sum;
return;
}
}
int querry(int a, int b, int l, int r, int k) {
if (b < l || a > r) {
return 0;
} else if (a <= l && r <= b) {
return tree[k].x;
} else {
int sum = 0;
if (tree[k].chl != 0) {
sum += querry(a, b, l, mid, tree[k].chl);
}
if (tree[k].chr != 0) {
sum += querry(a, b, mid + 1, r, tree[k].chr);
}
return sum;
}
}
int main() {
f();
scanf("%d%d", &n, &m);
tt = n + m + 1;
for (int i = 0; i < n; i++) {
int t;
scanf("%d", &t);
add(i + 1, t);
if (mp[t] == 0) {
mp[t] = ++tot;
update(i + 1, i + 1, 1, n, tot, 1);
} else {
update(i + 1, i + 1, 1, n, mp[t], 1);
}
}
// debug(sum(1));
while (m--) {
int op;
scanf("%d", &op);
if (op == 1) {
int p, x;
scanf("%d%d", &p, &x);
int t = sum(p) ^sum(p - 1);
update(p, p, 1, n, mp[t], 0);
add(p, t ^ x);
if (mp[x] == 0)mp[x] = ++tot;
update(p, p, 1, n, mp[x], 1);
assert(tt < 5e7);
} else {
int l, r;
scanf("%d%d", &l, &r);
int t = sum(r) ^sum(l - 1);
//debug(t);
if (mp[t] == 0)printf("%d\n", r - l + 1);
else printf("%d\n", r - l + 1 - querry(l, r, 1, n, mp[t]));
}
}
return 0;
}