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>
用户输出
455134627
793913007
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#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;
}
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>
用户输出
455134627
793913007
系统信息
Exited with return code 0
15 15
0 897135375
1 358432579
1 602917765
1 217421102
1 376580608
0 538599413
1 371811698
0 31196545
<337 bytes omitted>
用户输出
216377874
540305084
530317326
574404455
113299621
517430644
922267438
982379975
系统信息
Exited with return code 0
500 500
1 159418858
0 651920937
0 652100067
0 365475059
1 228562079
0 344014735
0 250315824
1 793250
<15217 bytes omitted>
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
1000 1000
1 432968930
1 146613541
0 363915141
1 271750910
0 359885055
1 909324639
1 889068353
0 5483
<30657 bytes omitted>
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
5000 5000
0 327340172
1 264347742
1 872019940
1 345426744
1 150595861
0 776941713
0 864167311
0 8410
<160281 bytes omitted>
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
20000 20000
0 387357108
0 132484258
0 247420303
0 714542477
1 817132850
0 456496538
0 37437007
0 802
<662826 bytes omitted>
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
50000 50000
1 832782475
1 350577985
1 195880998
1 732850761
0 75656777
0 654099248
1 460552450
0 753
<1677665 bytes omitted>
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
100000 100000
0 13720568
1 504640041
0 255460027
1 622817671
1 720062783
0 116902584
1 112482479
0 3
<3365730 bytes omitted>
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
200000 200000
0 442736931
0 723689083
0 468758675
1 160076033
1 94543233
0 508187305
1 405012629
0 5
<6929970 bytes omitted>
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
500000 500000
0 37624822
0 306152656
1 718073334
0 126069045
0 607141298
1 309185990
0 225942581
0 6
<17521546 bytes omitted>
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