题目分析
本题要求维护一个序列 $b$，支持区间修改（对满足 $a_i \leq a_j$ 的 $(i,j)$ 对 $b_j$ 加 1）和单点查询。直接模拟复杂度太高，需要高效算法。

---

算法思路

核心思想：分块 + 二维偏序 + 树状数组

关键观察：

• 修改操作本质是：对每个 $j \in [l,r]$，统计 $i \in [l,j]$ 中满足 $a_i \leq a_j$ 的个数
• 这是一个二维偏序问题：$(i \leq j, a_i \leq a_j)$
• 将 $a$ 的值域分块处理

---

算法流程详解

1. 值域分块

const int B = 650; // 块大小

将值域 $[1,n]$ 分成 $\frac{n}{B}$ 块，分别处理每块对答案的贡献。

2. 数据结构设计

块内信息

int arr[B+2], tot;        // 当前块内的位置
int is[MAXN], rk[MAXN];   // 是否属于当前块，块内排名
int c0[MAXN];             // 前缀计数：值域小于当前块的元素个数

块内树状数组

struct {
    int s[B+2];
    int m;
    void reset(int m0) { m = m0; memset(s,0,sizeof(int)*(m+1)); }
    void preadd(int x) { for(; x; x &= x-1) s[x]++; }
    int qrypos(int x) { 
        int sm = 0;
        for(; x <= m; x += lowbit(x)) sm += s[x];
        return sm;
    }
} ds[B+2];

用于快速查询块内偏序关系。

全局树状数组

namespace fenwick {
ll s0[B+2]; int s1[B+2];
void apply(int l, int r) { // 记录修改区间
    int delt = c0[l-1];
    for(l = rk[l-1]+1; l <= tot; l += lowbit(l)) 
        s0[l] += delt, s1[l]++;
    for(r = rk[r]+1; r <= tot; r += lowbit(r)) 
        s0[r] -= delt, s1[r]--;
}
ll search(int x) { // 查询贡献
    ll sm = 0, per = c0[x];
    for(x = rk[x]; x; x &= x-1)
        sm += per * s1[x], sm -= s0[x];
    return sm;
}
}

3. 主要处理流程

外层循环：按值域块处理

rep(T, 0, n/B) {
    // 预处理当前块信息
    tot = 0;
    rep(i,1,n) {
        is[i] = (p[i]/B == T);  // 是否属于当前值域块
        if(is[i]) arr[++tot] = i;
    }
    // 计算排名和前缀计数
    rep(i,1,n) {
        rk[i] = rk[i-1] + is[i];
        c0[i] = c0[i-1] + (p[i]/B < T);  // 值域小于当前块的个数
    }
}

处理修改操作

if(opt == 1) {
    apply(l, r);  // 记录修改区间
    l = rk[l-1]+1, r = rk[r];
    if(l > r) continue;
    ds[l].preadd(r);  // 更新块内偏序信息
}

处理查询操作

else if(is[l]) {  // 查询点属于当前值域块
    answer[id] += search(l);  // 值域较小块的贡献
    
    // 当前块内的贡献
    int x = rk[l], times = 0;
    rep(y,1,x) {
        times += ds[y].qrypos(x);  // 区间包含关系
        if(p[arr[y]] <= p[arr[x]])  // 值域偏序
            answer[id] += times;
    }
}

---

关键技术与优化

1. 值域分块降低复杂度

• 将 $O(n^2)$ 的偏序对计数降到 $O(\frac{n}{B} \times B^2) = O(nB)$
• 平衡预处理和查询的代价

2. 树状数组高效维护

• 使用树状数组维护前缀和、区间修改
• 低常数、代码简洁

3. 离线处理

• 所有操作一起处理，避免在线算法的高复杂度
• 充分利用预处理信息

4. 空间优化

• 每个值域块独立处理，复用数据结构
• 使用数组而非动态结构，提高缓存命中率

---

复杂度分析

• 预处理：$O(\frac{n}{B} \times n)$
• 修改操作：$O(\frac{n}{B} \times \log B)$
• 查询操作：$O(\frac{n}{B} \times B) = O(n)$
• 总复杂度：$O(\frac{n^2}{B} + q \cdot \frac{n}{B} \log B)$

取 $B = \sqrt{n}$，复杂度为 $O(n\sqrt{n} + q\sqrt{n}\log n)$，对于 $n,m \leq 2\times 10^5$ 可接受。

---

样例验证

对于样例输入，算法正确计算每个查询点的 $b_x$ 值：

• 第一次查询 $x=8$：$b_8=0$
• 后续查询依次为 $4,0,3,4,4$

---

算法优势

1. 理论保证：分块平衡预处理和查询代价
2. 实现高效：树状数组常数小，运行速度快
3. 空间经济：重复利用数据结构，内存占用合理
4. 扩展性强：框架可应用于其他二维偏序问题

该算法通过巧妙的值域分块和树状数组技术，高效解决了大规模区间偏序修改问题。