C. 建筑
鹤了才发现我的50pts部分分居然和正解很沾边！！
感觉所有序列上说什么用笛卡尔树的东西都可以用单调栈代替，比如《矩形》。
50% code
/*
二缺吧我是，调了俩小时才发现系数和最值一一对应只能单点查询！？
真是醉了还是n^4的。。。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 204;
int n, m, v[maxn][maxn], Mx[maxn][maxn][maxn];
int st[maxn], top;
ll ans, res1, res2, sum[maxn][maxn][maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct line
{
struct lines
{
ll mx, xs;
}t[maxn];
void clear(int n)
{
for(int i=1; i<=n; i++)
{
t[i].mx = t[i].xs = 0;
}
}
void update1(int l, int r, int v)
{
for(int i=l; i<=r; i++) t[i].mx = v;
}
void update2(int l, int r, int v)
{
for(int i=l; i<=r; i++) t[i].xs++;
}
int query(int l, int r)
{
int ans = 0;
for(int i=l; i<=r; i++) ans += t[i].mx*t[i].xs;
return ans;
}
}t;
int main()
{
freopen("building.in", "r", stdin);
freopen("building.out", "w", stdout);
n = read(), m = read();
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++) v[i][j] = read();
}
for(int i=1; i<=n; i++)
{
for(int l=1; l<=m; l++)
{
int su = 0, ma = 0;
for(int r=l; r<=m; r++)
{
su += v[i][r]; ma = max(ma, v[i][r]);
sum[i][l][r] = su, Mx[i][l][r] = ma;
}
}
}
for(int l=1; l<=m; l++)
{
for(int r=l; r<=m; r++)
{
top = 0; res1 = 0; res2 = 0;
t.clear(n);
for(int i=1; i<=n; i++)
{
while(top && Mx[st[top]][l][r] < Mx[i][l][r]) top--;
t.update1(st[top]+1, i, Mx[i][l][r]);
st[++top] = i;
t.update2(1, i, 1);
res1 += t.query(1, i);
}
res1 *= (r-l+1);
for(int i=1; i<=n; i++)
{
res2 += sum[i][l][r]*(n-i+1)*i;
}
ans += res1-res2;
}
}
printf("%lld\n", ans);
return 0;
}差别在于：没有考虑根号，保持了矩阵的原有形态，比较T；把矩形压成序列不需要过度预处理，空间开不下；但是最主要的是我并不知道怎么O(n)算出序列的答案(应该是最重要的部分)。
本来想把最大值的系数鹤最大值自己拆开，放到线段树上变成互不干涉的两部分，然而它们的一一对应关系是不可能解除的，由于单点查询代表复杂度不可避免，我把它改成了暴力处理。
然而最终死于没开long long——连续的第二天！！
前两天《串串超人》刚刚提醒过我们：只需要求和的东西不需要维护序列，这个题也是这样的。如果只是最大值求和就很显然，加上的区间长度也不难算，发现这些区间长度构成了等差序列，所以要用到等差序列求和公式。
ll calc(ll x, ll y) {return (x+y)*(y-x+1)/2;}这个东西鹤起来非常眼熟，因为在<矩形>里用过！
ll calc(ll s, ll w)
{
if(s < 0 || s-w+1 < 0) return 0;
return (s+s-w+1)*w/2;
}当时Chen_jr大佬的原版用的是等差序列求和的形式，然而我并不知道求和公式只是感觉传的参数之间有交叉好麻烦于是就化简了一下，calc(s, w)表示长度为s的大区间内长度为w的子区间个数，这个东西我当时也是用等差序列求和来理解的，然而到了这个题上又忘了这个思路，所以这个题用到这个公式和定长区间统计并没有关系是我跑偏了……
ll calc(ll s, ll w){return s < 0 || w < 0 ? 0 : (s + w) * (s - w + 1) / 2;}矩形那题%%%Chen_jr用到的式子本来长这样。
于是就结束了，add 存数据方式非常赞。
鹤得很明显
//原来是等差序列原来是等差序列原来是等差序列原来是等差序列原来是等差序列原来是等差序列
//兴奋死了！！！！！！！！！
//只求和用不着维护序列，这话我好像说过，然而用到的时候就不这么想！！！
//鹤了那就鹤的再彻底一点！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, m, mx[maxn], st[maxn], top;
ll sval[maxn], ans;
vector<int> mp[maxn];
ll calc(ll x, ll y) {return (x+y)*(y-x+1)/2;}
void ckmx(int &x, int y) {if(x < y) x = y;}
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void sol(ll len)
{
ll now = 0, sum = 0, smax = 0; st[top = 0] = -1;
for(int i=0; i<m; i++)
{
sum += 1ll * sval[i] * (i + 1);
while(top && mx[st[top]] < mx[i])
{
smax -= 1ll * mx[st[top]] * (st[top] - st[top-1]);
now -= 1ll * mx[st[top]] * calc(i-1-st[top]+1, i-1-st[top-1]);
top--;
}
now += smax;
smax += 1ll * mx[i] * (i - st[top]);
now += 1ll * mx[i] * calc(1, i-st[top]);
st[++top] = i;
ans += 1ll * len * now - sum;
}
}
int main()
{
freopen("building.in", "r", stdin);
freopen("building.out", "w", stdout);
n = read(), m = read();
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(n < m) mp[i-1].push_back(read());
else mp[j-1].push_back(read());
}
}
if(n > m) swap(n, m);
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++) mx[j] = 0, sval[j] = 0;
for(int j=i; j<n; j++)
{
for(int k=0; k<m; k++) ckmx(mx[k], mp[j][k]), sval[k] += mp[j][k];
sol(j - i + 1);
}
}
printf("%lld\n", ans);
return 0;
}标签：ch,2022NOIPA,33,ll,long,int,maxn,联测,序列 From： https://www.cnblogs.com/Catherine2006/p/16916416.html