QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277267#5214. 树状数组james1BadCreeper100 ✓966ms210556kbC++142.3kb2023-12-06 17:11:462023-12-06 17:11:46

Judging History

你现在查看的是最新测评结果

  • [2023-12-06 17:11:46]
  • 评测
  • 测评结果:100
  • 用时:966ms
  • 内存:210556kb
  • [2023-12-06 17:11:46]
  • 提交

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