题解说明

问题背景：
给定一个排列数组 $p[1..n]$，需要对其划分区间并计算每个位置的某种统计量。代码通过复杂的数据结构（树状数组、链表、并查集）和双向处理技巧，完成对每个区间的答案计算。

核心思路：
$1.$ 区间划分

• 遍历数组 $p$，维护当前最大值 $mx$。
• 当 $mx == i$ 时，说明 $[lst+1, i]$ 是一个完整区间（排列的前缀最大值刚好覆盖到 $i$）。
• 将该区间作为独立子问题处理。

$2.$ 区间标准化

• 将区间 $[l,r]$ 内的值映射为 $1..n$ 的连续整数，存入数组 $a$。
• 初始化答案数组 $ans[i] = n-1$，表示基础贡献。

$3.$ solve 函数（核心）

• 使用树状数组维护前缀和，用于快速统计小于某值的元素个数。
• 使用 $ls[i], rs[i]$ 记录每个位置向左/向右扩展到的最小值位置。
• 每个元素初始为独立集合，集合存储区间 $[X[i], Y[i]]$。
• 从大到小遍历值，逐步合并集合，更新答案。
• 合并时使用链表和并查集思想，保证小集合并入大集合，减少复杂度。

$4.$ 双向处理

• 为了覆盖所有情况，除了正向处理，还需要反向处理：
  • 将 $a[i]$ 映射为 $n-a[i]+1$，再整体反转。
  • 同时反转 $ans$ 数组，保证对应关系。
  • 再次调用 solve，补充计算答案。
• 最终再反转回来，得到完整答案。

$5.$ 输出

• 每个区间处理完毕后，输出该区间的所有 $ans[i]$。

复杂度分析：

• 每个区间内的处理主要依赖树状数组（$O(\log n)$）和集合合并（均摊 $O(n \log n)$）。
• 整体复杂度约 $O(n \log n)$，适合 $n \leq 2 \times 10^5$ 的数据范围。

实现细节：

• 树状数组用于快速统计前缀和。
• $ls/rs$ 数组通过逆序遍历构建，保证能快速找到左右边界。
• 合并集合时维护 $tg$（标记值），避免重复更新，保证效率。
• 双向处理是关键技巧，确保所有情况都被覆盖。

#include <bits/stdc++.h>
// 循环宏定义：rep为正向循环（i从a到b递增），per为反向循环（i从a到b递减）
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back          // 向量尾部插入元素
#define P make_pair           // 创建pair对（简化写法）
using namespace std;
typedef long long ll;        // 定义长整型别名ll
const int N = 2e5 + 3;       // 数组最大规模（2e5+3，适配题目数据范围）

// 快速读取整数（处理正负号）
inline ll read() {
    ll x = 0;                // 存储读取结果
    bool f = 0;              // 符号标记（0为正，1为负）
    char c = getchar();      // 读取单个字符

    // 跳过非数字字符，检测负号
    while (c < '0' || c > '9')
        f = (c == '-'), c = getchar();  // 遇'-'则标记f为1

    // 读取数字部分，累加形成最终结果
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();  // 字符转数字并累加

    return f ? -x : x;       // 返回带符号的结果
}

int nn, p[N];                // nn：原始数组长度；p[N]：原始输入数组
ll ans[N];                   // ans[N]：最终答案数组（存储每个位置的结果）
int n, a[N], ra[N], ls[N], rs[N];  // n：当前处理区间长度；a[N]：当前区间的数组；
                                  // ra[N]：a数组的逆映射（ra[val] = 下标）；
                                  // ls[N]：每个位置的左边界；rs[N]：每个位置的右边界

#define lb(x) (x&-(x))       // 宏定义：获取x的最低位1（树状数组专用）
int t[N];                    // 树状数组：用于快速查询前缀和、更新元素

// 树状数组更新：在x位置加k
inline void ad(int x, int k) {
    for (; x <= n; x += lb(x))  // 沿最低位1向上更新父节点
        t[x] += k;
}

// 树状数组查询：查询1~x的前缀和
inline int qr(int x) {
    int A = 0;                  // 存储查询结果
    for (; x; x -= lb(x))       // 沿最低位1向下累加子节点值
        A += t[x];
    return A;
}

// 初始化函数：预处理ra、rs、ls数组
inline void init() {
    // 1. 构建ra数组（a的逆映射：ra[值] = 对应的下标）
    rep(i, 1, n) {
        ra[a[i]] = i;
        t[i] = 0;  // 初始化树状数组（后续会重新赋值）
    }

    // 2. 构建rs数组：rs[i]表示i右侧（含i）第一个最小值的下标
    int mi = n;    // 记录当前最小值的下标，初始为n
    per(i, n, 1) { // 反向遍历（从后往前）
        if (a[i] < a[mi])       // 若当前a[i]更小，更新最小值下标
            mi = i;
        rs[i] = mi;             // 记录i位置的右边界
    }

    // 3. 构建ls数组：ls[i]表示i左侧（含i）第一个最小值的下标
    mi = n;        // 重置最小值下标
    per(i, n, 1) { // 反向遍历（从后往前）
        mi = min(mi, ra[i]);    // ra[i]是值i的下标，取当前最小值下标
        ls[ra[i]] = mi;         // 记录值i对应下标的左边界
    }
}

// 链表与并查集相关数组：用于区间合并操作
int hd[N], pre[N], X[N], Y[N];  // hd[N]：链表头；pre[N]：前驱指针；X/Y[N]：区间左右端点
int h2[N], p2[N], sz[N];        // h2/p2[N]：另一组链表（用于合并）；sz[N]：集合大小
ll tg[N];                       // tg[N]：标记值（用于批量更新答案）

// 合并函数：将集合i合并到集合j
inline void mer(int j, int i) {
    // 按大小合并：小集合合并到大集合（减少操作次数）
    if (sz[j] < sz[i]) {
        swap(h2[i], h2[j]);     // 交换链表头
        swap(sz[i], sz[j]);     // 交换集合大小
        swap(tg[i], tg[j]);     // 交换标记值
    }

    // 遍历集合i的所有元素，合并到集合j
    for (int x = h2[i], t = p2[x]; x; x = t, t = p2[x]) {
        ans[x] += tg[i] - tg[j];// 更新元素x的答案（调整标记差值）
        p2[x] = h2[j];          // 接入集合j的链表
        h2[j] = x;              // 更新集合j的链表头
    }

    sz[j] += sz[i];             // 更新集合j的大小
}

// 核心解决函数：处理当前区间的答案计算
inline void solve() {
    init();  // 先调用init()预处理ra、rs、ls数组

    // 初始化每个元素为独立集合
    rep(i, 1, n) {
        hd[i] = X[i] = Y[i] = h2[i] = i;  // 链表头、区间端点、另一链表头均指向自身
        pre[i] = p2[i] = tg[i] = 0;       // 前驱、链表指针、标记初始化为0
        sz[i] = 1;                        // 集合大小初始为1
        ad(i, 1);                         // 树状数组初始化：每个位置加1（表示存在）
    }

    // 从大到小遍历值xx（控制合并顺序）
    per(xx, n, 1) {
        ad(a[xx], -1);  // 树状数组中删除a[xx]位置（标记为不存在）

        static int b[N << 1];  // 临时数组：存储当前要处理的集合
        int tt = 0, hh = 1;    // tt：数组尾指针；hh：数组头指针（模拟队列）

        // 将以xx为头的链表元素存入b数组
        for (int i = hd[xx]; i; i = pre[i])
            b[++tt] = i;

        reverse(b + 1, b + tt + 1);  // 反转数组（调整处理顺序）

        // 处理b数组中的所有集合
        while (hh <= tt) {
            int i = b[hh++];              // 取出当前要处理的集合i
            int x = X[i], y = Y[i];       // 集合i对应的区间[x,y]
            // 查询树状数组中1~(a[y]-1)的和（统计符合条件的元素个数）
            int res = qr(a[y] - 1);
            int x2 = ls[y], y2 = rs[x];   // 计算新的区间边界[x2,y2]
            tg[i] += res;                 // 累加当前集合的标记值（贡献到答案）

            // 情况1：x == x2（左边界已达最小）
            if (x == x2) {
                // 子情况1.1：y == y2（右边界也达最小，整个区间处理完毕）
                if (y == y2) {
                    // 所有位置的答案加上当前集合的标记值，直接返回
                    rep(j, 1, n)ans[j] += tg[i];
                    return;
                }

                // 子情况1.2：右边界未达最小，处理末尾集合
                int j = b[tt];
                if (Y[j] == y2)            // 若集合j的右边界是y2，合并j到i
                    mer(j, i);
                else {
                    X[i] = x2, Y[i] = y2;  // 更新集合i的区间边界
                    b[++tt] = i;          // 重新加入b数组待处理
                }
            }
            // 情况2：x != x2（左边界未达最小）
            else {
                int j = hd[x2];            // 取x2为头的集合j
                if (Y[j] == y2)            // 若集合j的右边界是y2，合并j到i
                    mer(j, i);
                else {
                    X[i] = x2, Y[i] = y2;  // 更新集合i的区间边界
                    pre[i] = hd[x2];       // 接入x2对应的链表
                    hd[x2] = i;            // 更新链表头
                }
            }
        }
    }
}

// 区间初始化与双向处理函数：处理[L,R]区间，计算最终答案
inline void init(int l, int r) {
    n = r - l + 1;  // 当前处理区间的长度（从l到r共n个元素）

    // 1. 构建当前区间的a数组（将原始p数组的[l,r]段映射为1~n的连续下标）
    rep(i, l, r)a[i - l + 1] = p[i] - l + 1;
    // 初始化答案数组：每个位置初始值为n-1（基础贡献）
    rep(i, 1, n)ans[i] = n - 1;
    solve();  // 正向处理当前区间，计算部分答案

    // 2. 反向处理（转换为逆问题，覆盖所有情况）
    rep(i, 1, n)a[i] = n - a[i] + 1;  // 数组值反转（1→n，2→n-1...）
    reverse(a + 1, a + n + 1);        // 数组整体反转
    reverse(ans + 1, ans + n + 1);    // 答案数组同步反转
    solve();                          // 反向处理，补充计算答案

    // 3. 恢复答案数组顺序，输出当前区间的结果
    reverse(ans + 1, ans + n + 1);
    rep(i, 1, n)printf("%lld ", ans[i]);
}

int main() {
    nn = read();              // 读取原始数组长度
    rep(i, 1, nn)p[i] = read();// 读取原始数组p

    int mx = 0, lst = 0;      // mx：当前最大值；lst：上一个区间的结束位置
    // 划分“最大值为当前下标”的区间（如[1,3]、[4,5]等）
    rep(i, 1, nn) {
        mx = max(mx, p[i]);   // 更新当前最大值
        // 若最大值等于当前下标i，说明[lst+1, i]是一个完整区间，处理该区间
        if (mx == i)
            init(lst + 1, i), lst = i;
    }
}