本题解仅提供F题的另一种求解全一子矩阵个数的方法 众所周知， 求解全一子矩阵的问题可以用 单调栈 解决， 例如最大子矩阵， 子矩阵个数 而有另一种工具也可以有效而优雅地解决该类问题， 那便是 笛卡尔树 (上面的超链接里有介绍笛卡尔树，并且提供了求解 最大子矩阵 的做法和例题) 如果你熟悉了 笛卡尔树求解最大子矩阵 的做法，相信 求解子矩阵的数量 也很好理解。 假设以当前行为底列连续全1列的高分别为 {} 那么对这k个数字建立小根堆笛卡尔树之后，对于当前分治中心u，区间假设为 计算经过u这一点的区间，满足 那么区间数量即为 因为是小根堆，所以目前任何区间 ，都可以向上延展最多至 从而可以...

该解法时间复杂度为O(nlognlogn)。貌似很多大佬都用优秀的O(nlogn)就把题目解决了，这里提供一种时间复杂度并没那么优秀的解法（离线 + dsu on tree + 树状数组）。题意：n个火山形成一棵树，1号火山为根节点，每一个火山都有权值，t[i]表示第i座火山的温度。 对于从根节点出发的链上的点，距离根节点越远，则温度越低。 q个询问：给出三元组{x, l, r}，表示从x节点开始蔓延，温度在[l, r]的节点数量是多少(包括x，若t[x]不属于[l, r]，则输出0)。分析：既然是蔓延，那么则有两个方向： 往儿子蔓延。 往祖先蔓延(之后可能还会再往祖先的儿子...

首先这题题型很DP，然后容易想到DP状态f[i][j]为前i个人用前j种棋子的方案数。后来感觉状态转移不太好写(本人太菜)，就把第一维改成了四个人有无使用棋子的状态压缩，状态转移就很显然了。这里我用的是刷表法：f[k][j+1] += f[i][j], 当且仅当：1. 在二进制下，i为k的真子集，且仅有一个数位不同(令该位置为p，则k=i|1<<p)。2. s[p][j+1] = '1'。f[i][j+1] += f[i][j], 正常的转移。 #include <bits/stdc++.h> using namespace std; typedef long long...