QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770671#7992. 【模板】线段树ToboAC ✓2738ms68600kbC++205.1kb2024-11-21 23:13:052024-11-21 23:13:05

Judging History

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

  • [2024-11-21 23:13:05]
  • 评测
  • 测评结果:AC
  • 用时:2738ms
  • 内存:68600kb
  • [2024-11-21 23:13:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

bool Memory_begin;

/*
 */

// template <int mod>
// unsigned int down(unsigned int x)
// {
//     return x >= mod ? x - mod : x;
// }
// template <int mod>
// struct Modint
// {
//     unsigned int x;
//     Modint() = default;
//     Modint(unsigned int x) : x(x) {}
//     friend istream &operator>>(istream &in, Modint &a) { return in >> a.x; }
//     friend ostream &operator<<(ostream &out, Modint a) { return out << a.x; }
//     friend Modint operator+(Modint a, Modint b) { return down<mod>(a.x + b.x); }
//     friend Modint operator-(Modint a, Modint b) { return down<mod>(a.x - b.x + mod); }
//     friend Modint operator*(Modint a, Modint b) { return 1ULL * a.x * b.x % mod; }
//     friend Modint operator/(Modint a, Modint b) { return a * ~b; }
//     friend Modint operator^(Modint a, int b)
//     {
//         Modint ans = 1;
//         for (; b; b >>= 1, a *= a)
//             if (b & 1)
//                 ans *= a;
//         return ans;
//     }
//     friend Modint operator~(Modint a) { return a ^ (mod - 2); }
//     friend Modint operator-(Modint a) { return down<mod>(mod - a.x); }
//     friend Modint &operator+=(Modint &a, Modint b) { return a = a + b; }
//     friend Modint &operator-=(Modint &a, Modint b) { return a = a - b; }
//     friend Modint &operator*=(Modint &a, Modint b) { return a = a * b; }
//     friend Modint &operator/=(Modint &a, Modint b) { return a = a / b; }
//     friend Modint &operator^=(Modint &a, int b) { return a = a ^ b; }
//     friend Modint &operator++(Modint &a) { return a += 1; }
//     friend Modint operator++(Modint &a, int)
//     {
//         Modint x = a;
//         a += 1;
//         return x;
//     }
//     friend Modint &operator--(Modint &a) { return a -= 1; }
//     friend Modint operator--(Modint &a, int)
//     {
//         Modint x = a;
//         a -= 1;
//         return x;
//     }
//     friend bool operator==(Modint a, Modint b) { return a.x == b.x; }
//     friend bool operator!=(Modint a, Modint b) { return !(a == b); }
// };
// const int mod = 1e9 + 7;
// typedef Modint<mod> mint;

const int N = 2e5 + 5;
const unsigned all = (1 << 20) - 1;
int n, q;
unsigned a[N], binom[N][20];
struct node
{
    unsigned sum[20], tag;
    int siz;
} st[N << 2];
#define lc cur << 1
#define rc cur << 1 | 1
void pushup(int cur)
{
    for (int i = 0; i < 20; i++)
        st[cur].sum[i] = 0;
    for (int i = 0; i < 20; i++)
        for (int j = 0; i + j < 20; j++)
            st[cur].sum[i + j] += st[lc].sum[i] * st[rc].sum[j],
                st[cur].sum[i + j] &= all;
}
void pushdown(int cur)
{
    unsigned tmp = st[cur].tag;
    st[cur].tag = 0;
    st[lc].tag += tmp, st[rc].tag += tmp;
    for (int i = 0; i < 20; i++)
    {
        unsigned coef = 1;
        for (int j = i + 1; j < 20; j++)
        {
            coef *= tmp;
            coef &= all;
            st[lc].sum[i] += st[lc].sum[j] * coef * binom[j][j - i];
            st[lc].sum[i] &= all;
            st[rc].sum[i] += st[rc].sum[j] * coef * binom[j][j - i];
            st[rc].sum[i] &= all;
        }
    }
}
void build(int cur, int l, int r)
{
    st[cur].siz = r - l + 1;
    if (l == r)
    {
        st[cur].sum[0] = a[l];
        st[cur].sum[1] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(cur);
}
void update(int cur, int l, int r, int a, int b, unsigned x)
{
    if (a <= l and r <= b)
    {
        st[cur].tag += x;
        for (int i = 0; i < 20; i++)
        {
            unsigned coef = 1;
            for (int j = i + 1; j < 20; j++)
            {
                coef *= x;
                coef &= all;
                st[cur].sum[i] += st[cur].sum[j] * coef * binom[j][j - i];
                st[cur].sum[i] &= all;
            }
        }
        return;
    }
    int mid = l + r >> 1;
    pushdown(cur);
    if (a <= mid)
        update(lc, l, mid, a, b, x);
    if (b > mid)
        update(rc, mid + 1, r, a, b, x);
    pushup(cur);
}
unsigned query(int cur, int l, int r, int a, int b)
{
    if (a > r or b < l)
        return 1;
    if (a <= l and r <= b)
        return st[cur].sum[0];
    int mid = l + r >> 1;
    pushdown(cur);
    return (query(lc, l, mid, a, b) * query(rc, mid + 1, r, a, b)) & all;
}

bool Memory_end;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i <= n; i++)
    {
        binom[i][0] = 1;
        for (int j = 1; j <= min(19, i); j++)
            binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) & all;
    }
    build(1, 1, n);
    while (q--)
    {
        int opt, l, r, x;
        cin >> opt >> l >> r;
        if (opt == 1)
        {
            cin >> x;
            update(1, 1, n, l, r, x);
        }
        else
            cout << query(1, 1, n, l, r) << '\n';
    }
}
/*
 */

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7912kb

input:

10 10
969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323
1 5 6 3034
2 1 10
2 1 9
2 1 4
1 3 6 126904
2 5 5
2 9 9
1 7 7 853094
1 4 9 1025178
2 5 8

output:

1045541
1012343
558151
580413
810659
527353

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 2738ms
memory: 66512kb

input:

200000 200000
496015 180543 330721 874799 740427 144379 598057 795949 323465 87657 683935 748203 748665 288301 846003 33033 746029 132621 876629 361899 701297 373189 256151 723161 377571 54947 91151 855991 433965 73347 155081 314317 790527 705555 1035217 298963 604641 203865 230029 802437 720769 843...

output:

746709
564663
426791
840425
762201
413693
881143
534387
189149
257625
60619
958793
250635
869079
383765
151047
272239
146175
46215
914259
617511
698623
381177
932779
792705
785375
1044293
202971
508317
237901
634919
646839
38501
304017
889609
214899
617927
720071
628729
202369
420511
528565
555717
7...

result:

ok 100378 lines

Test #3:

score: 0
Accepted
time: 2711ms
memory: 66456kb

input:

200000 200000
313625 170101 477893 536285 651807 542493 870481 1038171 205037 914869 1020857 263797 349049 146425 49155 634785 620419 520999 216377 365705 284761 874801 450169 521981 238295 791805 292987 339767 765065 1017179 333101 73531 855729 410125 933189 192789 52457 526865 918271 334533 876331...

output:

225575
235385
743949
20373
509445
393347
140689
735475
977073
494895
593783
118129
492359
290607
103169
466197
609397
831915
388819
1031053
461107
492189
790925
208041
397517
1008911
672577
873151
784219
796179
760731
460383
118997
497147
238277
523161
689295
284013
911061
929085
706393
43425
510263...

result:

ok 100374 lines

Test #4:

score: 0
Accepted
time: 2656ms
memory: 66412kb

input:

200000 200000
739417 442397 798113 1007491 665409 592547 462937 279569 996861 214643 160915 500005 469305 265763 795325 714747 389531 895767 42643 690581 622101 972937 523057 537349 516203 142465 236475 847121 91 207903 662211 217361 719869 627825 604205 672273 850891 1022115 1048509 897035 628451 3...

output:

444657
39965
452743
238997
193873
136779
260825
787865
9695
595453
261037
544313
699625
820773
559969
248143
774521
63201
638949
505491
716869
1030369
297709
62897
252693
946983
516321
487437
379371
462937
719033
135883
504135
358807
653171
667547
244677
757901
507969
47983
217365
482585
50135
2125
...

result:

ok 100322 lines

Test #5:

score: 0
Accepted
time: 2675ms
memory: 68520kb

input:

200000 200000
878281 409257 412753 876501 321015 417441 946983 984087 562451 252151 374129 580547 937283 981209 389785 264703 440961 891661 388351 126163 259811 935411 1020727 464021 919541 640021 739311 742339 441387 1001965 243001 885461 512517 138375 284195 942661 327139 169879 187213 451495 3596...

output:

109927
998377
991627
620943
787199
273921
572857
720861
1017973
64061
139487
579101
504019
258045
603557
635973
482857
581423
929839
679177
136695
770551
555407
554481
397867
562315
143345
831265
539885
247475
748131
668535
355937
691045
822657
975439
1015853
419521
524191
379285
367763
616871
72602...

result:

ok 100002 lines

Test #6:

score: 0
Accepted
time: 2688ms
memory: 66452kb

input:

200000 200000
127893 64597 871723 63155 821817 218213 746965 755721 310759 814059 598775 632527 306539 52465 874049 814177 243599 487785 277453 349495 308319 46575 108867 732681 207131 919913 217321 337991 497569 581951 682603 696093 972195 684017 470693 11061 222099 415301 927951 549639 985241 3657...

output:

420091
18519
640371
904943
684475
1036055
125371
827039
1043611
365105
828065
516723
714231
354665
439379
532007
338053
897737
489167
643919
371741
927141
389683
236981
958531
9039
242417
105419
99761
338857
947389
885165
246889
614361
374675
764687
372385
736799
443909
974843
203445
114007
16069
18...

result:

ok 99968 lines

Test #7:

score: 0
Accepted
time: 2660ms
memory: 66512kb

input:

200000 200000
552729 50675 303307 219501 239115 563593 893279 207933 189701 331997 618615 154239 925927 379343 657609 596487 865283 638581 542281 532455 561911 468203 644599 903169 109173 544673 188019 1045397 582443 1042025 440935 973477 323733 962839 88373 1017593 724845 1415 257687 53431 9105 583...

output:

1004311
994397
283331
283373
358651
1044557
642177
849191
645865
338359
764519
359989
55583
358623
334417
971329
771383
241551
239343
678001
551689
855905
820529
906269
500967
169191
25389
177595
547533
525387
11781
149391
714847
86315
132663
735845
154711
791163
944107
143599
348051
68825
578927
26...

result:

ok 100487 lines

Test #8:

score: 0
Accepted
time: 2689ms
memory: 66508kb

input:

200000 200000
575177 557681 1002353 493679 352743 89217 869843 12137 33559 66533 863027 540457 504531 678293 901479 928227 720599 608365 849151 621057 250027 171949 275393 935665 308089 915065 673393 362717 594793 189327 735051 315341 413853 792019 967187 1029717 123133 272127 1044415 387851 539943 ...

output:

948807
806243
64705
251743
448317
325333
411821
716895
1033391
676065
759575
303009
280355
190165
1031133
151559
128289
501093
14521
598743
232451
521649
170415
370785
508273
1038995
215395
567067
84125
649463
954247
465053
827789
465053
790997
166955
105803
915513
71253
437073
282949
527089
887273
...

result:

ok 99480 lines

Test #9:

score: 0
Accepted
time: 2675ms
memory: 66560kb

input:

200000 200000
882221 660105 538731 297131 886341 644377 386761 820241 454147 292943 25889 883147 449877 661847 912985 598895 409353 251235 876743 215475 816959 151689 843113 507553 214065 478113 328115 243763 531161 316423 608895 472243 295301 536125 748067 896975 888621 901489 959709 282659 105347 ...

output:

732079
1897
398235
826895
132261
1013735
455617
72641
503751
921843
271355
645451
432715
955837
901009
479467
957403
323345
202757
580215
163319
1022767
409345
772473
192851
667489
469149
1017755
317195
778665
509611
627913
569891
55169
63183
546729
1043679
81017
762265
917119
390211
741405
929853
6...

result:

ok 100308 lines

Test #10:

score: 0
Accepted
time: 2670ms
memory: 66460kb

input:

200000 200000
384849 532345 43083 43209 795051 227833 1042073 146175 36147 975669 518917 206645 260179 260527 975997 1045035 1014499 282973 278293 788491 889929 756037 58707 687759 981789 598217 448957 556941 734767 461657 786369 836109 123747 971483 458237 814657 1013559 881139 777837 573065 449295...

output:

89867
51467
450641
701417
173861
287229
82987
817843
801543
82987
218275
821635
401115
401115
801359
996737
401281
8299
38285
458019
1022033
700557
261405
696513
573203
178967
870709
1032533
433917
1017465
515537
481053
995153
92099
927267
973293
401303
173179
914689
742083
233337
774063
107853
1011...

result:

ok 100052 lines

Test #11:

score: 0
Accepted
time: 2675ms
memory: 66460kb

input:

200000 200000
562665 355033 546325 27599 904077 567287 226889 119357 94659 133007 427157 986781 300649 535213 232957 294815 141471 454615 902301 118519 281243 799927 769561 393977 926857 1013411 545831 129277 1033901 77247 215177 609269 434599 845667 476035 773097 446923 5583 398777 886489 95099 633...

output:

518065
303595
341693
507727
159343
234189
441185
464047
484833
994861
267275
955947
179555
345789
973715
232699
123181
188541
493439
780831
513831
850729
148331
380251
16969
214775
412689
662441
416301
276793
288285
894687
992137
127837
122449
501715
166257
182057
96141
1037921
349083
214155
474345
...

result:

ok 100240 lines

Test #12:

score: 0
Accepted
time: 2679ms
memory: 68496kb

input:

200000 200000
724927 19507 1000383 223083 612043 237831 758799 721837 11173 90137 951051 694565 108305 782913 208115 365167 815713 214681 589561 723105 157619 319579 921849 750143 376789 612529 539953 26395 309609 823759 387881 257133 904023 70225 424305 46217 118715 209767 628367 33541 780471 22726...

output:

945161
433909
794137
126313
864433
854279
157643
285011
701721
396349
352009
899045
722413
1026523
749115
3759
558339
342803
333769
400723
368739
817869
188801
179483
568357
543165
241047
578879
141533
476747
264795
487963
379217
847377
152547
605827
1048565
91191
761087
765697
205361
72559
708997
5...

result:

ok 100229 lines

Test #13:

score: 0
Accepted
time: 2706ms
memory: 66468kb

input:

200000 200000
933395 390001 114411 918947 417639 639281 10689 444375 36127 654091 738197 630259 131885 725113 899403 124739 384883 754043 195071 168673 936753 158963 115013 470955 933303 580477 111239 686123 48391 281989 991039 233027 81109 637515 1032729 142919 512091 83049 388465 598345 218217 730...

output:

240397
189029
201097
634671
677449
735205
141275
105573
478245
934793
279431
576083
1039889
873177
1019623
183023
651055
230423
264553
308875
732131
197503
722643
888617
262437
192327
613717
264883
876647
196887
688573
88583
662801
730743
325797
568861
523327
20789
560727
658357
756289
907571
269109...

result:

ok 99778 lines

Test #14:

score: 0
Accepted
time: 2676ms
memory: 68456kb

input:

200000 200000
221919 922271 628657 445807 404239 247597 240711 566255 238583 717265 654261 141819 1005135 873761 884645 353809 319429 18969 964313 92045 913043 811079 339357 236835 229561 803527 421189 949451 506245 166039 802915 24627 933099 740431 118145 98723 532921 470689 746221 597839 132263 55...

output:

917475
718077
512793
273363
197739
56595
847309
424065
987111
756185
411043
93439
456551
83517
1036847
374915
763181
195053
732533
822701
863399
418485
47549
289159
348023
560493
678215
988491
378945
369413
244901
52275
671523
662625
578053
376561
102875
306763
123799
303975
128519
857813
377371
688...

result:

ok 99866 lines

Test #15:

score: 0
Accepted
time: 2738ms
memory: 68552kb

input:

200000 200000
415007 961207 447891 263035 547939 638927 589479 588145 45435 464571 966555 73271 391883 531209 419597 554279 180143 551415 9583 297249 964515 453657 222381 196793 48499 538497 750469 941487 358093 932091 900111 310871 250735 907439 708253 994587 586761 967163 617199 50167 936755 13375...

output:

155423
1043405
294585
689027
634687
854363
406173
877995
612443
481599
630763
509819
896257
888081
229945
401565
470685
806181
125557
205763
163081
929041
849777
89257
866479
451979
979207
282479
990707
726917
984609
193175
116181
690531
642737
240111
392233
788847
194461
57511
566665
1015993
435515...

result:

ok 100265 lines

Test #16:

score: 0
Accepted
time: 2707ms
memory: 68504kb

input:

200000 200000
1021311 707231 46007 863705 635269 151063 635895 471479 286613 234667 426219 578437 950703 895697 84713 801311 711389 662925 586823 403475 719249 975733 954409 162599 763433 190897 725187 678559 544959 397325 43953 338335 137953 238999 619807 175311 153077 193503 847267 907097 589543 9...

output:

447619
467103
571597
174675
13717
902403
867875
701939
354797
274629
323007
200295
340479
998721
698657
157491
39017
924403
943449
68335
65357
79655
150455
567677
444861
351481
77067
102291
989887
308337
548745
302133
389741
18281
454673
540095
324905
779799
330357
302157
665621
484239
459987
703885...

result:

ok 100088 lines

Test #17:

score: 0
Accepted
time: 2695ms
memory: 68500kb

input:

200000 200000
680581 339593 428191 513713 753227 2519 1014047 906027 876875 905399 198813 836751 311529 381509 171565 686599 158089 388099 90013 627157 404217 264219 709091 752363 771955 755449 585851 522765 587787 190261 1025955 748873 48475 945039 1031699 394747 356713 249305 407635 589849 75025 4...

output:

604619
704623
294035
107401
39691
139057
454493
588635
746637
839043
914131
636609
25383
869657
31473
64895
200195
490475
548203
9533
634197
590305
804167
549311
566303
283915
654961
906949
428677
98223
640441
841129
639001
606597
113871
812087
274973
1000655
742847
90503
319617
208813
680007
374735...

result:

ok 100251 lines

Test #18:

score: 0
Accepted
time: 2710ms
memory: 68600kb

input:

200000 200000
857881 498273 866271 490109 137835 407213 397031 630443 948281 45171 495209 848207 146641 177513 414545 205407 236197 948355 425337 850363 1023739 807429 255079 455521 778883 276575 486615 529903 442081 857749 1103 886831 83859 472259 170715 345709 373097 808563 1007675 933159 447511 2...

output:

446819
62221
713907
969515
597261
772411
604023
88857
384161
429043
180911
221479
201579
782439
853303
253861
327369
944427
653231
933585
924365
17573
228517
630201
951313
389997
770053
884953
94821
822947
1046735
820189
267241
354655
680009
553865
397261
144901
293929
311497
386489
877455
1030737
6...

result:

ok 100101 lines

Test #19:

score: 0
Accepted
time: 2702ms
memory: 66312kb

input:

200000 200000
1000531 465825 384607 507917 430313 73703 382597 17457 97771 558737 511647 644175 68505 582371 995109 462393 6157 312771 564449 39251 433241 716003 13897 298975 722927 168543 776109 622551 975477 272265 255799 654047 402571 156075 97445 402099 690447 203493 791613 324065 314689 224447 ...

output:

251089
550253
495813
678511
784283
715985
567373
495433
924957
649653
891811
446329
563485
933723
789699
530225
191415
1041893
371133
814297
508469
355527
946117
666753
801087
476947
241487
409879
845047
727885
664175
949637
699659
871367
320421
962825
313565
573245
763965
271757
747121
371449
44835...

result:

ok 100238 lines

Test #20:

score: 0
Accepted
time: 2706ms
memory: 66512kb

input:

200000 200000
393397 150015 318611 201595 122651 361723 566771 36301 595453 641533 379391 958867 166721 564535 694133 155233 831721 123233 122397 1046775 913635 918811 1001799 844175 436297 843939 281903 235277 230191 530065 660699 626885 312131 134851 387823 676267 25057 301453 124627 485647 323011...

output:

389255
709013
480039
235969
982957
921477
347805
87469
54653
166923
1039261
859181
981581
567031
186927
198401
7111
537459
632057
914309
167125
539737
1018635
641743
352429
701507
245757
504603
88683
145151
249259
430473
900927
596247
378257
252853
120435
50635
917681
733033
418637
723295
557621
956...

result:

ok 99518 lines

Test #21:

score: 0
Accepted
time: 2689ms
memory: 66472kb

input:

200000 200000
595861 312381 929659 875705 606935 341011 743727 627239 146381 814421 444115 800007 960351 230959 287925 648131 556871 355623 667811 19285 39559 651329 819245 726657 474917 373169 995731 632871 213791 307001 300543 896125 719609 886555 619975 876063 548069 260401 658285 437097 512301 3...

output:

917045
173725
955725
514325
475651
514615
752649
199703
227145
571051
150863
487645
417337
167877
1038775
682983
372095
527947
339285
332601
954513
314813
76227
175821
136905
503751
722141
164805
132157
293145
910435
478747
500499
348727
579587
301361
869781
789237
339119
693191
918775
892679
637111...

result:

ok 99768 lines