时间限制：4s 空间限制：512MB
小 \(C\) 在上生物实验课上发现了一种独特的生物，出于生物第一的素养，小 \(C\) 决定研究一下这个独特的生物
这种生物只有两种形态，为了方便描述，小 \(C\) 将其标记为 \(0\) 和 \(1\)
这种生物独特的地方在于它的分裂方式：
- 对于每一个 \([0]\) 他会在原地分裂成 \(\begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix}\)
- 对于每一个 \([1]\) 他会在原地分裂成 \(\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}\)
例如分裂 \(1\) 次就会形成 \(\begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix}\)
例如分裂 \(2\) 次就会形成 \(\begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{bmatrix}\)
为了方便描述，小 \(C\) 将他们分裂后的排列情况看成一个二维矩阵，最左上角记为 \((0,0)\)
分裂 \(k\) 次就会形成一个 \(2^k * 2^k\) 的矩阵
刚开始小 \(C\) 只发现的了这种生物的基本单位 \([0]\) ，决定用显微镜观察它们
小 \(C\) 手上的显微镜看到的视野可以认为是一个矩阵，左上角是 \((x_1,y_1)\) ，右下角是 \((x_2,y_2)\) （相对与此生物形成的矩阵的坐标）
处于对数数的热爱，小C想知道在分裂 \(k\) 次后，他所观察到的范围内有多少个 \(1\)
小 \(C\) 发现这个问题太费时间了，以至于影响他去拿生物 \(rk1\) 了，所以想请你来帮他解决这个问题
小 \(C\) 做了很多次实验，所以共有 \(T\) 次询问
每次实验相互独立
输入格式
第一行一个数 \(T\) ，表示小 \(C\) 的询问次数
接下来 \(T\) 行，每行 \(5\) 个数，分别为 \(k,x_1,y_1,x_2,y_2\)
表示分裂 \(k\) 次时，小 \(C\) 的视野是一个左上角是 \((x_1,y_1)\) ，右下角是 \((x_2,y_2)\) 的矩形
输出格式
共 \(T\) 行，每行一个数，表示小 \(C\) 能看到的 \(1\) 的个数
样例
5
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 5 6 7 8
0
0
0
0
5
数据范围
本题采用子任务捆绑
\(1\le T\le 10^6\)
\(Sub1 : 30\%:0\le k \le 10\)
\(Sub2 : 100\% :0 \le k \le 20,0 \le x_1 \le x_2 < 2^k,0 \le y_1 \le y_2 < 2^k\)
这里的大样例从每个包里分别拿了一个点出来
题解
题目中的分裂规则可以看作是一个状态的转移矩阵：
- 状态
0分裂为：\(\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}\) - 状态
1分裂为：\(\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}\)
如果我们将由 0 经过 \(k\) 次分裂生成的矩阵记为 \(M_k\)，由 1 经过 \(k\) 次分裂生成的矩阵记为 \(N_k\)，它们之间的递归结构如下：
因为 \(x\) 和 \(y\) 是子矩阵的范围，我们可以用二维前缀和来求解：
其中 \(S(X, Y)\) 表示以 \((0,0)\) 为左上角，长宽分别为 \(X, Y\) 的前缀矩阵中 \(01\) 数量。
我们不需要管 \(k\) 是多少（因为 \(M_k\) 永远是 \(M_{k+1}\) 的左上角）。我们只需根据 \(X\) 和 \(Y\) 的二进制位，从低位到高位（自顶向下）三个维度的信息：
R0 / R1：对应矩阵 \(M\) 和 \(N\) 前 \(x\) 行的全局前缀和（覆盖所有宽度）。C0 / C1：对应矩阵 \(M\) 和 \(N\) 前 \(y\) 列的全局前缀和（覆盖所有高度）。S0 / S1：对应矩阵 \(M\) 和 \(N\) 严格在 \([0, x-1] \times [0, y-1]\) 范围内 \(01\) 的个数。
处理当前位时，根据 \(X\) 的第 \(i\) 位（决定上下半区）和 \(Y\) 的第 \(i\) 位（决定左右半区），用已经处理完的低位数据，和完整分形块的 \(01\) 总数 \(f_0[i-1]\) 和 \(f_1[i-1]\) 实现 \(O(1)\) 的状态转移。
:::info[code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Fast_OI{char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)#define putchar(x) (p3-obuf<1000000?*p3++=x:(fwrite(obuf,1,p3-obuf,stdout),p3=obuf,*p3++=x))int read(){int x=0;bool f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=0;c=getchar();}while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}void puts(const char* str){while(*str!='\0')putchar(*str ++); putchar('\n'); }void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+48);}void flush(){fwrite(obuf,1,p3-obuf,stdout);}
}using namespace Fast_OI;
const int N=1<<21;
int n;
int f0[25],f1[25];
int query(int x,int y){if(x==0||y==0) return 0;int r0=0,r1=0;int c0=0,c1=0;int s0=0,s1=0;int m=32-__builtin_clz(x|y);for(int i=1;i<=m;i++){int bx=(x>>(i-1))&1;int by=(y>>(i-1))&1;int nr0=0,nr1=0;int nc0=0,nc1=0;int ns0=0,ns1=0;if(bx==0){nr0=r0<<1;nr1=r0+r1;}if(bx==1){nr0=(f0[i-1]<<1)+r1+r0;nr1=f1[i-1]+f0[i-1]+(r1<<1);}if(by==0){nc1=c1<<1;nc0=c0+c1;}if(by==1){nc1=(f1[i-1]<<1)+c1+c0;nc0=f1[i-1]+f0[i-1]+(c0<<1);}if(bx==0&&by==0){ns0=s0;ns1=s1;}if(bx==0&&by==1){ns0=s0+r0;ns1=s0+r1;}if(bx==1&&by==0){ns0=s1+c0;ns1=s1+c1;}if(bx==1&&by==1){ns0=s0+c0+r1+f0[i-1];ns1=s1+c0+r1+f1[i-1];}r0=nr0,r1=nr1;c0=nc0,c1=nc1;s0=ns0,s1=ns1;}return s0;
}
signed main(){freopen("Count.in","r",stdin);freopen("Count.out","w",stdout);f0[0]=0;f1[0]=1;for(int i=1;i<=22;i++){f0[i]=3*f0[i-1]+f1[i-1];f1[i]=3*f1[i-1]+f0[i-1];}int T=read();while(T--){int k=read(),X1=read(),Y1=read(),X2=read(),Y2=read();int ans=query(X2+1,Y2+1)-query(X1,Y2+1)-query(X2+1,Y1)+query(X1,Y1);write(ans);putchar('\n');}flush();return 0;
}
:::