题解：P13730 【MGVOI R1-B】完美重排（sort）

for each query(x,y):
    v = a[x]
    count = 0
    for L=1 to x:
        for R=y to n:
            复制a[L..R]并排序
            if 排序后v在位置y:
                count++
    output count

for each query(x,y):
    v = a[x]
    count = 0
    for L=1 to x:
        for R=y to n:
            k = 区间[L..R]中小于v的元素数
            if L + k == y:  // 排序后v的位置公式
                count++
    output count

for each query(x,y):
    v = a[x]
    预处理前缀和p[i] = [1..i]中小于v的元素数
    count = 0
    for L=1 to x:
        for R=y to n:
            k = p[R] - p[L-1]  // 区间[L..R]中小于v的数量
            if L + k == y:
                count++
    output count

for each query(x,y):
    v = a[x]
    预处理前缀和p[i] = [1..i]中小于v的元素数
    count = 0
    for L=1 to x:
        need = y - L  // 所需小于v的元素数
        target = need + p[L-1]
        // 在p[y..n]中找等于target的数量（二分）
        count += upper_bound(p[y..n], target) - lower_bound(p[y..n], target)
    output count

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n,q;  // n:数组长度，q:查询次数
    cin>>n>>q;
    vector<int> a(n+5,0);  // 存储原数组(1-based索引)
    vector<int> p(n+5,0);  // 用于存储前缀和(每个查询单独计算)
    
    // 读入数组元素
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    
    // 处理每组查询
    while(q--){
        int x,y;  // 查询参数：原位置x，目标位置y
        cin>>x>>y;
        int d = a[x];  // d为原x位置的元素值
        
        // 计算前缀和数组p：p[i]表示[1..i]中小于d的元素个数
        for(int i=1;i<=n;i++){
            p[i] = p[i-1] + (a[i] < d);  // 累加计数
        }
        
        long long ans = 0;  // 存储当前查询的答案
        
        // 枚举所有可能的L(L<=x，因x必须在[L,R]区间内)
        for(int l=1;l<=x;l++){
            // 计算目标前缀和：需要[L..R]中小于d的元素数为(y - l)
            // 因此p[R] = (y - l) + p[L-1]
            int target = (y - l) + p[l-1];
            
            // 在p[y..n]中查找等于target的元素个数
            // lower_bound找到第一个>=target的位置
            auto l1 = lower_bound(p.begin() + y, p.begin() + n + 1, target);
            // upper_bound找到第一个>target的位置
            auto r1 = upper_bound(p.begin() + y, p.begin() + n + 1, target);
            
            // 两个迭代器的差即为符合条件的R的数量
            ans += (r1 - l1);
        }
        
        // 输出当前查询的结果
        cout<<ans<<"\n";
    }
    return 0;//完美结束
}