QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671696#8335. Fast Hash Transformhuan_ypRE 0ms0kbC++202.5kb2024-10-24 14:06:382024-10-24 14:06:39

Judging History

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

  • [2024-10-24 14:06:39]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-24 14:06:38]
  • 提交

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

output:


result: