Lowbit

我们定义表示 x 的二进制最低位的 1 及其后面的 0 构成的数,或者用位运算可以表示为

其中利用了补码的性质。

树状数组

树状数组是基于一个序列建立的:

即从往前数个数的和。

树状数组用于维护前缀和。广义地说,树状数组可以维护可减信息(或者不涉及到减法的信息)。

单点修改与单点查询

修改:容易想到,把包含这个点的值都更新一遍:

void add(int p,int v){
    for(int i=p;i<=n;i+=lowbit(i))c[i]+=v;
}

查询:把前缀的段都加起来:

int pre(int p){
    int res=0;
    for(int i=p;i>0;i-=lowbit(i))res+=c[i];
    return res;
}

区间修改与单点查询

区间加上一个数,我们可以维护差分数组。于是区间修改可以转化为差分数组上两个单点修改,单点查询就转化为差分数组上前缀和查询:

/*
 * add(int,int), pre(int) 即上文所定义
 */
void add(int l,int r,int v){
    add(l,v),add(r+1,-v);
}
void query(int p){
    return pre(p);
}

区间修改与区间查询

区间查询可以转化为两个前缀和查询。则我们考虑差分数组上的前缀和查询。我们约定记号表示在序列上的前个数的和(前缀和),则可以推一推得到:

于是我们维护两个数组的前缀和即可。区间修改则转化为单点修改,在两个数组上都做一遍即可。

树状数组上二分

更准确地说,是在树状数组上倍增。例如,求的最大的。根据树状数组的结构,我我们判断一下是否跳过下一子树,或者进入下一子树:

int find(int T){
  int cur = 0, curA = 0;
  for(int j=20; j>=0; j--){
    int nex = (1<<j) + cur;
    if(nex >= N)continue;
    int nexA = curA + A[nex];
    if(nexA <= T) cur = nex, curA = nexA:
  }
  return cur;
}

二维树状数组

推广得到,对于矩阵建立二维树状数组(矩阵)

单点修改与单点查询

修改:同理:

void add(int x,int y,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=n;j+=lowbit(j)){
            c[i][j]+=v;
        }
    }
}

查询:同理:

int pre(int x,int y){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j)){
            res+=c[i][j];
        }
    }
    return res;
}

区间修改与单点查询

这里的区间修改指修改一个子矩阵。类似的,我们也定义一个二维上的差分数组。即

而注意到

于是我们得到了的公式:

而区间修改,则可以转化为差分数组上 4 个单点的修改,于是有

/*
 * add(int,int,int), pre(int,int) 即上文所定义
 */
void add(int rL,int rR,int cL,int cR,int v){
    add(rL,cL,v);
    add(rL,cR+1,-v);
    add(rR+1,cL,-v);
    add(rR+1,cR+1,v);
}
void query(int x,int y){
    return pre(x,y);
}

区间修改与区间查询

我们约定记号表示在矩阵上的的和(二维前缀和):

于是维护 4 个树状数组即可。单点修改的时候给 4 个都改一下。

模板

ZROI1011

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
#define lowbit(x) (x&(-x))
int n,P,q,op,las;
short s[8010][8010][4];
void add(const int & r,const int & c,const int & val){
  int a[4]={val%P,val*c%P,val*r%P,val*r*c%P};
  for(int x=r;x<=n;x+=lowbit(x))
    for(int y=c;y<=n;y+=lowbit(y))
      for(int i=0;i<4;++i)
        s[x][y][i]=((int)s[x][y][i]+a[i])%P;
}
int query(const int & r,const int & c){
  int a[4]={0,0,0,0};
  for(int x=r;x>0;x-=lowbit(x))
    for(int y=c;y>0;y-=lowbit(y))
      for(int i=0;i<4;++i)
        a[i]=(a[i]+s[x][y][i])%P;
  return ((r+1)*(c+1)%P*a[0]-(r+1)*a[1]-(c+1)*a[2]+a[3])%P;
}
int main(){
  scanf("%d%d%d",&n,&q,&P);
  while(q--){
    int rL,rR,cL,cR;
    scanf("%d%d%d%d%d",&op,&rL,&rR,&cL,&cR);
    rL=(rL+las)%n+1;
    rR=(rR+las)%n+1;
    cL=(cL+las)%n+1;
    cR=(cR+las)%n+1;
    if(rL>rR)swap(rL,rR);
    if(cL>cR)swap(cL,cR);
    if(op==1){
      add(rL,cL,1);
      add(rL,cR+1,-1);
      add(rR+1,cL,-1);
      add(rR+1,cR+1,1);
    } else {
      int ans=(query(rR,cR)-query(rL-1,cR)-query(rR,cL-1)+query(rL-1,cL-1))%P;
      ans=(ans+P)%P;
      printf("%d\n",ans),las=(las+ans)%n;
    }
  }
  return 0;
}