XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#114708 #1162. 异或 Accepted 100 1768 ms 15712 K C++ 17 / 1.6 K iNx 2024-08-12 15:02:50
显示原始代码 
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>

// #define int long long

using namespace std;
using ll = long long;

constexpr int MAX_N = 3e5 + 7;

int bit[MAX_N];

int n, m;

int lowbit(int x) { return x & (-x); }

void update(int x, int y) {
    for (; x <= n; x += lowbit(x)) bit[x] ^= y;
}

int get(int x) {
    int res = 0;
    for (; x > 0; x -= lowbit(x)) res ^= bit[x];
    return res;
}

struct Node {
    int l, r, idx;

    Node(int _l = 0, int _r = 0, int _idx = 0) : l(_l), r(_r), idx(_idx) {}

    bool operator<(const Node &u) const {
        if (r < u.r)
            return true;
        if (r > u.r)
            return false;
        return l < u.l;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    vector<int> a(n), s(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[i + 1] = a[i] ^ s[i];
    }
    vector<Node> qs;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        --l;
        qs.emplace_back(l, r, i);
    }
    sort(qs.begin(), qs.end());
    vector<int> ans(m);
    int i = 0;
    map<int, int> mp;
    for (auto [l, r, idx] : qs) {
        while (i < n && i < r) {
            if (mp.count(a[i])) {
                update(mp[a[i]], a[i]);
            }
            mp[a[i]] = i + 1;
            update(i + 1, a[i]);
            i++;
        }
        ans[idx] = get(r) ^ get(l) ^ s[r] ^ s[l];
    }
    for (int i = 0; i < m; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：182 ms
内存：15680 KiB

输入文件（xor1.in） 

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>

答案文件（xor1.out） 

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 0
测试点 #2
Accepted
得分：100
用时：199 ms
内存：15712 KiB

输入文件（xor2.in） 

256041
100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2
<5984493 bytes omitted>

答案文件（xor2.out） 

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 0
测试点 #3
Accepted
得分：100
用时：3 ms
内存：352 KiB

输入文件（xor3.in） 

907
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>

答案文件（xor3.out） 

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 0
测试点 #4
Accepted
得分：100
用时：4 ms
内存：280 KiB

输入文件（xor4.in） 

911
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>

答案文件（xor4.out） 

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 0
测试点 #5
Accepted
得分：100
用时：5 ms
内存：388 KiB

输入文件（xor5.in） 

910
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>

答案文件（xor5.out） 

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 0
测试点 #6
Accepted
得分：100
用时：6 ms
内存：352 KiB

输入文件（xor6.in） 

908
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>

答案文件（xor6.out） 

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 0
测试点 #7
Accepted
得分：100
用时：3 ms
内存：352 KiB

输入文件（xor7.in） 

978
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>

答案文件（xor7.out） 

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 0
测试点 #8
Accepted
得分：100
用时：4 ms
内存：332 KiB

输入文件（xor8.in） 

962
299718210 299718210 0 39962428 59943642 559473992 219793354 939117058 159849712 999060700 97907
<17226 bytes omitted>

答案文件（xor8.out） 

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 0
测试点 #9
Accepted
得分：100
用时：5 ms
内存：384 KiB

输入文件（xor9.in） 

935
899154630 939117058 939117058 319699424 319699424 639398848 419605494 659380062 279736996 73930
<17186 bytes omitted>

答案文件（xor9.out） 

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 0
测试点 #10
Accepted
得分：100
用时：4 ms
内存：384 KiB

输入文件（xor10.in） 

935
379643066 0 699342490 219793354 79924856 299718210 219793354 179830926 99906070 79924856 539492
<17019 bytes omitted>

答案文件（xor10.out） 

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 0
测试点 #11
Accepted
得分：100
用时：5 ms
内存：336 KiB

输入文件（xor11.in） 

952
599436420 19981214 839210988 899154630 859192202 0 99906070 179830926 539492778 359661852 21979
<17213 bytes omitted>

答案文件（xor11.out） 

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 0
测试点 #12
Accepted
得分：100
用时：7 ms
内存：408 KiB

输入文件（xor12.in） 

962
59943642 239774568 159849712 379643066 119887284 239774568 559473992 379643066 19981214 6393988
<17270 bytes omitted>

答案文件（xor12.out） 

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 0
测试点 #13
Accepted
得分：100
用时：123 ms
内存：8380 KiB

输入文件（xor13.in） 

293327
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>

答案文件（xor13.out） 

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 0
测试点 #14
Accepted
得分：100
用时：123 ms
内存：8132 KiB

输入文件（xor14.in） 

268065
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>

答案文件（xor14.out） 

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 0
测试点 #15
Accepted
得分：100
用时：123 ms
内存：8268 KiB

输入文件（xor15.in） 

273128
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>

答案文件（xor15.out） 

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 0
测试点 #16
Accepted
得分：100
用时：107 ms
内存：7496 KiB

输入文件（xor16.in） 

256076
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>

答案文件（xor16.out） 

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 0
测试点 #17
Accepted
得分：100
用时：193 ms
内存：8584 KiB

输入文件（xor17.in） 

286020
1714284 1926072 1256742 1856142 2173824 271728 2259738 1616382 1978020 2221776 1566432 13826
<6399775 bytes omitted>

答案文件（xor17.out） 

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 0
测试点 #18
Accepted
得分：100
用时：248 ms
内存：8360 KiB

输入文件（xor18.in） 

293085
1580418 1902096 733266 903096 2211786 699300 763236 721278 2229768 1146852 2149848 2259738 4
<6230057 bytes omitted>

答案文件（xor18.out） 

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 0
测试点 #19
Accepted
得分：100
用时：250 ms
内存：8176 KiB

输入文件（xor19.in） 

289253
2293704 1626372 2283714 1954044 1040958 1056942 2289708 303696 1440558 1228770 2063934 90709
<5964250 bytes omitted>

答案文件（xor19.out） 

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 0
测试点 #20
Accepted
得分：100
用时：174 ms
内存：8256 KiB

输入文件（xor20.in） 

255064
1146852 2093904 1342656 2029968 791208 1110888 1800198 331668 2021976 1730268 1542456 119280
<6096895 bytes omitted>

答案文件（xor20.out） 

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
XJTUOJ Powered by SYZOJ.