有点厉害的题，感觉需要练猜猜猜和状态优化的能力了。
题意：给出一个排列 \(p\)，两个点 \(i<j\) 有边当且仅当 \(p_i>p_j\)。求对于每一个 \(i\)，求所有点到 \(i\) 的最短路之和，如果两点不连通最短路为 \(0\)。\(n\le 2\times 10^5\)。
做法：
首先可以把这个排列分成若干个区间连通块去做，其他的没有贡献，比较显然。
然后直接计算所有点的距离，因为没有什么递推式的关系，所以我们感觉没有什么办法直接计算，或者根据某一个的答案去改改得到另一个的答案。所以我们考虑转化一下计算思路，不直接算距离，而是枚举 \(x\)，算有多少个点的距离 \(\ge x\)。这里为了方便，我们可以先算点 \(i\) 左侧的贡献再算右侧的。
为了方便思考，我们可以这个排列按照 \((i,p_i)\) 这些点画在二维平面上，会更直观。
我们讨论该怎么到一个点 \(j<i\)，在平面上就是 \((i,p_i)\) 左侧这个平面的点。我们发现，为了到一个点 \(j\)，我们每一步应该往左上角最左侧的点走，或者右下角最下的点走，这样对于我们要的 \(j\) 覆盖范围是最大的。记点 \(u\) 左上角走的点为 \(l_u\)，右下角走的点为 \(r_u\)。初始能走到的范围是 \((u,u)\)，每走一步，范围 \((x,y)\) 变为 \((l_y,r_x)\)。计算答案就是算走到的位置不能覆盖的点的个数加和，也就是左下角的一个矩形。
直接做是 \(O(n^2)\) 的，但是这里有一个很厉害的结论：不同的对 \((x,y)\) 只有 \(O(n\sqrt n)\) 个！让我们来证明一下。
我们对于同一个 \(x\) 考虑可能的 \(y\)，记分别为 \(y_1,y_2\cdots y_k\)，显然这些 \(y\) 必须要满足 \(p_{y_i}<p_{y_{i+1}}\) 的。我们记前 \(\sqrt n\) 个对为好对，显然是满足答案的量级的。考虑剩下的非好对，根据定义那么非好对的 \((x,y_t)\) 会取到 \((x',y_1)\)，根据定义，会有 \(y_t-y_1\ge \sqrt n,x'\le x\)，所以 如果我是走了一个非好对，那么 \(x+y\) 每次一定会减小至少根号，所以走的非好对个数也是根号的，就得证了。
如何求得这些对？可以直接暴力做，用哈希维护一下，常数会比较大，但是我们有更好的做法。我们可以考虑从后往前找出这些对，每次对于当前的 \(x\)，往序列开头加入一个 \((x,x)\) 的对，然后扫一遍 \((x,y)\) 的序列对，把他扔到对应的 \((l_y,?)\) 的序列中。这样有什么样的好处呢，因为我的 \(x\) 递减，所以 \(p_{r_x}\) 越来越小，也就是能覆盖的范围，很好理解，因为这个东西是单调的，所以我们往 \((l_y,?)\) 里塞的时候 \(p_{?}\) 也会保持单调，这样我们就可以只检验最后一个位置和加入的是否相同即可，常数会小很多。
最后就是一个 \(O(n)-O(n\sqrt n)\) 的修改和询问，直接用分块维护一下即可，时空复杂度 \(O(n\sqrt n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5, B = 500;
int nxt[maxn * 1000]; long long s[maxn * 1000];
int n, m, p[maxn], q[maxn];
struct Block {int tag[maxn], a[maxn], l[maxn], r[maxn], pos[maxn], pre[maxn];void prepare() {for (int i = 1; i <= m; i++)l[i] = r[i] = pre[i] = tag[i] = a[i] = 0;for (int i = 1; i <= m; i++) {pos[i] = (i - 1) / B + 1;if(!l[pos[i]])l[pos[i]] = i;r[pos[i]] = i;}}void add(int x, int val) {a[x] += val;for (int i = l[pos[x]]; i <= r[pos[x]]; i++)tag[i] = (i == l[pos[x]] ? a[i] : a[i] + tag[i - 1]);for (int i = 1; i <= pos[m]; i++)pre[i] = pre[i - 1] + tag[r[i]];}int query(int x) {if(x == 0)return 0;return pre[pos[x] - 1] + tag[x];}
} tree;
int ans[maxn], res[maxn], tot, l[maxn], r[maxn], rev[maxn];
vector<pair<int, int> > pos[maxn];
void cal() {for (int i = 1; i <= tot; i++)s[i] = nxt[i] = 0;tot = 0;for (int i = 1; i <= m; i++)res[i] = 0;for (int i = 1; i <= m; i++)rev[q[i]] = i;int p = m + 1;for (int i = m; i >= 1; i--) {l[rev[i]] = min(rev[i], p);p = min(p, rev[i]);}p = m + 1;for (int i = m; i >= 1; i--) {if(p < q[i])r[i] = max(i, rev[p]);elser[i] = i;p = min(p, q[i]);}
// for (int i = 1; i <= m; i++)
// cout << l[i] << " asd" << r[i] << " " << q[i] << endl;for (int i = 1; i <= m; i++)pos[i].clear();for (int i = m; i >= 1; i--) {reverse(pos[i].begin(), pos[i].end());pos[i].push_back(make_pair(i, ++tot));reverse(pos[i].begin(), pos[i].end());for (int j = 0; j < pos[i].size(); j++) {int tx = l[pos[i][j].first], ty = r[i];// cout << i << " " << pos[i][j].first << " " << tx << " " << ty << endl;if(tx == i && ty == pos[i][j].first)continue;if(!pos[tx].size() || pos[tx][pos[tx].size() - 1].first != ty)pos[tx].push_back(make_pair(ty, ++tot));nxt[pos[i][j].second] = pos[tx][pos[tx].size() - 1].second;}}
// cout << "debug" << endl;tree.prepare();for (int i = 1; i <= m; i++) {res[i] += i - 1;for (int j = (int)pos[i].size() - 1; j >= 0; j--) {int id = pos[i][j].second, x = i, y = pos[i][j].first;s[id] = s[nxt[id]] + tree.query(q[y] - 1);// cout << x << " " << y << " " << nxt[id] << " " << s[id] << endl;if(x == i && y == i)res[i] += s[id];}tree.add(q[i], 1);}//cout << endl;
}
void get_val(int l, int r) {cal();for (int i = l; i <= r; i++)ans[i] += res[i - l + 1];for (int i = 1; i <= m; i++)q[i] = m + 1 - q[i];reverse(q + 1, q + m + 1);cal();for (int i = l; i <= r; i++)ans[r - (i - l)] += res[i - l + 1];
}
void solve(int l, int r) {m = 0;for (int i = l; i <= r; i++)q[++m] = p[i] - l + 1;get_val(l, r);
}
int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> p[i];int mx = 0, lst = 0;for (int i = 1; i <= n; i++) {mx = max(mx, p[i]); if(mx == i)solve(lst + 1, i), lst = i;}for (int i = 1; i <= n; i++)cout << ans[i] << " ";cout << endl;return 0;
}