QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#671696 | #8335. Fast Hash Transform | huan_yp | RE | 0ms | 0kb | C++20 | 2.5kb | 2024-10-24 14:06:38 | 2024-10-24 14:06:39 |
answer
#include<bits/stdc++.h>
#define M 20005
#define mid ((l+r)>>1)
using namespace std;
int n,q,c,m,s[M],o[M];
unsigned long long B,A[M];
struct node{
unsigned long long a[64];
bool x[64];
}a[M],sm[M<<2];
const node& add(const node &b,const node &a){
node ans({});
memcpy(ans.x, b.x, 64);
for(int i=0;i<=63;++i){
for(int j=0;j<=63;++j)
if((a.a[i]>>j)&1) ans.a[i]^=b.a[j],ans.x[i]^=b.x[j];
}
return ans;
}
node cj(){
node ans({});
for(int i=0;i<=63;++i){
ans.x[i]=((B>>i)&1);
for(int j=1;j<=m;++j){
if(((A[j]>>i)&1)&&o[j]==0){ans.x[i]^=1;continue;}
if((!((A[j]>>i)&1))&&o[j]==1) continue;
if(i>=s[j]) ans.a[i]^=(1ll<<(i-s[j]));
else ans.a[i]^=(1ll<<(64+i-s[j]));
}
}
return ans;
}
void build(int p,int l,int r){
if(l==r){sm[p]=a[l];return ;}
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
sm[p]=add(sm[p<<1],sm[p<<1|1]);
}
const node& ck(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return sm[p];
if(L>mid) return ck(p<<1|1,mid+1,r,L,R);
if(R<=mid) return ck(p<<1,l,mid,L,R);
return add(ck(p<<1,l,mid,L,R),ck(p<<1|1,mid+1,r,L,R));
}
void cg(int p,int l,int r,int pos){
if(l==r){sm[p]=a[l];return;}
if(pos<=mid) cg(p<<1,l,mid,pos);
else cg(p<<1|1,mid+1,r,pos);
sm[p]=add(sm[p<<1],sm[p<<1|1]);
}
void print(node a){
for(int i=0;i<=63;++i) printf("%llu ",a.a[i]);
printf("\n");
// for(int i=0;i<=63;++i) printf("%d ",a.x[i]);
// printf("\n");
}
int main(){
scanf("%d%d%*d",&n,&q);
for(int i=1;i<=n;++i){
scanf("%d",&m);
for(int j=1;j<=m;++j) scanf("%d%d%llu",&s[j],&o[j],&A[j]);
scanf("%llu",&B);
a[i]=cj();
// print(a[i]);
}
build(1,1,n);
int op,i,l,r;
unsigned long long x;
while(q--){
scanf("%d",&op);
if(op){
scanf("%d",&i);
scanf("%d",&m);
for(int j=1;j<=m;++j) scanf("%d%d%llu",&s[j],&o[j],&A[j]);
scanf("%llu",&B);
a[i]=cj();
cg(1,1,n,i);
}
else{
scanf("%d%d%llu",&l,&r,&x);
node ans=ck(1,1,n,l,r);
// print(ans);
unsigned long long as=0;
for(int i=0;i<=63;++i){
bool nw=ans.x[i];
nw^=((__builtin_popcountll(ans.a[i]&x))&1);
if(nw) as|=(1ll<<i);
}
printf("%llu\n",as);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 5 1 1 4 0 0 51966 1 60 0 0 0 1 0 0 16 15 0 1 1 771 0 2 2 32368 0 3 3 0 1 2 2 0 0 15 61 1 4095 46681 0 1 3 2023