如果大家打过最近某场 ABC 的 F，那相信难不倒大家。
注意到 很小，所以我们可以使用套路：枚举第 行和第 行，再统计前 列在第 行之间的和。
注意到所有数都大于等于 ，因此前 列在第 行之间的和应该是单调不减的。
如果将其转化为一维怎么做？
由于 ，所以我们只需要找到一个 满足 。由于 在哪里没有关系，所以可以用一些具有单调性的数据结构维护在已经算出来的 中有多少是满足这个条件的，即满足 。比如可以用 set 然后计算区间的贡献即可。
但是这样的算法是 的，但是计算一下就会发现约为 。大概率会超时。
但是我们发现我们可以用单调栈来维护，于是就变成 。才 多一点，但是时限 1.5s，不会 T 的。
注意：，所以需要使用 unsigned long long。
CODE：
#include <bits/stdc++.h>
using namespace std;
#define intt unsigned long long
intt sum[60][50010];
intt st[50010], ans;
int ll, rr, top;
signed main() {
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
intt l, r;
cin >> n >> m;
intt c;
for (int i = 1, j; i <= n; i++) {
for (j = 1; j <= m; j++) {
cin >> c;
sum[i][j] += c;
}
}
cin >> l >> r;
for (int i = 1, j; i <= n; i++) {
for (j = 1; j <= m; j++) {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
intt t;
for (int i = 1, i2, j; i <= n; i++) {
for (i2 = i; i2 <= n; i2++) {
ll = 1, rr = 1, top = 1;
for (j = 1; j <= m; j++) {
t = sum[i2][j] - sum[i - 1][j]; // t 具有单调性。
//需要将 t - x >= l && t - x <= r → t - r <= x <= t - l
while (ll <= top && t - st[ll] > r) {
ll++;
}
while (rr <= top && t - st[rr] >= l) {
rr++;
}
while (rr && t - st[rr] < l ||
rr > top) { //需要回退，因为可能加过头了，还因为只有像上面那样写才有单调性。
rr--;
}
if (t - st[ll] <= r && t - st[rr] >= l && rr >= ll) {
ans += rr - ll + 1;
}
st[++top] = t;
}
}
}
cout << ans;
return 0;
}