| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #31284 | #1162. 异或 | Accepted | 100 | 8318 ms | 39016 K | C++ 11 / 2.6 K | q3540555 | 2020-07-04 10:24:12 |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 3e5 + 10, mxm = 3e5 + 10;
struct sgt {
int n;
ll dta[4 * mxn];
static int kid(int id, int i) { return id * 2 + i; }
void set(int sz) { n = sz; }
void marge(int id) { dta[id] = dta[kid(id, 0)] ^ dta[kid(id, 1)]; }
void build(ll a[], int l = 0, int r = -1, int id = 1);
ll find(int l, int r, int gl = 0, int gr = -1, int id = 1);
void add(int loc, ll val, int l = 0, int r = -1, int id = 1);
} tr;
void sgt::build(ll a[], int l, int r, int id) {
r = r < 0 ? n : r;
if (l + 1 == r)
return dta[id] = 0, void();
int mid = l + r >> 1;
build(a, l, mid, kid(id, 0));
build(a, mid, r, kid(id, 1));
marge(id);
}
ll sgt::find(int l, int r, int gl, int gr, int id) {
gr = gr < 0 ? n : gr;
if (l == gl && r == gr)
return dta[id];
int mid = gl + gr >> 1;
if (r <= mid)
return find(l, r, gl, mid, kid(id, 0));
if (l >= mid)
return find(l, r, mid, gr, kid(id, 1));
return find(l, mid, gl, mid, kid(id, 0)) ^ find(mid, r, mid, gr, kid(id, 1));
}
void sgt::add(int loc, ll val, int l, int r, int id) {
r = r < 0 ? n : r;
if (l > loc || r <= loc)
return;
if (l + 1 == r)
return dta[id] ^= val, void();
int mid = l + r >> 1;
add(loc, val, l, mid, kid(id, 0));
add(loc, val, mid, r, kid(id, 1));
marge(id);
}
struct presum {
ll dta[mxn];
ll &operator[](int loc) { return dta[loc]; }
ll get(int l, int r) const { return dta[r] ^ dta[l]; }
} chi, tot;
map<ll, int> cnt, pre;
int nxt[mxn], ans[mxm];
vector<pair<int, int>> que[mxn];
ll a[mxn];
int main() {
int n, q;
cin >> n;
tr.set(n);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) {
chi[i + 1] = chi[i] ^ a[i];
if (cnt[a[i]])
tot[i + 1] = tot[i], nxt[pre[a[i]]] = i;
else
tot[i + 1] = tot[i] ^ a[i];
pre[a[i]] = i;
++cnt[a[i]];
}
cin >> q;
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
que[l - 1].push_back({ r, i });
}
for (int i = 0; i < n; ++i) {
for (const pair<int, int> &aq : que[i]) {
int r = aq.first, qi = aq.second;
ans[qi] = tot.get(i, r) ^ tr.find(i, r) ^ chi.get(i, r);
}
if (nxt[i])
tr.add(nxt[i], a[i]);
}
for (int i = 0; i < q; ++i) cout << ans[i] << endl;
return 0;
}251838
100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2
<6166055 bytes omitted>0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<852089 bytes omitted>用户输出
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<567998 bytes omitted>系统信息
Exited with return code 0256041
100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2
<5984493 bytes omitted>0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<804650 bytes omitted>用户输出
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<536372 bytes omitted>系统信息
Exited with return code 0907
56 71 13 4 45 57 55 89 12 58 95 99 45 100 42 94 89 94 16 18 55 67 5 68 20 43 51 93 84 92 77 63
<10826 bytes omitted>113
37
35
10
30
69
105
16
64
123
87
73
4
0
91
1
90
94
2
77
118
12
16
48
123
<3772 bytes omitted>用户输出
113
37
35
10
30
69
105
16
64
123
87
73
4
0
91
1
90
94
2
77
118
12
16
48
123
69
66
35
48
65
8
48
58
50
79
44
16
60
122
12
4
112
2
<2799 bytes omitted>系统信息
Exited with return code 0911
79 65 67 71 96 98 41 89 63 100 54 9 66 92 97 89 64 44 2 38 94 94 37 91 17 26 38 13 87 96 5 75 1
<10954 bytes omitted>5
68
32
111
15
52
104
119
29
42
98
104
33
104
23
13
57
16
41
81
5
109
53
6
7
<3840 bytes omitted>用户输出
5
68
32
111
15
52
104
119
29
42
98
104
33
104
23
13
57
16
41
81
5
109
53
6
73
15
109
105
104
92
2
53
47
102
66
83
94
91
85
100
1
<2854 bytes omitted>系统信息
Exited with return code 0910
96 10 58 93 18 79 68 66 20 19 79 50 22 92 79 6 85 16 57 4 81 43 21 39 74 59 34 84 86 39 24 2 6
<10840 bytes omitted>105
19
114
5
48
41
33
108
26
10
108
49
87
48
68
38
110
68
52
4
14
13
120
118
<3759 bytes omitted>用户输出
105
19
114
5
48
41
33
108
26
10
108
49
87
48
68
38
110
68
52
4
14
13
120
118
107
12
35
67
58
76
90
21
58
9
105
87
62
59
41
51
40
<2788 bytes omitted>系统信息
Exited with return code 0908
82 94 2 44 73 45 58 30 18 39 80 54 88 81 37 7 99 59 65 93 22 20 35 57 60 37 46 20 59 88 99 41 3
<11278 bytes omitted>0
60
0
91
79
122
121
78
115
41
103
2
31
59
96
114
23
98
62
45
50
62
122
78
9
<3988 bytes omitted>用户输出
0
60
0
91
79
122
121
78
115
41
103
2
31
59
96
114
23
98
62
45
50
62
122
78
95
96
121
81
61
92
68
111
104
123
119
75
10
104
65
40
<2963 bytes omitted>系统信息
Exited with return code 0978
41 67 43 65 96 23 3 53 34 78 87 67 31 52 74 3 16 45 10 85 96 46 36 0 41 26 85 62 29 0 98 91 47
<10961 bytes omitted>17
80
84
85
54
79
62
124
53
92
84
70
82
98
69
19
39
94
39
117
34
121
89
79
5
<3753 bytes omitted>用户输出
17
80
84
85
54
79
62
124
53
92
84
70
82
98
69
19
39
94
39
117
34
121
89
79
52
0
59
59
113
99
82
39
82
57
111
84
14
86
93
55
90
6
<2789 bytes omitted>系统信息
Exited with return code 0962
299718210 299718210 0 39962428 59943642 559473992 219793354 939117058 159849712 999060700 97907
<17226 bytes omitted>746812074
909717596
495511252
55402154
812639012
0
919969834
79389020
742767238
787403722
<9685 bytes omitted>用户输出
746812074
909717596
495511252
55402154
812639012
0
919969834
79389020
742767238
787403722
945520388
1068797380
233603052
4395848
<8754 bytes omitted>系统信息
Exited with return code 0935
899154630 939117058 939117058 319699424 319699424 639398848 419605494 659380062 279736996 73930
<17186 bytes omitted>934921578
489567608
451179490
711757202
879173416
69610634
818405958
154782278
137133528
31
<9859 bytes omitted>用户输出
934921578
489567608
451179490
711757202
879173416
69610634
818405958
154782278
137133528
310552354
849410002
851616358
364033954
<8911 bytes omitted>系统信息
Exited with return code 0935
379643066 0 699342490 219793354 79924856 299718210 219793354 179830926 99906070 79924856 539492
<17019 bytes omitted>352765180
138762976
649995032
331699740
1003139736
28540058
272635836
693480286
952284874
4
<9684 bytes omitted>用户输出
352765180
138762976
649995032
331699740
1003139736
28540058
272635836
693480286
952284874
425278884
612072688
593203122
68810111
<8746 bytes omitted>系统信息
Exited with return code 0952
599436420 19981214 839210988 899154630 859192202 0 99906070 179830926 539492778 359661852 21979
<17213 bytes omitted>103578644
618951634
383099418
248973264
889950206
51673546
58135816
239774568
597982474
168
<9751 bytes omitted>用户输出
103578644
618951634
383099418
248973264
889950206
51673546
58135816
239774568
597982474
168596210
862628576
780260688
956305864
<8816 bytes omitted>系统信息
Exited with return code 0962
59943642 239774568 159849712 379643066 119887284 239774568 559473992 379643066 19981214 6393988
<17270 bytes omitted>816843836
2171850
710812428
500992326
93317780
619242180
742511584
592153734
211465332
1070
<9659 bytes omitted>用户输出
816843836
2171850
710812428
500992326
93317780
619242180
742511584
592153734
211465332
1070226742
862396096
788304070
455981652
<8726 bytes omitted>系统信息
Exited with return code 0293327
0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0
<4452780 bytes omitted>1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
1
0
<814433 bytes omitted>用户输出
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1
0
1
0
<542894 bytes omitted>系统信息
Exited with return code 0268065
0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0
<4495021 bytes omitted>1
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
1
0
0
0
1
0
1
1
1
0
<838052 bytes omitted>用户输出
1
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
1
0
0
0
1
0
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
0
0
0
0
1
0
0
0
1
1
0
1
0
1
1
1
0
0
0
<558640 bytes omitted>系统信息
Exited with return code 0273128
1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0
<4438785 bytes omitted>0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
1
1
1
1
1
0
0
0
1
0
<822920 bytes omitted>用户输出
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
1
1
1
1
1
0
0
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
1
1
0
<548552 bytes omitted>系统信息
Exited with return code 0256076
0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1
<4077145 bytes omitted>1
1
1
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
1
1
0
0
0
1
1
0
1
0
1
1
1
1
1
<756695 bytes omitted>用户输出
1
1
1
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
1
1
0
0
0
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
0
0
1
1
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
0
<504402 bytes omitted>系统信息
Exited with return code 0286020
1714284 1926072 1256742 1856142 2173824 271728 2259738 1616382 1978020 2221776 1566432 13826
<6399775 bytes omitted>3913446
3562702
1973544
520860
1866136
337592
978922
1314168
3757208
2380906
1135324
3703
<2605049 bytes omitted>用户输出
3913446
3562702
1973544
520860
1866136
337592
978922
1314168
3757208
2380906
1135324
3703996
2417332
2620928
1251534
2427410
193
<2306731 bytes omitted>系统信息
Exited with return code 0293085
1580418 1902096 733266 903096 2211786 699300 763236 721278 2229768 1146852 2149848 2259738 4
<6230057 bytes omitted>3945724
4091218
2106936
3698428
65340
642284
3473038
1346446
3241504
4085906
2386892
3958
<2465891 bytes omitted>用户输出
3945724
4091218
2106936
3698428
65340
642284
3473038
1346446
3241504
4085906
2386892
3958312
3243784
2385752
4135310
1387094
197
<2183530 bytes omitted>系统信息
Exited with return code 0289253
2293704 1626372 2283714 1954044 1040958 1056942 2289708 303696 1440558 1228770 2063934 90709
<5964250 bytes omitted>2678284
1217318
1450570
3253324
753876
1842350
1581642
4140122
4050490
1114512
3836554
23
<2321125 bytes omitted>用户输出
2678284
1217318
1450570
3253324
753876
1842350
1581642
4140122
4050490
1114512
3836554
2351900
4169700
4021638
87586
1680646
290
<2055296 bytes omitted>系统信息
Exited with return code 0255064
1146852 2093904 1342656 2029968 791208 1110888 1800198 331668 2021976 1730268 1542456 119280
<6096895 bytes omitted>239536
4038706
793690
1566870
4190844
3042696
3755022
469656
3713758
2273578
1261770
3776
<2579881 bytes omitted>用户输出
239536
4038706
793690
1566870
4190844
3042696
3755022
469656
3713758
2273578
1261770
3776234
430010
3348450
1309964
340764
29665
<2284425 bytes omitted>系统信息
Exited with return code 0