QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#281179 | #7765. Xor Master | songziyan | Compile Error | / | / | C++14 | 3.4kb | 2023-12-09 22:52:40 | 2023-12-09 22:52:40 |
Judging History
This is the latest submission verdict.
- [2023-12-09 22:52:40]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2023-12-09 22:52:40]
- Submitted
answer
#include<cstdio>
#define int long long
#define ull unsigned long long
const int N=1e6+5;
int n,q;
ull a[N],g[N];
ull min(ull x,ull y){return x<y?x:y;}
ull max(ull x,ull y){return x>y?x:y;}
struct basis{
ull s[70];
ull insert(ull x){
for(int i=63;i>=0;i--)if((x>>i)&1){
if(!s[i]){
for(int j=i-1;j>=0;j--)
if((x>>j)&1)x^=s[j];
s[i]=x;
for(int j=63;j>i;j--)
if((s[j]>>i)&1)s[j]^=x;
return x;
}
x^=s[i];
}
return 0;
}
ull qrymin(ull x){
for(int i=63;i>=0;i--)x=min(x,x^s[i]);
return x;
}
ull qrymax(ull x){
for(int i=63;i>=0;i--)x=max(x,x^s[i]);
return x;
}
}bas;
struct bit{
ull a[N];
void add(int x,ull v){
for(;x<=n;x+=(x&(-x)))
a[x]^=v;
}
ull sum(int x){
ull res=0;
for(;x;x-=(x&(-x)))
res^=a[x];
return res;
}
void init(){
memset(a,0,sizeof(a));
}
}c;
struct tree{
#define lc x<<1
#define rc x<<1|1
ull tmp[N<<4],*p=tmp;
ull *tr[N<<2],tag[N<<2],sum[N<<2];
int tot[N<<2],len[N<<2];
void pushup(int x){
ull k=0;
for(int i=0;i<tot[x];i++){
tr[x][i]=tr[lc][i]^tr[rc][i]^k;
k=(tr[lc][i]&tr[rc][i])|(tr[lc][i]&k)|(tr[rc][i]&k);
}
sum[x]=sum[lc]+sum[rc];
}
void addtag(int x,ull v){
tag[x]^=v;
sum[x]=0;
ull k=0;
for(int i=0;i<tot[x];i++){
ull t=k;
if((len[x]>>i)&1){
k=k&(tr[x][i]&v);
tr[x][i]=tr[x][i]^t^v;
}else{
k=k|(tr[x][i]&v);
tr[x][i]=tr[x][i]^t;
}
sum[x]+=(tr[x][i]<<i);
}
}
void pushdown(int x){
if(tag[x]){
addtag(lc,tag[x]);
addtag(rc,tag[x]);
tag[x]=0;
}
}
void build(int x,int l,int r){
tag[x]=0;
len[x]=r-l+1;tot[x]=1;
while((1<<tot[x])<=(r-l+1))++tot[x];
tr[x]=p;p+=tot[x]+5;
if(l==r){
tr[x][0]=sum[x]=bas.qrymax(g[l]);
//printf("%llu ",tr[x][0]);
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(x);
}
void upd(int x,int l,int r,int ql,int qr,ull v){
if(!v)return;
if(ql<=l&&r<=qr)return addtag(x,v);
pushdown(x);
int mid=(l+r)>>1;
if(ql<=mid)upd(lc,l,mid,ql,qr,v);
if(qr>mid)upd(rc,mid+1,r,ql,qr,v);
pushup(x);
}
ull qry(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sum[x];
pushdown(x);
int mid=(l+r)>>1;
ull res=0;
if(ql<=mid)res+=qry(lc,l,mid,ql,qr);
if(qr>mid)res+=qry(rc,mid+1,r,ql,qr);
return res;
}
void rbuild(int x,int l,int r){
tag[x]=0;
if(l==r){
tr[x][0]=sum[x]=bas.qrymax(g[l]);
return;
}
int mid=(l+r)>>1;
rbuild(lc,l,mid);
rbuild(rc,mid+1,r);
pushup(x);
}
}T;
void init(){
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++)
scanf("%llu",&a[i]);
for(int i=1;i<=n;i++){
g[i]=g[i-1]^a[i];
c.add(i,a[i]);
}
T.build(1,1,n);
}
void opt1(int x,ull v){
a[x]^=v;
c.add(x,v);
T.upd(1,1,n,x,n,bas.qrymin(v));
}
void opt2(ull v){
if(bas.insert(v)){
c.init();
for(int i=1;i<=n;i++){
g[i]=g[i-1]^a[i];
c.add(i,a[i]);
}
T.rbuild(1,1,n);
}
}
ull opt3(int ql,int qr){
ull pre=c.sum(ql-1);
ull v=bas.qrymin(pre);
T.upd(1,1,n,ql,qr,v);
ull ans=T.qry(1,1,n,ql,qr);
T.upd(1,1,n,ql,qr,v);
return ans;
}
signed main(){
init();
while(q--){
int op,x,l,r;ull v;
scanf("%lld",&op);
if(op==1){
scanf("%lld%llu",&x,&v);
opt1(x,v);
}
if(op==2){
scanf("%llu",&x);
opt2(x);
}
if(op==3){
scanf("%lld%lld",&l,&r);
printf("%llu\n",opt3(l,r));
}
}
return 0;
}
/*
*/
详细
answer.code: In member function ‘void bit::init()’: answer.code:47:17: error: ‘memset’ was not declared in this scope 47 | memset(a,0,sizeof(a)); | ^~~~~~ answer.code:2:1: note: ‘memset’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’? 1 | #include<cstdio> +++ |+#include <cstring> 2 | #define int long long answer.code: In function ‘void init()’: answer.code:133:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 133 | scanf("%lld%lld",&n,&q); | ~~~~~^~~~~~~~~~~~~~~~~~ answer.code:135:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 135 | scanf("%llu",&a[i]); | ~~~~~^~~~~~~~~~~~~~ answer.code: In function ‘int main()’: answer.code:169:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 169 | scanf("%lld",&op); | ~~~~~^~~~~~~~~~~~ answer.code:171:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 171 | scanf("%lld%llu",&x,&v); | ~~~~~^~~~~~~~~~~~~~~~~~ answer.code:175:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 175 | scanf("%llu",&x); | ~~~~~^~~~~~~~~~~ answer.code:179:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 179 | scanf("%lld%lld",&l,&r); | ~~~~~^~~~~~~~~~~~~~~~~~