C. Colorful Table
设p1为最左边的a[p1]>=i,p2为最右边的a[p2]>=i，则i的面积大小为行的p1-p2,列的p1-p2，大小为2*（p2-p1+1）
但是如果暴力的去求每个点的左右端点，肯定会超时，有没有办法优化呢？
1.我们想到，大的数一定包含小的数：如果大的数算出来了，那么比他小的数一定也满足条件，可以递推
2.再用两个数组记录自己第一次出现和最后一次出现的位置
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 10;
#define LL long long
int a[N], last_[N], first_[N], min_first[N], max_last[N];
void solve() {
int n, k;
cin >> n >> k;
memset(first_, 0, sizeof first_);
memset(last_, 0, sizeof last_);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {//算第一次和最后一次出现的位置
if (!first_[a[i]]) first_[a[i]] = i;
last_[a[i]] = i;
}
for (int i = 1; i <= k+1; i++) min_first[i] = 1e9, max_last[i] = -1e9;
for (int i = k; i >= 1; i--) {
if (last_[i]) max_last[i] = max(max_last[i + 1], last_[i]);//要么继承，要么自己的更优
else max_last[i] = max_last[i + 1];//不算，但是要继承上面的
}
for (int i = k; i >= 1; i--) {
if (first_[i]) min_first[i] = min(min_first[i + 1], first_[i]);
else min_first[i] = min_first[i + 1];
}
for (int i = 1; i <= k; i++) {
if (!first_[i]) {//没出现，返回0
cout << "0 ";
continue;
}
cout << 2 * (max_last[i] - min_first[i] + 1) << ' ';
}
cout << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}