QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#267408 | #7765. Xor Master | kgqy | 0 | 79ms | 67744kb | C++14 | 4.0kb | 2023-11-27 11:14:05 | 2023-11-27 11:14:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
#define lowbit(x) ((x)&-(x))
inline int read(){
int w=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) w=w*10+ch-'0',ch=getchar();
return w;
}
int n,q;
int a[500005];
int g[500005];
struct bbd{
int c[500005];
void add(signed x,int v){
while(x<=n) c[x]^=v,x+=lowbit(x);
}
int query(signed x){
int sum=0;
while(x) sum^=c[x],x-=lowbit(x);
return sum;
}
}tra;
struct ba{
int c[70];
int insert(int x){
for(int i=63;i<=63;i--){
if(!(x&(1ll<<i))) continue;
if(!c[i]){
for(int j=i-1;j<=63;j--){
if(x&(1ll<<j)) x^=c[j];
}
c[i]=x;
for(int j=63;j>i;j--){
if(c[j]&(1ll<<i)) c[j]^=x;
}
return x;
}
x^=c[i];
}
return 0;
}
int querymin(int x){
int mx=__lg(x);
for(int i=x;i<=x;i--){
if(!(x&(1ll<<i))) continue;
x^=c[i];
}
return x;
}
}bas;
int qt(int x,int y,int z){
return (x&y)|(x&z)|(y&z);
}
int us1[105],us2[105],uslen;
struct sgt{
vector<int> d[2000005];
int tag[2000005],sum[2000005];
void build(int x,int l,int r){
for(int i=0;(1<<i)<=(r-l+1);i++) d[x].push_back(0);
if(l==r) return;
int mid=(l+r)>>1;
build(lc(x),l,mid);build(rc(x),mid+1,r);
}
void pushtag(int x,int val){
// return;
if(x>114514) return;
tag[x]^=val;
sum[x]=0;
uslen=d[x].size();
return;
if(uslen>100) return;
for(int i=0;i<uslen;i++){
us2[i]=(d[x][i]&val);
us1[i]=d[x][i]-us2[i];
if(uslen&(1ll<<i)) us1[i]|=val;
}
for(int i=0,jw=0;i<uslen;i++){
d[x][i]=(jw^us1[i]^us2[i]);
jw=qt(~us1[i],us2[i],jw);
sum[x]+=(1ll<<i)*d[x][i];
}
}
void pushdown(int x){
// if(!tag[x]) return;
// pushtag(lc(x),tag[x]);pushtag(rc(x),tag[x]);
// tag[x]=0;
}
void pushup(int x){
for(int i=0;i<d[x].size();i++) d[x][i]=0;
for(int i=0;i<min(d[lc(x)].size(),d[rc(x)].size());i++){
if(i+1<d[x].size()) d[x][i+1]=qt(d[x][i],d[lc(x)][i],d[rc(x)][i]);
d[x][i]=(d[lc(x)][i]^d[rc(x)][i]^d[x][i]);
}
int ls=d[lc(x)].size(),rs=d[rc(x)].size();
if(ls==d[x].size()) d[x][ls-1]|=d[lc(x)][ls-1];
if(rs==d[x].size()) d[x][rs-1]|=d[rc(x)][rs-1];
sum[x]=sum[lc(x)]+sum[rc(x)];
}
void tbuild(int x,int l,int r){
// sum[x]=tag[x]=0;
if(l==r) return d[x][0]=g[l],sum[x]=g[l],void();
int mid=(l+r)>>1;
tbuild(lc(x),l,mid);tbuild(rc(x),mid+1,r);
pushup(x);
}
void reset(int x,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr) return pushtag(x,val);
int mid=(l+r)>>1;
// pushdown(x);
if(ql<=mid) reset(lc(x),l,mid,ql,qr,val);
if(qr>mid) reset(rc(x),mid+1,r,ql,qr,val);
// pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sum[x];
int mid=(l+r)>>1,rt=0;
if(ql<=mid) rt+=query(lc(x),l,mid,ql,qr);
if(qr>mid) rt+=query(rc(x),mid+1,r,ql,qr);
return rt;
}
void bk(int x,int l,int r,int al){
if(l==r) return g[l]=sum[x]^al,void();
int mid=(l+r)>>1;
bk(lc(x),l,mid,al^tag[x]);bk(rc(x),mid+1,r,al^tag[x]);
}
}tr;
void init(){
for(int i=1;i<=n;i++) tra.add(i,a[i]);
tr.build(1,1,n);
for(int i=1;i<=n;i++) g[i]=a[i]^g[i-1];
tr.tbuild(1,1,n);
}
void modify(int id,int val){
return;
int w=bas.querymin(val);
tr.reset(1,1,n,id,n,w);
a[id]^=w;
tra.add(id,w);
}
void rebuild(int val){
// tr.bk(1,1,n,0);
for(int i=1;i<=n;i++) g[i]=max(g[i],g[i]^val);
tr.tbuild(1,1,n);
}
void insertnum(int x){
int val=bas.insert(x);
if(!val) return;
rebuild(val);
}
int query(int ql,int qr){
int w=bas.querymin(tra.query(ql-1));
tr.reset(1,1,n,ql,qr,w);
return 0;
int rt=tr.query(1,1,n,ql,qr);
tr.reset(1,1,n,ql,qr,w);
return rt;
}
main(){
n=read();q=read();
for(int i=1;i<=n;i++) a[i]=read();
init();
while(q--){
int op=read();
if(op==1){
int id=read(),val=read();
modify(id,val);
}else if(op==2){
insertnum(read());
}else{
int ql=read(),qr=read();
printf("%llu\n",query(ql,qr));
}
}
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
2000 2000 1860495733 462603674 3739839441 759356520 47330263 550811730 2301200895 989240351 2499503801 2624225494 2123076812 1180966826 238739434 488666688 784742950 2583466952 4111371941 2335988605 2583741355 933716686 1644403538 1970423306 304500250 905101643 1814942168 1136358764 88729799 1577263...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #5:
score: 0
Runtime Error
input:
500000 100000 12261386944926786495 7846697792998647383 16622924885320463714 170129022271213944 12625257523700625864 7684671687986103560 11532026873918423068 1131776055566669037 8263146651412710501 17872572061246021001 5017109039248728310 11088626167542318645 13810119722795416818 10928315716094262229...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 79ms
memory: 67744kb
input:
100000 100000 860905160 3192911636 290327446 2020707113 959258245 454185039 421895589 1070265496 2218913641 1684685660 1206723673 2606734467 4247254571 3341954386 3805299640 1702270353 2472053741 2816060613 1307901348 2702949728 879391505 884661815 330738731 1575749344 1239158446 2099693858 67466644...
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:
wrong answer 1st lines differ - expected: '208755389215975', found: '0'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%