QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277267 | #5214. 树状数组 | james1BadCreeper | 100 ✓ | 966ms | 210556kb | C++14 | 2.3kb | 2023-12-06 17:11:46 | 2023-12-06 17:11:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 100005, P = 998244353;
int n, q, cnt;
int rt[N * 4];
struct node {
int ls, rs, v;
} T[N * 400];
inline i64 poww(i64 a, i64 b) {
i64 r = 1;
for (; b; b >>= 1, a = a * a % P) if (b & 1) r = r * a % P;
return r;
}
inline i64 mul(i64 p, i64 q) {
i64 r = p * q % P;
r = (r + (1 - p) * (1 - q) % P) % P;
return (r + P) % P;
}
void changey(int &o, int l, int r, int x, int y, i64 p) {
if (!o) o = ++cnt, T[o].v = 1;
if (x <= l && y >= r) return T[o].v = mul(T[o].v, p), void();
int mid = l + r >> 1;
if (x <= mid) changey(T[o].ls, l, mid, x, y, p);
if (mid < y) changey(T[o].rs, mid + 1, r, x, y, p);
}
void changex(int o, int l, int r, int lx, int rx, int ly, int ry, i64 p) {
if (lx <= l && rx >= r) return changey(rt[o], 1, n, ly, ry, p);
int mid = (l + r) >> 1;
if (lx <= mid) changex(o << 1, l, mid, lx, rx, ly, ry, p);
if (mid < rx) changex(o << 1 | 1, mid + 1, r, lx, rx, ly, ry, p);
}
i64 asky(int o, int l, int r, int x) {
if (!o) return 1;
if (l == r) return T[o].v;
int mid = (l + r) >> 1;
if (x <= mid) return mul(T[o].v, asky(T[o].ls, l, mid, x));
return mul(T[o].v, asky(T[o].rs, mid + 1, r, x));
}
i64 askx(int o, int l, int r, int x, int y) {
if (l == r) return asky(rt[o], 1, n, y);
int mid = l + r >> 1;
if (x <= mid) return mul(askx(o << 1, l, mid, x, y), asky(rt[o], 1, n, y));
return mul(askx(o << 1 | 1, mid + 1, r, x, y), asky(rt[o], 1, n, y));
}
int main(void) {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
while (q--) {
int op, l, r; cin >> op >> l >> r;
if (op == 1) {
i64 p = poww(r - l + 1, P - 2);
if (l > 1)
changex(1, 0, n, 1, l - 1, l, r, (1 - p + P) % P),
changex(1, 0, n, 0, 0, 1, l - 1, 0);
if (r < n)
changex(1, 0, n, l, r, r + 1, n, (1 - p + P) % P),
changex(1, 0, n, 0, 0, r + 1, n, 0);
changex(1, 0, n, l, r, l, r, (1 - 2 * p + P) % P);
changex(1, 0, n, 0, 0, l, r, p);
} else cout << askx(1, 0, n, l - 1, r) << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 3356kb
input:
5 10 1 4 5 1 1 2 2 3 4 2 3 5 2 1 4 2 1 4 1 2 4 2 3 5 2 1 3 1 1 2
output:
499122177 499122177 499122177 499122177 499122177 332748118
result:
ok 6 numbers
Test #2:
score: 10
Accepted
time: 1ms
memory: 3476kb
input:
50 50 2 13 47 1 17 33 2 22 48 2 12 48 2 1 49 1 42 42 1 43 48 1 24 36 1 7 33 1 24 27 1 4 15 2 1 23 2 1 6 1 14 40 2 17 49 1 10 19 1 10 16 2 1 25 1 9 35 2 10 13 2 40 47 2 1 19 2 1 12 2 1 36 1 27 48 1 13 26 2 1 15 2 1 29 1 8 49 2 35 46 2 33 50 2 1 23 1 9 39 1 9 12 1 11 26 1 1 5 2 1 41 2 1 32 2 1 45 2 1 ...
output:
1 58720257 1 0 130489458 582309206 442294824 809903640 764642525 178698064 86075608 240970149 944208334 531916842 601084191 771574464 402015497 676130263 36731936 794697613 523610134 67596158 984427464 974473803 381206706 0 637835356
result:
ok 27 numbers
Test #3:
score: 10
Accepted
time: 1ms
memory: 3476kb
input:
50 50 1 6 48 1 40 41 2 1 38 1 12 19 2 46 49 2 10 14 2 15 47 1 33 40 2 43 48 2 6 16 2 12 46 1 4 46 2 1 39 1 22 23 1 19 30 1 37 38 2 17 41 1 6 39 2 2 10 1 21 36 2 1 12 1 39 42 1 18 26 1 39 47 2 2 3 2 1 4 2 1 50 1 19 32 1 13 49 2 28 35 1 43 50 1 14 28 2 1 13 2 1 43 1 3 8 2 1 8 2 27 49 2 1 6 1 24 32 2 1...
output:
487514685 487514685 856052571 856052571 975029369 490416558 975029369 252058049 499122177 476415318 731653121 1 510729669 0 5404218 225201319 203434499 483984271 169811274 483984271 396988660 499122177 499122177 505507228 271127225 955477964 715277724 724002175
result:
ok 28 numbers
Test #4:
score: 10
Accepted
time: 10ms
memory: 8828kb
input:
3000 3000 1 2930 2931 1 2934 2960 1 2958 2959 1 2907 2908 1 2916 2940 1 2935 2942 1 2913 2972 1 2929 2984 1 2912 2913 1 2938 2939 1 2928 2982 1 2975 2976 1 2963 2964 1 2937 2951 1 2939 2979 1 2945 2946 1 2968 2993 1 2950 2970 1 2996 2997 1 2929 2952 1 2977 2978 1 2976 2977 1 2952 2970 1 2936 2983 1 ...
output:
499122177 126891706 360016686 226152091 428320779 425836760 420590547 360016686 499122177 103356395 634572362 141535362 645717502 226152091 499122177 443084963 499122177 539899668 499122177 499122177 122654492 512869152 939591492 956839002 369663921 438096993 939591492 997438593 499122177 406194069 ...
result:
ok 1768 numbers
Test #5:
score: 10
Accepted
time: 7ms
memory: 6980kb
input:
3000 3000 1 2923 2933 1 2924 2925 1 2950 2989 1 2971 2972 1 2904 2970 1 2912 2913 1 2968 2969 1 2903 2904 1 2934 2935 1 2928 2929 1 2937 2986 1 2929 2964 1 2975 2976 1 2906 2968 1 2987 2988 1 2993 2994 1 2912 2935 1 2913 2991 1 2947 2956 1 2962 2963 1 2913 2915 1 2958 2959 1 2968 2973 1 2985 2999 1 ...
output:
499122177 499122177 499122177 198533075 499122177 499122177 521449317 532612887 937483089 499122177 499122177 499122177 499122177 879681651 172092882 499122177 664906556 541475081 455681480 499122177 407770097 499122177 110852426 171480151 499122177 499122177 499122177 635928571 499122177 499122177 ...
result:
ok 1802 numbers
Test #6:
score: 10
Accepted
time: 918ms
memory: 210072kb
input:
100000 100000 1 89088 93392 1 91302 95813 1 92585 92586 1 91247 91248 1 90231 90232 1 82634 82635 1 84794 84795 1 82976 91226 1 92602 99162 1 80375 86045 1 95860 95861 1 80619 80620 1 92287 97686 1 82662 86941 1 80057 89342 1 83144 83145 1 96149 96150 1 80142 80616 1 82591 90125 1 88102 97414 1 8051...
output:
499122177 499122177 499122177 499122177 936701003 499122177 84939443 323913486 499122177 499122177 499122177 580237851 166719108 226787210 499122177 499122177 358921865 499122177 233197118 499122177 499122177 499122177 564031502 499122177 322577497 499122177 159082042 968633340 499122177 499122177 4...
result:
ok 62035 numbers
Test #7:
score: 10
Accepted
time: 915ms
memory: 210456kb
input:
100000 100000 1 83336 93959 1 84757 84758 1 90676 93742 1 80824 80825 1 81849 89541 1 85659 96918 1 97621 97622 1 93643 93644 1 93464 99523 1 87522 87523 1 82954 82955 1 82902 89012 1 99501 99502 1 94989 94990 1 83392 91757 1 84724 84725 1 82212 85908 1 80500 81062 1 82030 82031 1 84784 93374 1 8884...
output:
663666502 499122177 630720162 499122177 686154283 494053514 731816966 499122177 499122177 499122177 935271408 757579533 397691303 154879167 499122177 499122177 156240057 499122177 499122177 499122177 499122177 953812002 499122177 499122177 499122177 436737768 890813668 499122177 427054283 499122177 ...
result:
ok 62054 numbers
Test #8:
score: 10
Accepted
time: 911ms
memory: 209632kb
input:
100000 100000 1 89568 89569 1 82854 91182 1 86464 86465 1 80604 96936 1 90681 90682 1 95943 97129 1 96365 96462 1 80022 80023 1 82862 95367 1 86847 92316 1 95642 95643 1 92725 98528 1 99696 99697 1 87850 87851 1 93364 93365 1 82612 88906 1 81906 81907 1 83249 83878 1 90229 94006 1 88951 88952 1 8933...
output:
499122177 139331710 499122177 782466725 499122177 683070831 918123230 499122177 331495294 499122177 499122177 499122177 499122177 691105999 499122177 350277424 990098573 499122177 889554586 499122177 499122177 367935880 499122177 906106547 630448624 499122177 482803556 600358533 499122177 817747559 ...
result:
ok 61978 numbers
Test #9:
score: 10
Accepted
time: 966ms
memory: 210556kb
input:
100000 100000 1 94549 96339 1 80497 83646 1 89698 91274 1 83443 92198 1 80806 96866 1 96238 96239 1 90092 90093 1 83438 83439 1 84629 84630 1 80964 84916 1 81012 86693 1 89696 89697 1 95772 96465 1 93882 93883 1 81796 88375 1 89446 99376 1 86243 99626 1 90974 90975 1 90252 90253 1 83780 86329 1 8522...
output:
658142195 47152229 499122177 967485825 804296294 154409163 3883995 989790042 499122177 499122177 45850589 499122177 956499159 499122177 541441169 499122177 482875110 352205786 427060182 340268679 499122177 980068979 828524445 386533448 516518861 311914457 499122177 499122177 696801468 499122177 6770...
result:
ok 61893 numbers
Test #10:
score: 10
Accepted
time: 903ms
memory: 209504kb
input:
100000 100000 1 83897 83898 1 82522 98019 1 94764 94765 1 80498 82796 1 85934 85935 1 81305 81306 1 83356 88287 1 84226 84227 1 84240 84241 1 94785 99222 1 83508 91703 1 96921 96922 1 82779 82780 1 90455 90456 1 87143 87144 1 88815 88816 1 81652 91837 1 91611 96550 1 92298 92299 1 83774 95129 1 8792...
output:
101949989 935752070 480351940 658408109 499122177 762600920 509133755 499122177 499122177 748192598 499122177 617281151 499122177 16198420 661396037 499122177 499122177 71296140 59118253 458830724 756894947 116543802 47602388 499122177 225291291 132196166 149875976 499122177 499122177 534020183 2225...
result:
ok 62183 numbers
Extra Test:
score: 0
Extra Test Passed