QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424450#5022. 【模板】线段树marher0 305ms17896kbC++142.5kb2024-05-29 10:34:262024-05-29 10:34:26

Judging History

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

  • [2024-05-29 10:34:26]
  • 评测
  • 测评结果:0
  • 用时:305ms
  • 内存:17896kb
  • [2024-05-29 10:34:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+50,M=560;

struct node
{
    int x,l,r,y;
}Q[N];

struct ask
{
    int x,y;
}t[N];

int n,q,S=500,a[N],m,c,ans[N],vis[N],L[M],D[N],U[N],R[M],pre[M],s[N],f[N],tmp[N];
vector<pair<int,int>>in[N];

void solve(int l,int r)
{
    int w=r-l,h=0;
    for(int i=l;i<=r;i++)D[i-l]=a[i];
    s[0]=1;
    for(int i=1;i<=m;i++)if(Q[i].l<=l&&Q[i].r>=r)s[i]=1;
    for(int i=1,now=0;i<=m;i++)
    {
        if(Q[i].l<=l-1&&Q[i].r>l-1)now^=pre[i-1];
        if(s[i])L[++h]=now,now=0;
    }
    // cout<<"solve "<<l<<' '<<r<<'\n';
    // for(int i=0;i<=h;i++)cout<<L[i]<<' ';
    // puts("");
    for(auto&x:in[r])while(!s[x.second])x.second--;
    for(int i=0;i<=h;i++)//D -> R
    for(int d=i;;d=(d-1)&i)
    {
        if(d<=w)R[i]^=D[w-d];
        if(!d)break;
    }
    for(int i=0;i<=h;i++)//L -> U
    {
        int d=h-i;
        for(int y=d;;y=(y-1)&d)
        {
            if(y<=w)U[y]^=L[i];
            if(!y)break;
        }
    }
    for(int i=0;i<=w;i++)f[i]=D[i];
    for(int i=0;(1<<i)<=w;i++)if((h>>i)&1)
    for(int j=w-(1<<i);j>=0;j--)f[j+(1<<i)]^=f[j];
    for(int i=0;i<=w;i++)U[i]^=f[i];
    for(int i=0;i<=h;i++)f[i]=0;
    for(int i=0;i+w<=h;i++)f[i+w]=L[i];
    for(int i=0;(1<<i)<=h;i++)if(!((w>>i)&1))
    for(int j=h-(1<<i);j>=0;j--)f[j+(1<<i)]^=f[j];
    for(int i=0;i<=h;i++)R[i]^=f[i];
    // for(int i=0;i<=h;i++)cout<<R[i]<<' ';puts("");
    for(int i=0,now=-1;i<=m;i++)pre[i]=R[now+=s[i]];
    for(int i=0;i<=w;i++)a[i+l]=U[i];
    for(auto x:in[r])ans[x.first]=pre[x.second];
    for(int i=0;i<=h;i++)L[i]=R[i]=0;
    for(int i=0;i<=w;i++)U[i]=D[i]=0;
    for(int i=1;i<=m;i++)s[i]=0;
    if(r==n)for(int i=0;i<=m;i++)pre[i]=0;
}

void solve()
{
    vis[n]=1;
    for(int i=1;i<=m;i++)vis[Q[i].l-1]=vis[Q[i].r]=1;
    for(int i=1;i<=c;i++)vis[t[i].y]=1,in[t[i].y].push_back(make_pair(i,t[i].x));
    for(int i=1,la=1;i<=n;i++)if(vis[i])solve(la,i),la=i+1;
    for(int i=1;i<=c;i++)cout<<ans[i]<<'\n';
    for(int i=1;i<=n;i++)vis[i]=0,in[i].clear();
}

main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    cin>>n>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(q--)
    {
        int opt;cin>>opt;
        if(opt==1)
        {
            m++;Q[m].x=m;
            cin>>Q[m].l>>Q[m].r;
        }
        else cin>>t[++c].y,t[c].x=m;
        if(!q||m==S)solve();
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<'\n';
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 0ms
memory: 10676kb

input:

1
6 6
1 1 5 1 9 4
2 5
1 2 5
2 4
1 3 6
2 6
1 1 6

output:

9
4
12
1
0
5
4
12
0

result:

ok 9 numbers

Test #2:

score: 8
Accepted
time: 4ms
memory: 10768kb

input:

1
999 997
898798734 979577086 45974352 1013270193 1053191143 533594258 372426673 947830633 122319874 368651315 866424479 109724831 427664962 558099346 764830489 326451620 322471751 525780385 746941281 670254345 586958579 979544209 743892216 436404384 291681381 979530194 998929567 367716728 909076993...

output:

1015342581
962986689
965094083
871356796
835210392
172023195
63088572
606096781
569607283
436055720
154605892
663158209
154605892
776365236
281312240
62398687
182713417
604764772
816533315
793514230
325061861
806973284
91749226
283750235
198953311
170342298
432592070
809908556
683302450
40932811
669...

result:

ok 1996 numbers

Test #3:

score: 0
Wrong Answer
time: 20ms
memory: 10796kb

input:

1
999 997
89872218 906651903 120274311 490547919 291584020 755757065 24942887 707247173 763024744 68250332 114193028 999245166 140381610 171802205 399965713 299821903 907998064 906075056 427270276 335420206 708713870 492555323 359637714 197212814 35225369 1011322274 912003632 633998134 1026276199 85...

output:

89872218
860962725
824268152
740065207
207360731
808901318
746023214
487883
419931777
387807782
1069489608
1026379960
59885224
611224003
360758266
449284814
269701002
434535530
104500241
435776988
921908996
342351996
990283018
655743701
798201263
720333733
960717734
1057447450
410290969
233871733
31...

result:

wrong answer 3rd numbers differ - expected: '120274311', found: '824268152'

Subtask #2:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

2
249998 99999
1048488450 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #10:

score: 0
Time Limit Exceeded

input:

3
250000 99999
1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1...

output:

0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
0
0
0
1
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
0
1
1
1
0
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
0
1
1
1
0
0
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
...

result:


Subtask #4:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 165ms
memory: 17896kb

input:

4
249996 99997
309331355 195839266 912372930 57974187 363345291 954954162 650621300 389049294 821214285 263720748 231045308 844370953 768579771 664766522 681320982 124177317 32442094 297873605 743179832 1073656106 443742270 235746807 1054294813 974443618 422427461 307448375 1018255356 20105813 36821...

output:

611117059
866091251
300188933
0
478915924
1053588351
453142424
897441996
60971719
748656483
600408393
0
303761852
983037069
883016404
332332552
1069626159
860304528
851235295
561276840
389049294
681320982
484263000
351914192
620106464
667080579
733146026
375466744
0
347632358
737240082
321494160
0
3...

result:

wrong answer 522nd numbers differ - expected: '12256831', found: '611117059'

Subtask #5:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 305ms
memory: 17556kb

input:

5
249997 99997
860563869 428592873 58576739 761578583 47999879 294581118 988847649 569566599 640106250 440172702 178219106 966598261 763325707 846927552 877923116 145156535 246778542 25949847 507939778 116507169 555239769 259969305 328955819 171606729 535970481 121608060 4437163 370976515 713807003 ...

output:

86824175
176028474
827196202
134440532
680530273
927115559
701565570
162989098
737327525
893620802
145238420
466956310
584685220
335076254
906496781
615301959
450043819
299084464
256395522
415693271
243156406
523874648
432299025
36870751
850336562
1021142651
980343788
690474169
906382780
255651605
8...

result:

wrong answer 1st numbers differ - expected: '860563869', found: '86824175'

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #5:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%