Find a car
注意到矩阵本质上是一个分形，即每次向右下复制当前矩阵，证明考虑归纳法。
由此可以知道一个比较好的性质 \(a_{i+k,j+k}=a_{i,j}\) 其中 \(k=2^n\)，由于每次是复制加倍，所以横纵坐标都会加上一个 \(2^n\)，且每次增加的二次幂一定是横纵坐标二进制减一后没有的那一位（证明考虑分讨矩阵的位置）。
显然最终得到的位置其左上方的矩阵中是没有比它大的（因为此时的位置不是分形而来的），而不是分形而来的则意味着横纵坐标之和减一等于其本身，且横纵坐标二进制下不会有相同的一。
整理一下上述思路，可以知道 \(a_{i,j}=(i-1)⊕(j-1)+1\)
定义 \(v=(i-1)⊕(j-1)+1\) 题目即求 \(\sum_{x_1≤i≤x_2,y_1≤j≤y_2}[v≤k]v\)
矩阵前缀和做 \(4\) 遍数位 DP 就行了。
【模板】"动态 DP"&动态树分治
\(DDP\) 是解决一类树上点（边）权带修的 \(DP\) 问题，具体看 oi-wiki
本题若不带修则有显然的 \(DP\) 的做法，设 \(f_{i,0/1}\) 表示 \(i\) 这个点选或不选的最大值，转移如下
\[\begin{aligned} f_{i,0}&=\sum_{v\in son_i}\max(f_{v,0},f_{v,1}) \\ f_{i,1}&=\sum_{v\in son_i}f_{v,0}+c_i \end{aligned} \]引入 \((\min+)\) 矩阵：
注意到一个点修改后所影响的状态只有其父亲，考虑树剖然后将重儿子和轻儿子的状态分开，以便于转移。
具体的设 \(g_{i,0/1}\) 表示将 \(i\) 的重儿子去除后 \(i\) 这个点选或不选的最大值。
记 \(i\) 的重儿子为 \(son_i\)，则转移方程变为
\[\begin{aligned} f_{i,0}&=g_{i,0}+\max(f_{son_i,0},f_{son_i,1}) \\ f_{i,1}&=g_{i,1}+f_{son_i,0} \end{aligned} \]写成矩阵的形式
此时重儿子和轻儿子的状态分开了，树链剖分后只用修改轻儿子状态改变部分的矩阵，只会有 \(O(logn)\) 个。由于矩阵具有结合律每次得到一个点的 \(f\) 数组只需要在线段树上查询其所在重链的后缀和即可。
标签：动态,儿子,题解,矩阵,son,纵坐标,aligned,规划,DP From： https://www.cnblogs.com/07Qyun/p/18470475