QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#276021 | #5075. Fenwick Tree | rageOfThunder# | AC ✓ | 20ms | 4388kb | C++14 | 1.7kb | 2023-12-05 14:47:16 | 2023-12-05 14:47:16 |
Judging History
answer
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T &x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T &x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 1e5 + 10;
int n, ans, t0[N], t1[N];//, t[N];
// vector <int> v[N];
string st;
// void add(int x, int y) {
// for (; x <= n; x += x & -x) t[x] += y;
// }
// int query(int x) {
// int s = 0;
// for (; x; x -= x & -x) s += t[x];
// return s;
// }
void zhk() {
ans = 0;
cin >> n >> st; st = ' ' + st;
F(i, 1, n) t0[i] = t1[i] = 0;
F(i, 1, n) {
int id = i + (i & -i);
if (id <= n) {
t0[id] += st[i] == '0';
t1[id] += st[i] == '1';
}
}
F(i, 1, n) {
if (st[i] == '0') {
if (t1[i] == 1) ans++;
} else {
if (t1[i] == 0) ans++;
}
}
cout << ans << '\n';
// int s = 0;
// F(i, 1, n) t[i] = 0;
// F(i, 1, n) {
// if (st[i] == '0') {
// if (t[i]) add(i, -t[i]), s++;
// } else {
// if (!t[i]) add(i, 1), s++;
// }
// // F(j, 1, n) cout << t[j] << ' '; cout << '\n';
// }
// cout << s << '\n';
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int _ = 1;
cin >> _;
while (_--) zhk();
return 0;
}
/* why?
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3436kb
input:
3 5 10110 5 00000 5 11111
output:
3 0 3
result:
ok 3 number(s): "3 0 3"
Test #2:
score: 0
Accepted
time: 17ms
memory: 3440kb
input:
100000 10 0000000000 10 0000000100 10 0000000000 10 1000000000 10 0000010000 10 0000000000 10 0000000000 10 0000000000 10 0100000000 10 0000000000 10 0000000001 10 0000001000 10 0000000000 10 0000000000 10 0000000001 10 0000100000 10 0010000000 10 0000000000 10 0010000000 10 0000000001 10 0000000000...
output:
0 1 0 2 2 0 0 0 2 0 1 2 0 0 1 2 2 0 2 1 0 0 2 2 2 0 2 2 2 0 2 2 0 0 2 2 0 0 2 0 2 2 0 0 0 0 0 0 0 2 2 2 2 0 1 0 2 2 0 2 2 0 2 2 0 1 0 2 0 0 2 2 0 0 0 1 2 0 2 0 0 0 0 2 2 0 0 0 0 0 0 2 0 2 2 0 2 2 2 0 0 0 0 0 0 0 1 0 0 0 2 0 2 0 0 0 2 0 2 0 0 2 0 0 0 1 0 0 1 2 0 0 2 0 2 0 0 2 0 2 0 0 0 2 0 0 2 2 1 0 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 19ms
memory: 3520kb
input:
100000 10 0000001010 10 1110010000 10 0100010000 10 0001010011 10 0100001001 10 0010100000 10 0101000000 10 0100110100 10 1000001010 10 1000101001 10 1000000011 10 0000000000 10 0100011001 10 1000100101 10 0110101000 10 1000110100 10 0011100000 10 1001000000 10 0111001100 10 1100000100 10 1100110000...
output:
4 4 4 3 5 4 2 3 6 7 3 0 5 6 6 3 4 4 3 3 4 2 4 0 3 3 2 2 0 4 2 2 2 2 4 4 2 2 5 5 2 3 0 4 2 6 6 3 3 0 4 5 4 2 0 6 4 7 3 0 2 2 2 1 4 2 2 5 3 0 4 0 0 4 5 0 0 2 5 3 2 4 1 0 2 4 3 2 1 2 2 2 4 2 5 3 3 1 2 4 0 0 2 5 4 2 4 0 5 7 5 2 7 3 2 4 4 5 0 3 4 4 2 2 0 4 2 0 4 4 9 2 2 5 6 2 6 4 2 0 5 2 1 2 4 6 6 0 2 1 ...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 20ms
memory: 3556kb
input:
100000 10 0000011010 10 1011001101 10 1010111001 10 1101010010 10 0010011110 10 0100000101 10 1111011011 10 0101110010 10 1111010010 10 0000101011 10 0101111000 10 1000001000 10 1000001110 10 0010111111 10 0000000000 10 1001011010 10 0110011010 10 1101110101 10 1011011011 10 1101011101 10 0001000000...
output:
4 5 7 4 6 4 5 4 5 5 3 4 5 5 0 7 6 3 6 4 2 2 5 0 3 5 5 0 2 6 6 8 7 0 4 6 0 6 6 3 2 5 2 2 2 6 5 3 0 1 0 2 7 6 3 5 4 2 3 2 6 3 6 4 4 6 2 0 2 6 3 4 4 7 4 2 5 2 3 6 2 4 1 2 5 7 4 5 6 2 4 2 3 4 0 4 0 4 2 4 3 4 2 0 4 1 2 6 6 2 3 0 5 2 1 6 6 5 4 0 8 4 6 3 4 2 5 2 5 5 3 4 4 6 6 2 4 6 4 4 4 0 4 5 2 7 9 7 3 5 ...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 3ms
memory: 3444kb
input:
10000 100 0000000000000000000000010000000000100001000000000000000001010000100000000000000000000000000000100000 100 0001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000 100 01000101000000000000000000000000000001000000010000000000000000000000000000000000...
output:
12 4 10 4 4 8 4 17 2 14 11 18 2 6 4 12 10 2 4 8 8 10 11 4 9 10 18 11 6 10 16 9 8 10 8 2 0 2 0 6 10 10 13 6 16 8 6 14 4 0 0 16 8 6 13 4 0 10 8 10 20 10 6 14 8 14 14 10 16 0 4 8 13 14 17 8 4 16 8 12 10 14 6 4 4 4 10 10 5 11 18 8 14 0 18 8 15 4 10 4 13 16 12 18 0 18 6 16 8 7 16 10 8 17 14 4 2 10 16 6 1...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 3ms
memory: 3504kb
input:
10000 100 0000101000000010000001000010000010001000010101000100000000010010000100000000001001000001010010001000 100 1010100000100000111000100000000000010000000000101011100000000001000000000000001001000101000010000000 100 00000000000000000000000000000000000000000000000000000000000000000000000000000010...
output:
34 31 2 24 28 25 4 47 12 20 39 32 11 31 37 44 22 29 35 20 31 16 15 31 23 24 10 33 35 25 37 25 37 35 17 38 32 26 39 36 24 39 41 18 37 6 46 8 25 34 12 33 16 15 29 33 38 35 39 6 13 22 34 28 38 23 6 23 36 14 30 31 33 13 9 47 35 42 40 25 23 40 33 18 17 8 39 8 23 35 8 34 41 34 30 20 35 20 25 45 22 30 34 2...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 4ms
memory: 3492kb
input:
10000 100 0011000101011111100110001000100000011110100011101010010000110011010011110001111110000110100100001001 100 0010000000000000000001000000000000000000000000001000100000000000000000000000000000000000000000000010 100 10101011110111011010111101100110101011111111111110111010110101111011100011101110...
output:
47 10 55 48 37 45 27 50 52 12 41 36 25 32 43 49 26 16 42 47 6 42 44 39 8 45 46 52 39 34 19 37 47 48 50 13 37 48 46 14 23 39 37 40 46 45 8 44 39 24 21 45 35 25 27 44 31 57 14 57 43 31 41 36 34 42 53 46 37 40 38 31 44 42 54 4 6 31 21 46 51 38 44 50 41 2 39 50 41 34 42 44 35 34 48 7 31 52 10 39 44 34 6...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 4ms
memory: 3464kb
input:
1000 1000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0 110 122 105 92 50 34 139 90 62 22 100 64 92 130 4 57 120 2 13 134 58 55 102 148 64 154 143 40 26 90 89 114 2 40 126 137 70 92 12 16 70 73 139 2 20 150 88 123 34 36 78 124 58 10 65 0 120 97 96 144 20 108 132 130 98 84 64 93 146 42 130 0 95 20 60 176 128 44 120 0 99 148 74 62 65 42 64 169 155 4 120 ...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 6ms
memory: 3452kb
input:
1000 1000 00011111000010001011010010000010101011110011001000001010000001010011000100111000000000010000001011000101000000100001010000000011011000010100110000101100010000110010000010010100100100010001010110000000110110100100100010000111000010110111100000010001111000100000011010010000101001011110011010...
output:
381 329 210 362 281 260 306 358 348 415 384 360 357 403 395 44 169 359 369 315 280 316 258 30 260 140 404 203 96 392 160 394 362 376 374 349 172 399 407 65 157 28 40 179 336 372 316 279 251 80 251 218 346 391 382 383 368 189 395 84 253 68 331 376 218 287 226 82 149 246 380 419 336 42 247 404 271 132...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 6ms
memory: 3452kb
input:
1000 1000 00100001010000111001111101011111110111110000100110111010111111101110101010110100001111100011101001110100100110010000110110111101000011111100001110000010111111011011011011111001000101100010000100000010111111101010111110101110110110111001111000100011000010010010111001111110000101001000100111...
output:
467 436 171 481 487 246 245 415 470 393 455 470 382 416 6 460 438 156 416 484 260 404 396 298 52 365 110 38 254 448 159 28 434 436 376 349 467 466 10 398 408 14 197 311 411 465 8 300 452 159 381 130 243 457 395 257 465 453 40 278 400 435 474 444 240 416 439 416 464 324 447 431 179 478 428 285 334 30...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 4ms
memory: 3660kb
input:
100 10000 00000001000000000101000000000000000000000000000000001000000000000000000000000010000000000010000000000000000001000001000000000010000000000100000000000000000000000000000000000000000100010000010000000010000100000001000000000000000100000000000000000010000000000000000000001001000000000001100000...
output:
1483 1213 2 1045 691 1363 1282 1495 1183 821 825 813 90 964 633 1475 1527 920 152 364 263 292 118 228 453 1113 134 361 1571 1435 1443 746 964 1600 868 954 714 1393 1271 1277 1477 949 1516 1059 607 286 482 792 1278 114 887 519 1344 1433 425 1415 394 893 198 618 1144 605 1275 1555 548 536 576 971 987 ...
result:
ok 100 numbers
Test #12:
score: 0
Accepted
time: 6ms
memory: 3552kb
input:
100 10000 00011000000010000101001110011000100001100110111000101100011010010010000011000010111010000111100000101010010100100000000000000000001000010100010000000110010000001101000000101110110010000011001000001010010001000000010000100100100101001000101101010001001000000100011010110000100000000001000100...
output:
3535 2671 3555 1183 3730 2432 3376 564 231 3769 3164 2570 2170 3588 1720 649 716 3749 2360 3185 130 3984 3193 3338 3827 2806 3880 2198 3808 3759 2313 1462 1345 4105 2849 1038 2287 3037 671 1796 1258 1621 2204 719 3302 2069 3419 3804 1270 3972 3130 3704 2530 3873 252 525 1693 3568 1561 2570 1014 2751...
result:
ok 100 numbers
Test #13:
score: 0
Accepted
time: 3ms
memory: 3592kb
input:
100 10000 00011111111100111100101101111111111101011000101000011111111101110011000110101111110010111100111110011110110001100100011001101110101101011110111011111000011100011010011011101011000110111011111000010110110001110001111110111010111101100010011001111111101001011011111011111100011111011110100001...
output:
4754 4000 3780 4647 4238 4515 4592 4554 1744 4090 3945 4592 2748 4414 4635 2256 1692 4438 2935 1410 4375 3001 3710 3475 4309 3242 4329 4692 3924 2517 3541 4078 947 4458 4621 4312 744 2983 261 4561 3130 4574 3499 3549 3239 1083 1051 1742 4336 2999 4138 3837 4710 3758 4534 2874 4479 4086 1439 3405 457...
result:
ok 100 numbers
Test #14:
score: 0
Accepted
time: 4ms
memory: 4388kb
input:
10 100000 00000000000000000000000000000000000000000000000001000001000000000000000000000010000000000000000101010000000000000000000000100000000001000000001000000000000000010001000000000010000101000100000000000000000000000000000000000000000001000000000011000000000000000000000000000000000000000000000000...
output:
8584 4084 1746 964 8834 711 5993 6493 3835 1710
result:
ok 10 numbers
Test #15:
score: 0
Accepted
time: 5ms
memory: 4352kb
input:
10 100000 00000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
3334 2611 9369 10529 14744 12414 340 14662 14868 3104
result:
ok 10 numbers
Test #16:
score: 0
Accepted
time: 6ms
memory: 4336kb
input:
10 100000 00000000000000010000000100000000000000001010000000000000000100000000110001000001100000001000000000001000000010000000000000000010010000001000000000000100001100000010000000011000010100010000011000000000000000010100010101000000000000001000000100010010000000001000000001001010000001000000000000...
output:
22727 36918 38266 39589 17491 22464 31990 11824 37582 39861
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 4336kb
input:
10 100000 10000001100000100000000000000001000110110000110011000100000000000000000000000000000101001000000001000000000000100001010000000000101000000010001001001000010000000000100010000001000000000100000110010100001010000100010010001001100100000100000010000100000000000000000000000001010000000000010001...
output:
24511 28732 3286 43353 39312 23907 14861 29009 45012 41944
result:
ok 10 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 4388kb
input:
10 100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #19:
score: 0
Accepted
time: 4ms
memory: 4328kb
input:
10 100000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
50000 50000 50000 50000 50000 50000 50000 50000 50000 50000
result:
ok 10 numbers