XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#8019 #1053. nocriz与队列计算机 Accepted 100 1627 ms 35468 K C++ 11 (NOI) / 2.0 K nocriz🦆 2019-07-01 14:26:45
显示原始代码 
#include <set>
#include <queue>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(x) cerr << #x << '=' << x << endl
#define set0(x) memset(x, 0, sizeof(x))
#define mid ((l + r) / 2)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
template <typename T>
void read(T &x) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while (!isdigit(ch)) {
        if (ch == '-')
            f *= -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}

const int N = 500050;
int mod = 998244353;
inline int mul(int x, int y) { return 1ll * x * y % mod; }
int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
int sub(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
int sq(int x) { return 1ll * x * x % mod; }
int pow(int a, int b) { return b == 0 ? 1 : (b & 1 ? mul(a, sq(pow(a, b / 2))) : sq(pow(a, b / 2))); }

pii value[4 * N];
int typ[N], val[N];
pii mulp(pii a, pii b) { return make_pair(mul(a.first, b.first), add(mul(a.second, b.first), b.second)); }
void build_tree(int id, int l, int r, int p) {
    if (l == r) {
        if (typ[l] == 0) {
            value[id] = make_pair(val[l], 0);
        } else {
            value[id] = make_pair(1, val[l]);
        }
        return;
    }
    if (p <= mid || p == -1)
        build_tree(id * 2, l, mid, p);
    if (p > mid || p == -1)
        build_tree(id * 2 + 1, mid + 1, r, p);
    value[id] = mulp(value[id * 2], value[id * 2 + 1]);
}
pii query(int id, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return value[id];
    }
    pii ans = make_pair(1, 0);
    if (ql <= mid)
        ans = mulp(ans, query(id * 2, l, mid, ql, qr));
    if (qr > mid)
        ans = mulp(ans, query(id * 2 + 1, mid + 1, r, ql, qr));
    return ans;
}

int n, q, op, po, l, r, x;
int main() {
    read(n);
    read(q);
    for (int i = 1; i <= n; i++) {
        read(typ[i]);
        read(val[i]);
    }
    build_tree(1, 1, n, -1);
    for (int t = 1; t <= q; t++) {
        read(op);
        if (op == 0) {
            read(po);
            read(typ[po]);
            read(val[po]);
            build_tree(1, 1, n, po);
        } else {
            read(l);
            read(r);
            read(x);
            pii cc = query(1, 1, n, l, r);
            cout << add(mul(x, cc.first), cc.second) << "\n";
        }
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：25 ms
内存：31524 KiB

输入文件（D1.in） 

5 5
0 858714488
1 532767806
1 780285257
1 125875467
0 802208893
1 5 5 369932640
0 2 0 601931983
0 1 
<44 bytes omitted>

答案文件（D1.out） 

455134627
793913007

用户输出 

455134627
793913007

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：27 ms
内存：31584 KiB

输入文件（D2.in） 

15 15
0 897135375
1 358432579
1 602917765
1 217421102
1 376580608
0 538599413
1 371811698
0 31196545
<337 bytes omitted>

答案文件（D2.out） 

216377874
540305084
530317326
574404455
113299621
517430644
922267438
982379975

用户输出 

216377874
540305084
530317326
574404455
113299621
517430644
922267438
982379975

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：25 ms
内存：31564 KiB

输入文件（D3.in） 

500 500
1 159418858
0 651920937
0 652100067
0 365475059
1 228562079
0 344014735
0 250315824
1 793250
<15217 bytes omitted>

答案文件（D3.out） 

707376858
265550697
849351982
390613978
103912941
687906530
356908539
36659338
152015080
756027342
8
<2579 bytes omitted>

用户输出 

707376858
265550697
849351982
390613978
103912941
687906530
356908539
36659338
152015080
756027342
807972171
811550850
623840240
<2551 bytes omitted>

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：25 ms
内存：31484 KiB

输入文件（D4.in） 

1000 1000
1 432968930
1 146613541
0 363915141
1 271750910
0 359885055
1 909324639
1 889068353
0 5483
<30657 bytes omitted>

答案文件（D4.out） 

115545442
166879639
920923309
401851623
733801174
83212102
953449873
662379019
877594392
944572172
3
<5196 bytes omitted>

用户输出 

115545442
166879639
920923309
401851623
733801174
83212102
953449873
662379019
877594392
944572172
364318626
770747334
813347441
<5168 bytes omitted>

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：29 ms
内存：31588 KiB

输入文件（D5.in） 

5000 5000
0 327340172
1 264347742
1 872019940
1 345426744
1 150595861
0 776941713
0 864167311
0 8410
<160281 bytes omitted>

答案文件（D5.out） 

139358580
904180821
713988600
856405035
663585708
100355385
809976690
314807431
37300417
235597211
3
<24919 bytes omitted>

用户输出 

139358580
904180821
713988600
856405035
663585708
100355385
809976690
314807431
37300417
235597211
307977561
924083413
340399106
<24891 bytes omitted>

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：47 ms
内存：31612 KiB

输入文件（D6.in） 

20000 20000
0 387357108
0 132484258
0 247420303
0 714542477
1 817132850
0 456496538
0 37437007
0 802
<662826 bytes omitted>

答案文件（D6.out） 

144911785
286263280
93254608
665909538
12385449
807044434
778201578
16567320
897980760
505412350
536
<98964 bytes omitted>

用户输出 

144911785
286263280
93254608
665909538
12385449
807044434
778201578
16567320
897980760
505412350
536336893
251953509
245778939
7
<98936 bytes omitted>

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：104 ms
内存：31952 KiB

输入文件（D7.in） 

50000 50000
1 832782475
1 350577985
1 195880998
1 732850761
0 75656777
0 654099248
1 460552450
0 753
<1677665 bytes omitted>

答案文件（D7.out） 

876860669
874867572
878573589
637380411
940727165
572409047
416621795
63841579
351397071
183829147
2
<248190 bytes omitted>

用户输出 

876860669
874867572
878573589
637380411
940727165
572409047
416621795
63841579
351397071
183829147
249283562
794019693
358341353
<248162 bytes omitted>

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：164 ms
内存：32264 KiB

输入文件（D8.in） 

100000 100000
0 13720568
1 504640041
0 255460027
1 622817671
1 720062783
0 116902584
1 112482479
0 3
<3365730 bytes omitted>

答案文件（D8.out） 

59008631
249065407
372203263
184203192
946131603
320507232
653697464
241269717
215808976
892341701
6
<492347 bytes omitted>

用户输出 

59008631
249065407
372203263
184203192
946131603
320507232
653697464
241269717
215808976
892341701
675863936
710680079
761635504
<492319 bytes omitted>

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：328 ms
内存：33116 KiB

输入文件（D9.in） 

200000 200000
0 442736931
0 723689083
0 468758675
1 160076033
1 94543233
0 508187305
1 405012629
0 5
<6929970 bytes omitted>

答案文件（D9.out） 

869991448
609398279
39833416
724384270
189588393
900390484
690653805
654070164
99698926
14081181
114
<991059 bytes omitted>

用户输出 

869991448
609398279
39833416
724384270
189588393
900390484
690653805
654070164
99698926
14081181
11410818
906785725
869158503
50
<991031 bytes omitted>

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：853 ms
内存：35468 KiB

输入文件（D10.in） 

500000 500000
0 37624822
0 306152656
1 718073334
0 126069045
0 607141298
1 309185990
0 225942581
0 6
<17521546 bytes omitted>

答案文件（D10.out） 

523896439
300215338
483482429
520298565
981493578
248536508
278567092
762674167
602643677
134145177

<2472119 bytes omitted>

用户输出 

523896439
300215338
483482429
520298565
981493578
248536508
278567092
762674167
602643677
134145177
661852734
703673694
35291340
<2472091 bytes omitted>

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.