QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#424450 | #5022. 【模板】线段树 | marher | 0 | 305ms | 17896kb | C++14 | 2.5kb | 2024-05-29 10:34:26 | 2024-05-29 10:34:26 |
Judging History
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%