QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#257058 | #6435. Paimon Segment Tree | Satsuki | TL | 87ms | 130896kb | C++17 | 3.7kb | 2023-11-18 23:51:20 | 2023-11-18 23:51:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 50010;
typedef long long ll;
const int mod = 1e9 + 7;
struct Matrix{
int n,m;
using point_t = ll;
vector<vector<point_t>> g;
Matrix(int n, int m) :n(n),m(m),g(n+1,vector<point_t>(m+1, 0)) {};
void clear(){
for(auto& row : g) {
std::fill(row.begin(), row.end(), 0);
}
for(int i = 1;i <= n;i++)g[i][i] = 1;
}
friend Matrix operator^(Matrix a,Matrix b){
Matrix ans(a.n, b.m);
int cnt = 0;
for(int i=1;i<=a.n;i++)
for(int j=i;j<=a.n;j++){
for(int k=1;k<=j ;k++)
(ans.g[i][j]+=a.g[i][k]*b.g[k][j]) %= mod,cnt++;
}
return ans;
}
friend Matrix operator*(Matrix a,Matrix b){
Matrix ans(a.n, b.m);
for(int i=1;i<=a.n;i++)
for(int j=i;j<=b.m;j++){
for(int k=i;k<=a.m;k++)
(ans.g[i][j]+=a.g[i][k]*b.g[k][j]) %= mod;
}
return ans;
}
friend Matrix operator+(Matrix a,Matrix b){
Matrix ans(a.n, a.m);
for(int i=1;i<=a.n;i++)
for(int j=1;j<=a.m;j++){
(ans.g[i][j] = a.g[i][j] + b.g[i][j]) %= mod;
}
return ans;
}
};
#define ls (u << 1)
#define rs (u << 1 | 1)
#define A(u) (tr[u].A)
#define mk(u) (tr[u].mk)
struct node
{
int l, r;
Matrix A = Matrix(1, 4);
Matrix mk = Matrix(4, 4);
bool st = false;
}tr[N << 2];
int a[N];
void pushup(int u)
{
A(u) = A(ls) + A(rs);
}
Matrix e = Matrix(4,4);
void build(int u,int l,int r)
{
if(l == r)
{
tr[u] = {l,r};
A(u).g[1][1] = 1;
A(u).g[1][2] = a[l];
A(u).g[1][3] = a[l] * a[l] % mod;
A(u).g[1][4] = a[l] * a[l] % mod;
mk(u) = e;
}
else
{
int mid = l + r >> 1;
tr[u] = {l,r};
mk(u) = e;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void pushdown(int u)
{
if(!tr[u].st)return;
A(ls) = A(ls) * mk(u);
mk(ls) = mk(ls) ^ mk(u);
A(rs) = A(rs) * mk(u);
mk(rs) = mk(rs) ^ mk(u);
mk(u) = e;
tr[u].st = false;
tr[ls].st = true;
tr[rs].st = true;
}
Matrix B = Matrix(4,4);
void upd(int u,int l,int r,int k)
{
if(tr[u].l >= l && tr[u].r <= r)
{
B.g[1][1] = 1;
B.g[1][2] = k;
B.g[2][2] = 1;
B.g[1][3] = k * k % mod;
B.g[1][4] = k * k % mod;
B.g[2][3] = 2 * k % mod;
B.g[2][4] = 2 * k % mod;
B.g[3][3] = 1;
B.g[3][4] = 1;
B.g[4][4] = 1;
A(u) = A(u) * B;
mk(u) = mk(u) ^ B;
tr[u].st = true;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if(l <= mid)upd(ls, l, r, k);
if(r > mid)upd(rs, l ,r ,k);
pushup(u);
}
}
int que(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return A(u).g[1][4];
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
pushdown(u);
if(l <= mid)res += que(ls, l, r);
if(r > mid)res = (res + que(rs, l, r)) % mod;
return res;
}
}
struct qu
{
int l,r,k,id;
}modi[N];
int ans[N];
vector<qu> q[N];
void solve()
{
int n,m,k;cin >> n >> m >> k;
for(int i = 1;i <= n;i++)cin >> a[i];
build(1,1,n);
for(int i = 1;i <= m;i++)
{
cin >> modi[i].l >> modi[i].r >> modi[i].k;
}
for(int i = 1;i <= k;i++)
{
int l,r;cin >> l >> r;
int x,y;cin >> x >> y;
if(x)
q[x - 1].push_back({l, r, -1, i});
q[y].push_back({l, r, 1, i});
}
for(int i = 0;i <= m;i++)
{
if(i)
{
upd(1, modi[i].l, modi[i].r, modi[i].k);
if(modi[i].l > 1)
upd(1, 1, modi[i].l - 1, 0);
if(modi[i].r < n)
upd(1, modi[i].r + 1, n, 0);
}
for(auto t : q[i])
{
// cout << t.id <<" " << que(1,t.l,t.r) << endl;
(ans[t.id] += t.k * que(1, t.l, t.r)) %= mod;
}
}
for(int i = 1;i <= k;i++)
{
cout << (ans[i] + mod)% mod << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
e.clear();
solve();
}
详细
Test #1:
score: 100
Accepted
time: 51ms
memory: 130232kb
input:
3 1 1 8 1 6 2 3 2 2 2 0 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 63ms
memory: 130652kb
input:
4 3 3 2 3 2 2 1 1 6 1 3 3 1 3 6 2 2 2 3 1 4 1 3 4 4 2 3
output:
180 825 8
result:
ok 3 number(s): "180 825 8"
Test #3:
score: 0
Accepted
time: 51ms
memory: 130460kb
input:
100 107 180 -280960553 266308104 -997644864 856103777 592874377 674379235 -946339772 641750362 642418716 -360811715 -555543246 206614021 358239245 349842656 983198973 807518446 -66612455 -980932737 109826132 -109676067 51226145 452115561 -42729559 -950621304 -87009773 714026474 375317493 693260053 -...
output:
400489222 480617351 531108525 254983761 446689548 764223236 142229431 307405789 39817281 66225912 247029353 46506707 529135498 578008236 201809860 674078444 746060191 171471121 722471473 657196163 861551838 606551808 360903956 401221326 767571915 669762004 163759234 141144218 579174939 276557168 518...
result:
ok 180 numbers
Test #4:
score: 0
Accepted
time: 55ms
memory: 130632kb
input:
295 269 129 -210918287 343352194 936488821 -682920910 944685019 677819690 -913857474 643356008 215752838 -582778677 735744580 307969642 807954422 388654459 761031712 -978166251 65058102 236039317 -205619898 -79984863 977152006 79198370 -999053192 -933631858 -776338105 -988909566 -427172257 -83477275...
output:
618251287 899907228 531858556 882858895 725455126 938410366 816431580 6908535 24554323 39964258 545169468 118739750 324108277 57969570 909045869 771733081 78663884 765348479 855417630 840946863 849560917 792963883 68199493 607258525 976267825 554521243 921526613 189188489 544501166 169313970 7657692...
result:
ok 129 numbers
Test #5:
score: 0
Accepted
time: 65ms
memory: 129988kb
input:
290 130 153 467014672 -187494410 -834410250 -221945583 -113569812 976227414 823657567 644961655 -718120549 900287103 634923088 999259803 -742330414 114542837 -69026244 941181808 998903438 650836591 381792036 -50293659 -391889416 -588686091 44623189 -916642412 -368524388 505979642 770338007 734336505...
output:
205306195 913174634 627098553 583511289 53628555 776119748 741459303 361721232 792181766 998349032 63183274 449140540 772865125 869222155 83821401 342565107 772194112 208578315 473166159 924882996 534863573 359442652 252396430 259427632 357792582 605715971 225467777 31224502 410770535 77000480 73685...
result:
ok 153 numbers
Test #6:
score: 0
Accepted
time: 55ms
memory: 130628kb
input:
184 292 178 -560085111 986691728 196865471 -958795491 238240831 979667868 -848892877 351600031 -849819158 973287410 -73789099 492724730 509559542 743289180 3773764 -844502889 -869426018 770666596 66346005 -20602454 534036445 135538767 -911700444 -604685696 942147293 -607021858 -32151743 -793696299 -...
output:
858202984 433975321 69198683 98775914 749936095 716134874 281147731 186709890 903234421 920600352 323335030 69435264 896305275 257633690 55255202 182091822 935500760 726305425 381037995 804018605 478673738 484297808 286861521 10149069 594778768 547188580 540808257 427373166 853802061 768386487 90138...
result:
ok 178 numbers
Test #7:
score: 0
Accepted
time: 64ms
memory: 130664kb
input:
179 152 127 117847849 -936264195 130999142 -202852895 885018743 -721924420 -816410579 353205678 -686550496 751320448 -174610592 889047621 959274719 469177558 -826284192 779877900 64419317 -814536143 -249100025 -793086029 262137073 -237378424 739866630 -587696250 -42148309 887867350 -834641493 -26761...
output:
505009166 348176298 768846383 639656852 767297876 334028836 672141959 865320262 32468111 824990615 935878450 39788029 776229057 745398975 622480518 927354339 667485118 767183633 797234162 637335006 725843572 397083849 891541202 474690368 807830014 546532554 370859947 512952106 797356109 977040750 56...
result:
ok 127 numbers
Test #8:
score: 0
Accepted
time: 71ms
memory: 130844kb
input:
173 215 251 482857384 237921943 65132814 -644735533 -173236088 -423516696 921104462 -742330725 886783639 -862755834 -883322779 677479818 -591010117 -902076112 951548559 994193216 -706768090 697403181 338311909 -763394825 -811937079 799769858 -216457003 -570706804 660632678 -520101420 657836040 -4576...
output:
532409264 425334301 297106918 497679015 766180735 997240773 876619970 775627119 369095265 141725042 860632646 806561262 693330436 844811627 533129631 666137230 797776768 349015941 304013406 366877046 285656333 796617951 263787451 188404775 795402622 368862072 922591321 853125733 448636483 903008737 ...
result:
ok 251 numbers
Test #9:
score: 0
Accepted
time: 72ms
memory: 130604kb
input:
168 151 100 -544242399 314966033 -903591478 -478727476 178574554 -420076241 -751445982 -740725078 -47089749 915277216 112997778 778835439 -141294940 -863264310 121490604 -791491481 834967940 -887799557 22865879 971329122 -475945758 426852667 827219378 -553717358 -28695654 71929823 758204255 14314631...
output:
352187626 704247599 53684196 147547097 652201927 257200097 626135496 49775525 672820311 189599120 469216129 487715787 155787875 856115710 757497826 561926086 567295451 568260936 378849834 906105482 480823862 527730971 133376678 862463926 443893047 318620602 549415798 799707998 458453406 462381509 43...
result:
ok 100 numbers
Test #10:
score: 0
Accepted
time: 63ms
memory: 130864kb
input:
163 213 224 133690560 -215880572 -674490536 -625642844 825352466 -121668517 -718963684 -739119431 -178788357 693310253 307143555 567267636 308420237 862624082 -100676658 -872143435 63780533 -767969553 -587547422 -96121722 155012833 53935476 773753709 560414138 987008757 -433180982 -44285495 48628183...
output:
747432440 517227949 996821749 805271519 840593989 22089777 153536567 999462554 483313583 174809962 671096506 911407220 301225235 350791783 414302958 610922065 348064356 221620487 622546838 251737080 930284090 787053181 512448105 483900137 418446165 774811006 614925836 789232720 98746705 671256184 88...
result:
ok 224 numbers
Test #11:
score: 0
Accepted
time: 55ms
memory: 130568kb
input:
258 174 173 -893409223 958305567 -740356864 -459634788 -527869635 176739208 -981448656 967518958 -15519695 176376021 -991503172 668623257 758135414 -508629589 -930734614 -657828118 -707406874 743969771 -902993452 -66430518 -919061319 -613948985 -772504464 577403584 -310210269 158850261 -846775245 55...
output:
763779848 971203287 417629333 128055735 17327247 15630176 25359233 62738585 361956876 281789376 957004306 7982723 694276684 450550861 225480663 650754963 57977660 889194726 638963520 880818703 608956290 276560765 718925350 342938575 243384787 865317875 569251525 302758871 232054208 811410731 1124094...
result:
ok 173 numbers
Test #12:
score: 0
Accepted
time: 56ms
memory: 130568kb
input:
224 261 183 321076468 14144917 -964309122 -998152041 -233777241 498830290 -124389333 152924562 100565362 -951633735 -51153541 -539047258 -158691246 266759044 -656520429 -577382886 -383476274 -274905450 -161914533 -572427748 644517420 376447356 -227879896 -972623510 702539156 -675224598 698346506 -17...
output:
322262446 309629779 753522996 746794296 331484522 808430979 727359918 533145896 642265099 611737090 791371384 936246806 480013565 761553227 859970290 114739196 147749092 992690312 222043170 425264912 61368448 532877858 131993381 347759625 310385807 693085135 594668938 342481048 673051834 663459641 1...
result:
ok 183 numbers
Test #13:
score: 0
Accepted
time: 75ms
memory: 130364kb
input:
500 500 500 702413239 -895672661 513406482 -706023315 -811668957 -735208181 -537176715 118033401 207303475 203060235 -140437061 -31133246 -878633428 945167015 -142724367 291023931 895505386 218454358 -658034840 845336331 139891825 -182393293 -837703814 -429556732 -291437105 -281345565 -660666794 132...
output:
799094138 146472194 58171908 40775791 547185279 571631473 320570241 279864315 784754669 36384176 647854975 369168115 86332530 547176983 240323948 240924775 72654152 69035557 647102037 39065205 809733534 122261401 419058965 996509642 840422954 505500073 254560823 567513427 197957750 174710109 8980857...
result:
ok 500 numbers
Test #14:
score: 0
Accepted
time: 78ms
memory: 130612kb
input:
500 500 500 -124873923 -862644826 -949273940 266876915 -439657598 -801074509 -979059352 -940221430 505711199 -59424737 -138831414 -965006634 899399622 -860687221 -649259440 740739108 621393765 291254366 -443719524 -220818346 -348168865 -497839324 -513045340 201401859 -959321566 762330816 -643677348 ...
output:
726058600 157394298 6026295 626157799 473455503 836929915 65432281 223447620 258103506 201786082 245837249 839381477 776736180 495914531 234139152 826978202 609481390 609186653 448424325 37801505 772356936 176131960 94645367 507234205 491293083 51500902 336742281 8572500 581656090 337181638 19093229...
result:
ok 500 numbers
Test #15:
score: 0
Accepted
time: 82ms
memory: 129772kb
input:
500 500 500 -952161085 875415752 980154970 336919180 734528541 525168482 -813051296 -293443518 804118924 -26942438 157741502 608327501 382465389 135633335 -252936549 -809545728 660205567 -538803590 -229404208 -89147789 -228338860 89572610 419503829 224469756 -235096708 -488960087 -626687902 -2683037...
output:
948178708 63043518 412562474 979471847 632004126 197149770 44765001 333070147 209208490 245340835 327984181 86381120 108549140 206693435 696566524 692690063 761978712 63394241 115659288 133306357 949561112 412838504 951662013 614320278 450808891 653747562 528431330 653894325 459172133 26721646 92240...
result:
ok 500 numbers
Test #16:
score: 0
Accepted
time: 78ms
memory: 130896kb
input:
500 500 500 220551766 318509048 -482525453 -985147873 -91285334 164334884 -959966664 58367124 807559378 300507130 -135620121 771596163 160498427 34811843 -759471622 -64863281 -711048103 -466003581 -310056161 844697547 186458414 -225873420 449195033 855428348 -608013899 -837393026 -609698455 13950992...
output:
862364241 846328796 782119369 279661198 954588064 332802857 198320732 828750538 842000005 545677700 631170861 739609232 88580357 709394833 410740136 881387963 388869353 282008286 748754853 160380786 98885674 125774059 463282867 88796885 879824305 396598644 823020688 334851683 682882712 847429599 888...
result:
ok 500 numbers
Test #17:
score: 0
Accepted
time: 87ms
memory: 130448kb
input:
500 500 500 -901702666 351536883 -553096556 -12247644 -14241244 98468556 -793958607 -999887707 -894032910 38022158 -134014475 639897554 -61468536 -968867614 -363148731 -518006068 -985159725 -688170843 -390708115 73510139 601255689 -836286721 478886237 -218645804 724101653 206283354 -592709009 -54981...
output:
879478176 44895837 222778896 299056760 459849951 413838727 271861909 135172325 369876017 772291349 288915506 40518418 120722520 489004058 795467085 440669676 679489168 686147119 484183055 276961468 387433763 227355653 842643573 798414401 667476501 635395856 510642724 792257092 437757870 921878747 36...
result:
ok 500 numbers
Test #18:
score: 0
Accepted
time: 59ms
memory: 130748kb
input:
500 500 500 -23957085 89597448 279190305 665685316 -840055119 -575288467 -332983281 -648077065 -595625186 70504456 -427376098 803166216 324455195 -774721837 -574716534 -363258160 -356413382 186803944 -176392799 -89786574 113194999 -248874787 508577442 412312787 351184462 -750040278 -575719563 465886...
output:
796480339 557837848 754107862 815827346 414562979 472887526 461802193 704671280 150724230 889392203 410794501 355361325 755045478 230684672 469082755 160421817 613888058 880851910 81781514 275777155 469039160 274812243 382134369 90336156 83487675 755510237 502221402 519154393 272454262 984290073 699...
result:
ok 500 numbers
Test #19:
score: 0
Accepted
time: 65ms
memory: 130672kb
input:
500 500 500 -556276977 -974516765 816509895 735727582 629098290 -641154795 -774865919 -1299153 -297217461 397954025 -425770451 -425674441 102488232 221598719 -178393643 86457017 -630525004 259603952 -257044753 844058762 233025004 -564320817 -263906133 -661761365 -21732729 -1331168 -263762847 8736997...
output:
430703521 264296600 450750921 819273205 764437218 898752834 45110599 31736921 270581198 820706868 583121122 706134979 774622614 982742936 341484311 656982673 880764494 460796214 464341544 193506837 403410316 168844313 654226247 921525043 207675841 601386662 604116713 804815031 780918170 556319636 85...
result:
ok 500 numbers
Test #20:
score: 0
Accepted
time: 79ms
memory: 130404kb
input:
500 500 500 321468604 763543813 745938792 -586339472 706142380 -412053853 -313890593 645478759 -293777007 135469053 478693159 -557373050 -119478730 415744497 217929248 536172194 -591713202 -865421273 -42729437 -222095915 647822278 -879766847 -234214929 -933660738 -689617190 -54796837 -246773401 4793...
output:
99643867 797790680 117520301 52202392 750645517 708216290 41516009 835813051 977083646 977651719 730889761 289737413 425913664 845931313 563046428 367920130 455303169 324460957 330372383 916507678 470615106 571780062 981697429 286596333 568468983 29449857 156959753 537748583 968861047 328057384 2612...
result:
ok 500 numbers
Test #21:
score: 0
Accepted
time: 74ms
memory: 130636kb
input:
500 500 500 -505818558 206637109 -421774360 681528028 -414638765 619221868 -755773230 -707743342 4630718 167951351 185331536 -689071658 -341445693 -587934960 -288605825 985887371 -865824823 -792621265 -123381391 -90425359 159761589 2612356 -499490994 -302702146 642498362 988879543 -229783955 -504956...
output:
516027113 339960641 489756734 355729464 725784885 222560920 681515130 426514409 475293251 502597154 50178091 756157988 28579538 564199781 754874794 514003796 749624739 289019012 672003817 901814808 7682411 338820429 686389969 644898154 678031469 103954649 681979482 17471041 4440262 543919815 3165571...
result:
ok 500 numbers
Test #22:
score: 0
Accepted
time: 57ms
memory: 130604kb
input:
500 500 500 -347877860 527039679 48889269 423854846 -285585489 -909443324 83088136 -755862860 -342498224 -356043217 170471024 325807447 -511588712 -818997308 -358183 -669803979 -595710417 513262231 -929467517 164182054 -462596490 -79245066 345522978 -223646976 595580352 -657224741 -923381515 -895054...
output:
969965606 18264751 629305960 27286696 162768537 126384997 545402051 188094206 407060997 206670050 716310712 535000164 143845354 998379114 177833472 618210301 982753253 633108530 647352469 861145917 616175682 65506261 856210146 100547662 645637137 6039651 576222559 808554231 307695396 592645172 14327...
result:
ok 500 numbers
Test #23:
score: -100
Time Limit Exceeded
input:
30976 35179 40169 493897111 888600649 -975309652 -653761772 -109084948 -339057770 -323560919 172076671 194108839 -733555675 177323248 -801860526 -220088802 -261931344 291094970 -715152201 295852610 -950657180 -394691096 375214182 -495546348 222663161 -710690410 -906392069 415617168 457144628 -484651...