题解 P5232 【[JSOI2012]智者的考验】

· · 题解

水题为什么没人做???

问题显然可以转化成带修地查询区间内前缀异或和为给定数的数量

根据题面来看,把所有按钮都取反跟原来是一样，也就是2^4=16种状态

区间修改为某个数的影响最多只有1次（两两抵消）

线段树上打打标记就可以了...

顺便献上我的blog:https://www.luogu.org/blog/Root-std-admin/

只给伪代码了嗷:

void build(int &p,int l,int r) {
    if (p==0) p=++num,t[p].l=t[p].r=t[p].sum=t[p].y=0,t[p].a=-1;
    t[p].c[N[0]]=((r-l)>>1)+(!(l&1)||!(r&1));
    t[p].c[N[o[0]]]=((r-l)>>1)+((l&1)||(r&1));
    t[p].sum=((((r-l)>>1)+((l&1)||(r&1)))&1)*o[0];
    if (l==r) return;
    int mid=l+r>>1;
    build(t[p].l,l,mid);
    build(t[p].r,mid+1,r);
}
void pd(int p,int l,int r) {
    if (t[p].a!=-1) {
        if (t[p].l) t[t[p].l].a=t[p].a,t[t[p].l].V=t[p].V,t[t[p].l].Q=t[p].Q,t[t[p].l].y=0;
        if (t[p].r) t[t[p].r].a=t[p].a,t[t[p].r].V=t[p].V,t[t[p].r].Q=t[p].Q,t[t[p].r].y=0;
        memset(t[p].c,0,sizeof(t[p].c));
        t[p].c[N[t[p].V]]=((r-l)>>1)+(!(l-t[p].Q&1)||!(r-t[p].Q&1));
        t[p].c[N[t[p].a^t[p].V]]=((r-l)>>1)+((l-t[p].Q&1)||(r-t[p].Q&1));
        t[p].sum=((((r-l)>>1)+((l-t[p].Q&1)||(r-t[p].Q&1)))&1)*t[p].a^((r-l+1&1)*t[p].V);
        t[p].a=-1;
    }
}
void up(int p,int l,int r) {
    int mid=l+r>>1;
    pd(t[p].l,l,mid);
    pd(t[p].r,mid+1,r);
    t[p].sum=t[t[p].l].sum^t[t[p].r].sum^(((mid-l+1)&1)*t[t[p].l].y)^(((r-mid)&1)*t[t[p].r].y);
    for (int i=0; i<16; i++) t[p].c[i]=t[t[p].l].c[N[s[i]^t[t[p].l].y]]+t[t[p].r].c[N[s[i]^t[t[p].r].y]];
}
void cg(int p,int l,int r,int po,int v) {
    if (po<=l) t[p].y^=v;
    else {
        pd(p,l,r);
        int mid=l+r>>1;
        cg(t[p].r,mid+1,r,po,v);
        if (mid>=po) cg(t[p].l,l,mid,po,v);
        up(p,l,r);
    }
}
int ask(int p,int l,int r,int po) {
    if (t[p].a!=-1) return (t[p].a*(po-t[p].Q&1))^t[p].V^t[p].y;
    if (l==r) return t[p].sum^t[p].y;
    int mid=l+r>>1;
    if (po<=mid) return ask(t[p].l,l,mid,po)^t[p].y;
    else return ask(t[p].r,mid+1,r,po)^t[p].y;
}
int que(int p,int l,int r,int L,int R,int v) {
    pd(p,l,r);
    v^=t[p].y;
    if (L==l&&R==r) return t[p].c[N[v]];
    int mid=l+r>>1;
    if (R<=mid) return que(t[p].l,l,mid,L,R,v);
    else if (L>mid) return que(t[p].r,mid+1,r,L,R,v);
    else
        return que(t[p].l,l,mid,L,mid,v)+que(t[p].r,mid+1,r,mid+1,R,v);
}
void ca(int p,int l,int r,int L,int R,int v,int V,int Q) {
    if (L==l&&R==r) {
        t[p].a=v;
        t[p].V=V;
        t[p].y=0;
        t[p].Q=Q;
        t[p].c[N[V]]=((r-l)>>1)+(!(l-Q&1)||!(r-Q&1));
        t[p].c[N[v^V]]=((r-l)>>1)+((l-Q&1)||(r-Q&1));
        t[p].sum=(((((r-l)>>1)+((l-Q&1)||(r-Q&1)))&1)*v)^((r-l+1&1)*V);
    } else {
        pd(p,l,r);
        V^=t[p].y;
        int mid=l+r>>1;
        if (R<=mid) ca(t[p].l,l,mid,L,R,v,V,Q);
        else if (L>mid) ca(t[p].r,mid+1,r,L,R,v,V,Q);
        else
            ca(t[p].l,l,mid,L,mid,v,V,Q),ca(t[p].r,mid+1,r,mid+1,R,v,V,Q);
        up(p,l,r);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    register int i,j;
    rx=read();
    ry=read();
    n=0;
    for (i=0; i<rx; i++)
        for (j=0; j<ry; j++) o[i]^=1<<(i*ry+j),o[j+rx]^=1<<(i*ry+j),q^=read()<<(i*ry+j);
    n=read();
    m=read();
    s[bo=num=0]=0;
    for(; bo<=num;) {
        for (i=0; i<rx+ry; i++) {
            for (j=0; j<=num; j++)
                if (s[j]==(s[bo]^o[i])) break;
            if (j>num) s[++num]=s[bo]^o[i];
            to[bo][i]=j;
        }
        bo++;
    }
    for (i=0; i<64; i++) N[i]=-1;
    for (i=0; i<=num; i++) N[s[i]]=i;
    num=0;
    build(ro,1,n);
    while (m--) {
        bo=read();
        if (bo==0) bo=read(),cg(ro,1,n,bo,o[read()-1]^ask(ro,1,n,bo)^(bo==1?0:ask(ro,1,n,bo-1)));
        else if (bo==1) if (bo=read(),x=read(),N[q]==-1) puts("0");
            else printf("%d\n",que(ro,1,n,bo,x,q));
        else if (rx=read(),ry=read(),x=o[read()-1],cg(ro,1,n,ry+1,ask(ro,1,n,ry)^(((ry-rx+1)&1)*x)),ca(ro,1,n,rx,ry,x,0,rx-1),rx-1) cg(ro,1,n,rx,ask(ro,1,n,rx-1));
    }
    return 0;
}

哦对,MN看数据范围,好像是1e6吧...

真心感谢大家观看,谢谢!!!