cf 341D lahub and xors

题目大意

给定初始值为$0$的$n*n$矩阵

两种操作

矩形内异或一个值
求矩阵内异或和

$n\le 1000$

分析

二维线段树标记不下传貌似直接可做

有没有更简便的方法？

考虑异或的特性

我们修改$(u,v)-(x,y)时(u\le x,v\le y)$

修改$(u,v)$，$(x+1,y+1)$，$(x+1,v)$，$(u,y+1)$这四个单点的值$a(x,y)$

然后考虑我们只询问单点$val(x,y)$时

那么我们只需要计算$$\bigotimes_{i=1}^{x\bigotimes_{j=1}}y a(x,y)$$

然后再考虑我们询问矩形$(u,v)-(x,y)$时

首先差分成四个形如$(1,1)-(X,Y)$的询问，然后写下式子找规律

\[\begin{aligned}
&\bigotimes_{i=1}^X\bigotimes_{j=1}^Y val(i,j)\\
=&\bigotimes_{i=1}^X\bigotimes_{j=1}^Y \bigotimes_{x=1}^i\bigotimes_{y=1}^j a(x,y)\\
=&\bigotimes_{x=1}^X\bigotimes_{y=1}^Y\left(\bigotimes_{i=1}^{X-x+1}~\bigotimes_{j=1}^{Y-y+1}a(x,y)\right)\\
=&\bigotimes_{x=1}^X\bigotimes_{y=1}^Y [x,X奇偶同][y,Y奇偶同] a(x,y)
\end{aligned}
\]

按(x，y)的奇偶性分成四个树状数组维护

可以发现任意两个树状数组没有公共点

注意我们把val化成了a

这样我们就只需要单点修改四个位置（修改到对应树状数组里）

然后询问的时候到(X,Y)奇偶性对应的树状数组里查询即可

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

using namespace std;

const int M=1e3+7;

typedef long long LL;

inline int ri(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-48;

    return f?x:-x;

}

inline LL rl(){

    LL x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-48;

    return f?x:-x;

}

int n,m;

struct Bit{

    int c[M][M];

    Bit(){memset(c,0,sizeof c);}

    inline int lb(int x){return x&-x;}

    inline void add(int x,int y,LL d){

        int i,j;

        if(x==0||y==0) return;

        for(i=x;i<=n;i+=lb(i))

        for(j=y;j<=n;j+=lb(j)) c[i][j]^=d;

    }

    inline LL sum(int x,int y){

        int i,j; LL res=0;

        for(i=x;i>0;i-=lb(i))

        for(j=y;j>0;j-=lb(j)) res^=c[i][j];

        return res;

    }

}C[2][2];

inline int id(int x){return (x+1)>>1;}

LL get(int x,int y){

    return C[x&1][y&1].sum(id(x),id(y));

}

LL get(int u,int v,int x,int y){

    return get(x,y)^get(u-1,v-1)^get(x,v-1)^get(u-1,y);

}

void add(int x,int y,LL d){

    C[x&1][y&1].add(id(x),id(y),d);

}

void add(int u,int v,int x,int y,LL d){

    add(x+1,y+1,d); add(u,v,d); add(x+1,v,d); add(u,y+1,d);

}

int main(){

    int i,kd,u,v,x,y; LL d;

    n=ri(),m=ri();

    while(m--){

        kd=ri(),u=ri(),v=ri(),x=ri(),y=ri();

        if(kd==1) printf("%lld\n",get(u,v,x,y));

        else{

            d=rl();//

            add(u,v,x,y,d);

        }

    }

    return 0;

}

巴特西

cf 341D lahub and xors

题目大意

分析

solution

最新文章

热门文章