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>| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #30587 | #1162. 异或 | Time Limit Exceeded | 0 | 20653 ms | 537564 K | C++ 11 / 1.7 K | nocriz🦆 | 2020-07-03 11:12:29 |
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdlib>
#include <string>
#include <bitset>
#include <iomanip>
#include <deque>
#include <utility>
#define INF 1000000000
#define fi first
#define se second
#define N 1000005
#define P 1000000007
#define debug(x) cerr << #x << "=" << x << endl
#define MP(x, y) make_pair(x, y)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int c[N], now, sum, a[N], b[N], ans[N], nxt[N], n;
map<int, int> vis, pre;
vector<pii> Q[N];
void Add(int x, int w) {
for (; x <= n; x += x & -x) c[x] ^= w;
}
int Get(int x) {
int s = 0;
for (; x; x -= x & -x) s ^= c[x];
return s;
}
int main() {
int i, m, ql, qr, j;
freopen("xor.in", "r", stdin);
freopen("xor.out", "w", stdout);
cin >> n;
now = 0;
for (i = 1; i <= n; i++) {
scanf("%d", &a[i]);
vis[a[i]]++;
nxt[pre[a[i]]] = i;
pre[a[i]] = i;
if (vis[a[i]] > 1)
now ^= a[i];
b[i] = now;
// debug(b[i]);
}
cin >> m;
for (i = 1; i <= m; i++) {
scanf("%d%d", &ql, &qr);
Q[ql].push_back(MP(qr, i));
}
for (i = 1; i <= n; i++) {
// debug(sum);
for (j = 0; j < Q[i].size(); j++) ans[Q[i][j].se] = Get(Q[i][j].fi) ^ b[Q[i][j].fi];
ql = nxt[i];
if (ql) {
sum ^= a[i];
Add(ql, a[i]);
}
}
for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
// davidlee1999WTK 2016/
// srO myk Orz
// ios::sync_with_stdio(false);
//#pragma comment(linker, "/STACK:102400000,102400000") compiler c++,not g++
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>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>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>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>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>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>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>962
299718210 299718210 0 39962428 59943642 559473992 219793354 939117058 159849712 999060700 97907
<17226 bytes omitted>935
899154630 939117058 939117058 319699424 319699424 639398848 419605494 659380062 279736996 73930
<17186 bytes omitted>935
379643066 0 699342490 219793354 79924856 299718210 219793354 179830926 99906070 79924856 539492
<17019 bytes omitted>952
599436420 19981214 839210988 899154630 859192202 0 99906070 179830926 539492778 359661852 21979
<17213 bytes omitted>962
59943642 239774568 159849712 379643066 119887284 239774568 559473992 379643066 19981214 6393988
<17270 bytes omitted>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>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>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>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>286020
1714284 1926072 1256742 1856142 2173824 271728 2259738 1616382 1978020 2221776 1566432 13826
<6399775 bytes omitted>293085
1580418 1902096 733266 903096 2211786 699300 763236 721278 2229768 1146852 2149848 2259738 4
<6230057 bytes omitted>289253
2293704 1626372 2283714 1954044 1040958 1056942 2289708 303696 1440558 1228770 2063934 90709
<5964250 bytes omitted>