题目分析

题意简述

输入一系列测试数据，每组数据以一个字符 $ks$ 开始，若 $ks$ 为 '-' 则结束程序；否则，输入一个整数 $n$ 以及 $n$ 个整数数据 $lst[i]$（$1 \leq i \leq n$） 。通过构建一棵线段树，基于树的操作和相关计算，输出特定的结果。若 $n = 1$ ，直接输出 $1$；若 $n > 1$ ，经过一系列处理后输出一个计算得到的数值。每组数据输出结果之间以逗号分隔（第一组数据除外） 。

输入

• 多组测试用例，每组以一个字符 $ks$ 开始。
• 若 $ks$ 为 '-' ，程序结束；否则，输入一个整数 $n$ ，接着是 $n$ 对数据（每对数据为一个整数 $lst[i]$ 和一个字符 $fei$ ，其中 $fei$ 作用不明确，代码中未体现其核心作用 ）。

输出

• 对于每组输入数据（除最后一组以 '-' 结束的特殊情况），输出一个计算结果。若 $n = 1$ ，输出 $1$；若 $n > 1$ ，输出经过复杂计算处理后的数值，多组结果之间以逗号分隔（第一组结果前无逗号）。

解题思路

线段树构建

通过 buildTree 函数，以递归方式构建一棵线段树。树节点 $numb$ 存储区间 $[s, e]$ 的长度 $e - s + 1$ ，将区间不断二分递归构建左右子树，为后续的区间查询和节点删除操作提供基础。

线段树操作

• 删除操作：使用 del 函数，当需要删除某个位置 $pos$ 的节点时，从根节点开始，根据 $pos$ 与区间中点 $mid$ 的关系，递归地在左子树或右子树中进行删除操作，并更新对应节点存储的区间长度（使其减 1 ）。
• 查询操作：query 函数用于查询区间 $[qs, qe]$ 的相关信息。根据查询区间与当前节点所代表区间 $[s, e]$ 的关系，分情况递归查询左子树、右子树或同时查询左右子树，并将结果合并返回。

结果计算

在主程序中，先根据输入数据构建线段树，然后通过 query 和 del 操作，获取一系列数值 $q[i]$ 。基于这些数值，通过循环计算数组 $gjd$ ，在计算过程中处理进位，最终将 $gjd$ 数组逆序输出，得到每组数据对应的结果。

代码实现

#include <iostream>
#include <stdio.h>
using namespace std;

void buildTree(int s, int e, int *src, int numb){
    src[numb] = e - s + 1;
    if(s == e) return;
    int mid = (s + e) / 2;
    buildTree(s, mid, src, 2 * numb + 1);
    buildTree(mid + 1, e, src, 2 * numb + 2);
}

void del(int s, int e, int *src, int numb, int pos){
    src[numb]--;
    if(s == e) return;
    int mid = (s + e) / 2;
    if(pos <= mid) del(s, mid, src, 2 * numb + 1, pos);
    else del(mid + 1, e, src, 2 * numb + 2, pos);
}

int query(int qs, int qe, int s, int e, int *src, int numb){
    if(qe < qs) return 0;
    if(qs == s && qe == e) return src[numb];
    int mid = (s + e) / 2;
    if(qe <= mid) return query(qs, qe, s, mid, src, 2 * numb + 1);
    if(qs > mid) return query(qs, qe, mid + 1, e, src, 2 * numb + 2);
    return query(qs, mid, s, mid, src, 2 * numb + 1) + query(mid + 1, qe, mid + 1, e, src, 2 * numb + 2);
}

int main() {
    char fei, ks;
    bool dyg = 1;
    while(1){
        cin >> ks;
        if(ks == '-') {
            cout << endl;
            return 0;
        }
        if(!dyg) cout << ",";
        dyg = 0;
        int n;
        cin >> n;
        cin >> fei >> fei;
        int lst[55];
        for(int i = 1; i <= n; i++){
            cin >> lst[i] >> fei;
        }
        //for(int i = 1; i <= n; i++) cout << lst[i] << " "; cout << endl;
        cin >> fei;
        if(n == 1) {
            cout << 1;
            continue;
        }
        int xds[500];
        buildTree(1, n, xds, 0);
        int q[500];
        for(int i = 1; i < n; i++){
            q[i] = query(1, lst[i] - 1, 1, n, xds, 0);
            del(1, n, xds, 0, lst[i]);
        }
        //for(int i = 1; i < n; i++) cout << q[i] << " "; cout << endl;
        int gjd[500] = {0};
        int ws = 1;
        for(int i = 1; i < n; i++){
            gjd[0] += (q[i] + (i == n - 1 ? 1 : 0));
            if(n - i - 1){
                for(int j = 0; j < ws; j++){
                    gjd[j] *= (n - i);
                }
            }
            int carry = 0;
            for(int j = 0; j < ws; j++){
                gjd[j] += carry;
                carry = gjd[j] / 10;
                gjd[j] %= 10;
            }
            while(carry){
                gjd[ws] = carry;
                carry = gjd[ws] / 10;
                gjd[ws] %= 10;
                ws++;
            }
        }
        for(int i = ws - 1; i >= 0; i--){
            cout << gjd[i];
        }
    }
    return 0;
}

代码说明

1. 函数定义
   • buildTree 函数：接受区间起始位置 $s$ 、结束位置 $e$ 、存储线段树的数组 $src$ 以及当前节点编号 $numb$ ，构建线段树，为每个节点存储对应区间的长度。
   • del 函数：根据给定的位置 $pos$ ，在以 $[s, e]$ 为区间、根节点为 $numb$ 的线段树中删除对应节点，并更新相关节点的区间长度。
   • query 函数：在以 $[s, e]$ 为区间、根节点为 $numb$ 的线段树中，查询区间 $[qs, qe]$ 的信息，根据不同情况递归查询子树并合并结果。
2. 主程序逻辑
   • 通过循环读取输入数据，根据字符 $ks$ 判断是否结束程序。
   • 读取整数 $n$ 和 $n$ 个数据 $lst[i]$ 后，若 $n = 1$ 直接输出 $1$；若 $n > 1$ ，先构建线段树，再进行查询和删除操作得到数组 $q$ ，最后通过一系列计算得到数组 $gjd$ 并逆序输出结果 。在多组结果输出时，控制结果之间以逗号分隔 。