2023安徽省青少年信息学奥林匹克(AHOI)初中组
2023AHOI初中-T1- 评分（score）
题目描述
小可在观看跳水比赛中。
在跳水比赛中共有n位选手参赛，并由m位评委担任评分工作。
每位选手完成动作后都会获得由m位评委给出的分数。
每位选手的最终得分为：将所有评委打出分数中去掉一个最高分和一个最低分（若有多个最高或最低分则仅去除一个）后的平均值。
根据这些计算出的分数进行排序：
得分最高的运动员获得第一名，
第二高的运动员获得第二名，
依此类推。
若出现同分情况，
则编号较小的运动员将会排在前面。
例如，
若3号运动员与5号运动员得分均为70，
则3号运动员将被认为比5号运动员排名更高。
目前小可已掌握了所有运动员的各项评分数据，
希望你能根据这些数据计算出最终的排名列表。
输入描述
两个整数n和m分别代表参赛选手的数量与评委的数量。接下来依次列出每个选手的评分数据。其中ai,j是在第i位选手完成动作后由第j位评委打出的分数。
输出描述
输出一行 n 个整数，第 i 个整数表示排名为 i 的选手的编号。
样例输入
4 4
4 70 69 34
18 43 85 71
100 50 69 80
67 82 90 43
样例输出
3 4 2 1
数据范围及提示
四位选手在去除最高分和最低分后的平均得分分别为：51.5、57、74.5和74.5分。然而，在四名参赛者中编号较小的三位（即编号较小者优先）依次获得第1至第4名。针对大约30%的数据情况而言，在这些数据中n和m都不超过3；约6成的数据情况下n和m都不超过10；而全部测试用例中n的取值范围是2到100之间（包含端点），m则在3到100之间（包含端点），每个ai,j的取值均介于包括两端在内的整数范围。
时间限制：1000毫秒********内存限制：256MB
解析：
结构体排序
根据题目要求建立一个结构体用于记录每位参赛者的编号及其总得分，在接收输入数据的过程中同时记录所有评委给出的分数而不进行存储。随后计算所有选手的总分后将最高与最低分数扣除之后所得即为每位参赛者的最终得分。按照既定的排序规则进行排序即可完成整个评分过程。
时间复杂度：O(nlogn)
参考代码
#include<bits/stdc++.h>
using namespace std;
struct P{
int s, id;
} a[105];
int n, m;
bool cmp(P x, P y) {
if(x.s != y.s)
return x.s > y.s;
return x.id < y.id;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int sum = 0, mx = 0, mn = 100, t;
for(int j = 1; j <= m; j++) {
cin >> t;
sum += t;
mx = max(mx, t);
mn = min(mn, t);
}
a[i] = { sum-mx-mn, i};
}
sort(a+1, a+n+1, cmp);
for(int i = 1; i <= n; i++)
cout << a[i].id<< " ";
}2023AHOI初中-T2- 数数（count）
题目描述
小可可与小多多正在拼接木棍。
他们目前拥有n根木棍；其中第i根的长度为ai。
为了计算有多少种方法可以从这些木棍中选出三根并形成一个三角形，请问他们有多少种选择方式？
构成三角形的必要条件是任意两边之和必须大于第三边；也就是说，在任意两根较短的木棍长度之和大于最长的一根时才可以形成三角形。
输入描述
最上端一行的一个正整数 n
输出描述
每个一行的整数都表示共有多少种选择三根木棍的方式，并且这些选出的这三根木棍能够构成三角形。
样例输入
5
3 2 5 3 4
样例输出
8
数据范围及提示
可以选择以下编号方案：（1-4）等。
其中，在20%的情况下，则n值不会超过一百。
在40%的数据中，则n不超过千。
此外，在另20%的数据中，则每个ai都不超过五千元。
其中，在全部数据中，
则n的取值范围为在三到八千之间，
而每个ai都不超过一千万。
时间限制：1000毫秒********内存限制：1024MB
解析
考点：二分查找，双指针扫描
首先，暴力枚举 O(n^3) 可得 40 分左右。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[8005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
long long s=0;
for(int i=1;i<n-1;i++){ //a[i]是第一条边
for(int j=i+1; j<n; j++){ //a[j]是第二条边
int k=n; //a[k]是第三条边
while(k>j&&a[i]+a[j]<=a[k]) k--;
s+=k-j;
}
}
cout<<s;
return 0;
}考虑优化。
排序之后，在遍历完前两条边的基础上，在第三条边上执行二分查找操作。该算法的时间复杂度为O(n² log n)
假设三条边为 a, b, c 且 a ≤ b ≤ c。排序后的情况必然满足：b位于a右侧或与a重合，c位于b右侧或与b重合。由构成三角形的必要条件是任意两边之和大于第三边可知：a + b > c因而可得 a + b > c这一不等式确定了c的可能取值范围。
下面我们可以采用以下方法：首先，在排序后的序列中枚举所有a和b的组合；接着通过二分查找找到第一个不小于a+b的位置，并取其前一个元素p；这样我们可以确保这些元素中所有满足条件c的情况都会被包含进去；最终的时间复杂度为O(n²logn)，这足以保证算法运行效率而不至于超时（处于临界情况时仍可顺利运行）。
那么，在满足条件a≤b≤c且 a+b>c的情况下，请问是否能保证任意两条边之和都大于第三条边？确实如此。经过分析可知，在这种情况下必定有a + c > b 和 b + c > a 成立。因此，该算法所得的结果必然是正确的。
本题要不要开long long 呢？
考虑到极端情况
该方法仍具优化潜力。当变量b向右移动一位时，在满足条件c≥a+b的前提下分析其下界位置的变化情况：它可能保持不变或相较于前一过程中的b的位置更靠右侧；无论如何变化都不会朝左方向移动。基于此，在遍历a的过程中，则可定义指针c用于标记当前最优解的位置；随后，在对变量b进行右移操作时，则需相应地调整指针c的位置以维持最优解关系的完整性。
参考代码
#include<bits/stdc++.h>
using namespace std;
int n, a[8005];
long long ans;
int main() {
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1, a+n+1);
for(int i = 1; i <= n; i++) { // a[i]<a[j]<a[k]
int k = 1;
for(int j = i+1; j <= n; j++) {
//int k = lower_bound(a+j, a+n+1, a[i]+a[j]) - a; // a[k] >= a[i]+a[j] 的第一个k
while(k <= n && a[k] < a[i]+a[j]) k++; //双指针优化
ans += k - j - 1;
}
}
cout << ans;
}2023AHOI初中-T3- 行走（walk）
题目描述
输入格式
输出格式
输出 q 行，每行一个整数，表示删掉给定边后 (1, 1) 到 (n, n) 的最短路。
输入输出样例
输入样例1：
输出样例1：
5
4
7
9
说明
针对20%的数据集而言，则需满足n和q均不超过5且B值为1；而对于40%的数据量级，则要求n和q都不超过3百；在70%的数据规模下，则仅需保证n值小于等于3百；至于全部的数据情况，则规定n的取值范围在2至5千之间（含端点），同时q的数量控制在1万以下（含端点），B变量被限定于1至3十之间（含两端），x、y以及x’、y’变量均取自同一定义域内。
void xorshift64() {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
}
main(){
……
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
xorshift64();
ea[i][j]=seed&((1>>B)-1);
}
}
for(int j=1;j<=n-1;j++){
for(int i=1;i<=n-1;i++){
xorshift64();
eb[i][j]=seed&((1>>B)-1);
}
}
……
}时间限制：2000毫秒********内存限制：1024MB
解析
考点：线性dp
我们来分析一下，如果你没信心写对本题，只冲着部分分去，能拿多少分：
20 分
20 分
70分
70分
70分
上述思路的代码都很容易实现。
正解：正序+倒序 DP
题意：
考虑一个 n×n 的网格图，在仅允许向右或向下移动的情况下（即不允许对水平或垂直方向进行回退），每条边上赋予随机生成的权重值（即边权为随机数）。针对 q 组查询（即一组或多组查询），每次移除一条关键路径上的边（即割掉某条特定的路径），请求计算新的最短路径长度（即求解在移除某条特定路径后的新最短路径长度）。
n≤5000，边权小于 2^30
分析：
既然决定移除一条边，我们自然会考虑到用另一条边来代替被移除的边。假设我们选择移除一条从左到右延伸的边（如图中用红色荧光笔标注的那条边），那么从起点(1,1)到终点(n,n)的最短路径必定会经过图中用绿色荧光笔标注的那条路径；因为如果不经过这条绿色荧光笔标注的路径，则从(1,1)到(n,n)就无法到达了。
对于同一列jj中的所有边ei,j来说，在保证能够到达终点的情况下（即起点(1,1)到终点(n,n)必须经过这条特定的边ei,j），我们可以计算从起点(1,1)到终点(n,n)经过这条边ei,j的最短路径长度（记为disti,j）。通过这样的计算分析可以看出，在这种情况下（即移除某条特定的边ei,j后），我们可以记录下该列中disti,j的所有次小值；这些次小值将帮助我们判断是否需要对该条被移除的边进行补偿处理。否则如果这条被移除的edge不是该列所有disti,j中的最小者，则表明移除这条edge并不会影响整体路径的选择；因此，在实际计算时我们只需针对每一列记录其对应各条边上出现过的最短距离及其次优解即可。
对于删除的边是从上到下的情况也是同理。
现在我们探讨如何维护通过某条边的最短路 disti,j。实际上这个过程相当直接。具体来说只需要从起点(1,1)出发进行一次正向遍历（基于矩阵的动态规划）。然后反向进行一次遍历（同样基于矩阵的动态规划）。假设这条边是从(x₁,y₁)指向(x₂,y₂)，那么沿着这条边走的最短路径即等于起点到该节点的距离加上终点到该节点在反向图中的距离再加上这条边的实际权重值。
时间复杂度 O(n^2 + q)，注意空间利用率。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, q, B, x, y, xp, yp;
long long ea[N][N], eb[N][N];
// wa1/2[i]: 通过第 i 列的横向边的所有路径中的总距离的最小/次小值
// wb1/2[i]: 通过第 i 行的纵向边的所有路径中的总距离的最小/次小值
long long wa1[N], wb1[N], wa2[N], wb2[N];
long long f[N][N], g[N][N];
unsigned long long seed;
void xorshift64() {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
}
int main(){
cin >> n >> q;
cin >> seed >> B;
for (int i = 1; i <= n; i++) {
for (int j = 1; j != n; j++) {
xorshift64();
ea[i][j] = seed & ((1ll << B) - 1);
}
}
for (int i = 1; i != n; i++) {
for (int j = 1; j <= n; j++) {
xorshift64();
eb[i][j] = seed & ((1 << B) - 1);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == 1 && j == 1) continue;
f[i][j] = 1e18;
if(i-1 > 0) f[i][j] = min(f[i][j],f[i-1][j]+eb[i-1][j]);
if(j-1 > 0) f[i][j] = min(f[i][j],f[i][j-1]+ea[i][j-1]);
}
}
for(int i = n; i >= 1; i--) {
for(int j = n; j >= 1; j--) {
if(i == n && j == n) continue;
g[i][j] = 1e18;
if(i+1 <= n) g[i][j] = min(g[i][j],g[i+1][j]+eb[i][j]);
if(j+1 <= n) g[i][j] = min(g[i][j],g[i][j+1]+ea[i][j]);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j != n; j++) { // cut from top to bottom
ea[i][j] = f[i][j] + g[i][j+1] + ea[i][j];
if(wa1[j] == 0) wa1[j] = i;
else if(ea[i][j] <= ea[wa1[j]][j]) wa2[j]=wa1[j], wa1[j]=i;
else if(wa2[j]==0 || ea[i][j] < ea[wa2[j]][j]) wa2[j] = i;
}
}
for(int i = 1; i != n; i++) {
for(int j = 1; j <= n; j++) {
eb[i][j] = f[i][j] + g[i+1][j] + eb[i][j];
if(wb1[i] == 0) wb1[i] = j;
else if(eb[i][j] <= eb[i][wb1[i]]) wb2[i]=wb1[i], wb1[i]=j;
else if(wb2[i]==0 || eb[i][j] < eb[i][wb2[i]]) wb2[i] = j;
}
}
while(q--) {
cin >> x >> y >> xp >> yp;
if(x == xp) { // 删横向边
if(x==wa1[y]) cout << ea[wa2[y]][y] <<'\n';
else cout <<ea[wa1[y]][y] << '\n';
} else {
if(y==wb1[x]) cout << eb[x][wb2[x]] <<'\n';
else cout <<eb[x][wb1[x]] << '\n';
}
}
return 0;
}2023AHOI初中-T4- 石子 (stone)
题目描述
面对着小可可的是n堆互不相连的石子堆，在第i个位置上放置了数量为a_i的石头。游戏规则规定，在每一轮操作中玩家可以选择任意一堆石头作为起点，并依次向左或向右方向连续进行相邻两堆之间的合并操作。每一次将数量分别为x和y的两相邻石头堆进行结合时（即完成一次"合并"动作），玩家需要消耗掉(x + y)点体力值，并获得一个新的石头数量为(x + y)的新石头堆。
小可可想通过最少的力量从最初选定的那一堆石子开始进行合并操作，并使所有的石子最终形成单一的一堆。为了达到这一目标，在不同起始点的选择下所需的力量计算会有所变化。
小可可不想太为难你，所以他保证所有的ai是随机的。
输入格式
在第一行处指定三个整数n、l、r，分别表示石子堆的数量及其起始编号区间
第二行输入 n 个整数 a1, a2, · · · , an，表示每堆石子的石子个数。
输出格式
输出一行由r−l+1个整数组成；每个整数对应于小可可选择编号为l−1+i 的石子堆作为初始一堆的情况下的最小体力值计算结果。
输出一行由r−l+1个整数组成；每个整数对应于小可可选择编号为l−1+i 的石子堆作为初始一堆的情况下的最小体力值计算结果。
输入输出样例
输入样例1：
4 1 4
5 1 3 1
输出样例1：
25 19 19 19
说明
样例说明：
在处理第1堆石子时将其视为初始堆的情况下 最有效的策略是在此之后依次合并 第2到第4堆 然后依次进行后续两步操作 这样总共消耗的力量值为25
以第二堆石子作为初始子堆，在应用最理想的策略时，首先处理第三堆石子；接着依次处理第四堆和第一堆；整个过程所需耗费的力量计算为19单位。
在初始状态下以第3堆石子作为基准，在最有效的策略下先处理第2堆石子后依次处理第4堆和随后处理第1堆石子时所消耗的力量值为19
对于第4堆石子以初始石子堆的身份开始，在最佳(也是唯一的)的策略下，依次将第3堆、接着是第2堆、最后是第1堆进行合并操作。这样总共耗费的力量为19单位。
数据规模与约定
占总数据量的 20% 的测试用例中将满足 n 值不超过 10；在剩下的测试用例中，则分为两个部分：40% 的情况满足 n 值不超过 300；而剩余的测试用例则需要满足两个条件：一是 n 值不超过 10^5；二是区间长度 r − l + 1 不超过 50；为了全面覆盖各种复杂度情况，在全部测试用例中保证以下约束条件成立：即 l 和 r 满足关系式 1 ≤ l ≤ r ≤ n，并且 n 的最大值为 10^5；同时每个 ai 值均在 [1, v] 区间内随机选取（其中 v 是所有 ai 上界的最大值）。
时间限制：1000毫秒********内存限制：1024MB
解析
考点：区间DP,DP优化
一：区间DP（暴力 60 分）
思路分析：
我们定义 f[l][r] 用来表示，在完成区间 [l,r] 的合并之后，在将整个区间 [1,n] 转化为单一的整体时所需付出的最小努力量。
如此，易得状态转移方程如下：
f[l][r]=min(f[l−1][r]+sum[l−1][r],f[l][r+1]+sum[r+1][l])
其中 sum[l][r] 指该区间的元素总和。即合并该操作所需的计算量。为了高效计算这一数值序列的累加结果，在算法设计中通常采用前缀和数组这一数据结构来进行存储与快速查询的操作。
时间复杂度：O(n^2)
参考代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
int n, L, R, a[N];
long long f[N][N], sum[N];
int main(){
cin >> n >> L >> R;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
for(int len = n-1; len >= 1; len--) {
for(int l = 1, r = l+len-1; r <= n; l++, r++) {
f[l][r] = 1e18;
if(l-1>=1) f[l][r] = min(f[l][r], f[l-1][r]+sum[r]-sum[l-2]);
if(r+1<=n) f[l][r] = min(f[l][r], f[l][r+1]+sum[r+1]-sum[l-1]);
}
}
for(int i = L; i <= R; i++) cout << f[i][i] << ' ';
}二：单调栈优化 区间DP / 贪心
题意：
考虑一个长度为n的序列{a_i}（i=1到n），我们需要选择一个起始点x（1 ≤ x ≤ n），并从该起始点开始向左或向右展开"石子归并过程"：每次操作将相邻两个元素相加形成一个新的元素，并使新的元素等于它们之和；同时所增加的成本即为其总和。（注：这里的"石子归并"指的是将两个相邻元素合并成一个新的元素）给定区间[l, r]（l ≤ r ≤ n），求当起始点分别取自区间内的每个整数值时对应的最小总成本分别为多少？已知n ≤ 1e5且a_i ∈ [1, 1e8]）。
分析：
遇到随机的题目，我们需要打表找一下性质。
对于这个问题而言，在解决时我们采用了一个时间复杂度为O(n²)的方案。对于每一个区间长度l来说，在处理完长度为l-1的所有区间后，我们需要进一步处理长度为l的区间并最终将它们合并成一个完整的序列。定义f[l][r]表示我们已经处理并合并了区间[l, r]中的所有数，并在此基础上考虑如何将其扩展到更大的区间范围。为了将当前区间进一步扩展至整个[1, n]范围并完成计算，则需要考虑所附加的代价。对于每一个状态而言，在决策时我们只有两种可能的选择：要么选择当前区间的左侧相邻元素l-1作为新的扩展方向之一；要么选择右侧相邻元素r+1作为另一个可能的方向选项。于是可以得到状态转移方程：
f\left[l\right]\left[r\right]=\mathrm{min}\left(f\left[\left(l-1\right)\right]\left[r\right]+sum\left[\left(l-1\right)\right]\left[r\right],f\left[l\right]\left[\left(r+1\right)\right]+sum\left[l\right]\left[\left(r+1$$\right)\right] ) ，其中 sum \left[ l-1 \, , \, r \right] 为将已经合并到一块的 \text{[} l, r \text{]} 区间进行求和
合并的成本即为该区间的数值之和；同理,sum[l][r+1]同样是将已合并至统一区域[l,r]的数据与后续元素进行整合
合并的代价。 sum可以用前缀和优化，起始位置为 x时，答案存放在 f[x][x]。
这些细节倒是可以忽略。关键在于有了该程序之后我们能够生成一个表格来辅助后续分析。通过引入辅助数组g(l,r)，其作用是区分f(l,r)向左扩展还是向上扩展。其中转移方向由状态变量指示：0代表向左扩展（l减小），而1代表向上扩展（r增加）。
通过系统测试（打表），我们能够观察到我们的程序始终遵循一种特定模式：它会持续地采取一段连续的 0 后面紧跟一段连续的 1 ，然后再重复这一过程。
经过深入分析后会发现，在转换过程中从状态0到1以及从状态1返回到0的次数极少,仅约几十次.进而推断出该系统的变化频率仅为O(logn).
接下来我们致力于证明，在随机数据的情形下，那些部分平均值小于整体平均值的分段数量为O(logn)。
基于期望具有的线性可加性质
上述思路的贪心优化：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
typedef pair<ll, int> Pr;
int n, l, r;
// sum[i]: a[i] 的前缀和 isum[i]：i*a[i] 的前缀和
ll a[N], sum[N], isum[N];
Pr stk[N]; int top; // 单调栈
// pre[i]: 区间往左选择时，第 pre[i]~i 个元素连续选取是更优的
// suf[i]: 区间往右选择时，第 i~suf[i] 个元素连续选取是更优的
int pre[N], suf[N];
int pos[N]; // 单调栈中保存端点用
// 判断区间 a 内的平均值是否小于区间 b 的平均值
bool small(Pr a, Pr b) {
return a.first * b.second < b.first * a.second;
}
Pr merge(Pr a, Pr b) {
return make_pair(a.first+b.first, a.second+b.second);
}
ll get_l_sum(int l, int r, int q) {
// 计算 a[r]*q + a[r-1]*(q-1) + ... + a[l]*(q-r+l)
return isum[r]-isum[l-1] + (q-r)*(sum[r]-sum[l-1]);
}
ll get_r_sum(int l, int r, int q) {
// 计算 a[l]*q+a[l+1]*(q-1)+...+a[r]*(q-r+l)
return -(isum[r]-isum[l-1]) + (q+l)*(sum[r]-sum[l-1]);
}
ll solve(int x) {
// 获取往左的分段的区间端点
vector<int> ls, rs;
int pts = x-1;
while(pts) {
ls.push_back(pts);
pts = pre[pts];
} ls.push_back(0);
pts = x+1;
while(pts != n+1) {
rs.push_back(pts);
pts = suf[pts];
} rs.push_back(n+1);
reverse(ls.begin(), ls.end());
reverse(rs.begin(), rs.end());
int p = ls.size()-1, q = rs.size()-1; // p/q: x 左/右边段区间数量
ll ans = a[x]*(n-1); // a[x] 被合并了 n-1 次
while(p || q) {
int rest = ls[p] + n-rs[q]+1; // 剩余未合并的元素数量
if(p && q) {
// 获得左右的区间的元素和 与 长度，用于计算平均值
// [...p-1][...p]...[x]...[q...][q-1...]
Pr sp = make_pair(sum[ls[p]]-sum[ls[p-1]], ls[p]-ls[p-1]);
Pr sq = make_pair(sum[rs[q-1]-1]-sum[rs[q]-1], rs[q-1]-rs[q]);
if(small(sp, sq)) { // 选择合并左边的区间更优
ans += get_l_sum(ls[p-1]+1, ls[p], rest);
p--;
} else {
ans += get_r_sum(rs[q], rs[q-1]-1, rest);
q--;
}
} else if(p) { // 只剩下左边
ans += get_l_sum(ls[p-1]+1, ls[p], rest);
p--;
} else { // 只剩下右边
ans += get_r_sum(rs[q], rs[q-1]-1, rest);
q--;
}
}
return ans;
}
int main(){
cin >> n >> l >> r;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
isum[i] = isum[i-1] + i*a[i];
}
// 预处理，向左连续选择的区间段
top = 0;
for(int i = 1; i <= n; i++) {
Pr now = make_pair(a[i], 1);
// 当前区间 stk[top] 的平均值小于右侧区间 now，说明从 now 往左合并平均值会更小，就合并
while(top && small(stk[top], now)) {
now = merge(now, stk[top]);
top--; // 将栈顶区间弹出，合并（更优）
}
pre[i] = (top ? pos[top] : 0);
stk[++top] = now;
pos[top] = i; // pos[i]: 栈顶 i 的区间右端点(从左往右选的区间的起点)
}
// 预处理，向右连续选择的区间段
top = 0;
for(int i = n; i >= 1; i--) {
Pr now = make_pair(a[i], 1);
// 当前区间 stk[top] 的平均值小于左侧区间 now，说明从 now 往右合并平均值会更小，就合并
while(top && small(stk[top], now)) {
now = merge(now, stk[top]);
top--; // 将栈顶区间弹出，合并（更优）
}
suf[i] = (top ? pos[top] : n+1);
stk[++top] = now;
pos[top] = i; // pos[i]: 栈顶 i 的区间左端点(从右往左选的区间的起点)
}
for(int i = l; i <= r; i++)
cout << solve(i) << ' ';
return 0;
}