[Codeforces] CF1719C Fighting Tournament

题目传送门

另：多测不清空，WA两行泪

题意

Burenka正准备去观看一年中最有趣的体育活动 —— 她朋友Tonya组织的格斗锦标赛。

有 n 名运动员参加了大赛，标号分别为为 1，2，... ，n 。第 i 名运动员的实力是 \(a_i（1 \le a_i \le n）\) 。每个运动员的实力是不同的，也就是说，数组 a 是 n 的 一种 全排列 。

大赛的流程是这样的：

一开始，运动员们按标号从小到大排成一列，队头为 1 号运动员，队尾为 n 号运动员。

每轮一次比赛，队头的两个人进行格斗，赢的人（实力较强的人）变成队头，输的人变成队尾 。

Burenka 问了 Tonya q 个问题，每个问题包含两个整数 i 和 k ，表示 i 号运动员在前 k 轮中会胜多少场。

分析

首先可以将这个活动看成一个打擂台，每次实力强的上台，输的下台

那么，可以很容易地发现，如果一个人下台了，那么他就不可能再次上台，因为台上的人的实力一定比他强

所以，一个人胜利的场次一定是一个区间，所以只需要把每个人的范围都预处理一下即可

代码

代码还是挺简单的，但是要注意几个坑：

1. 除了第一个人之外，每个人都是可以和自己身前的人打一架的，所以是比第一个人要多一场的，也就是说第一个人需要减1（我为了方便就写成了-(i==1)）

2. 每个人都是可以最少和身前还有身后两个人打架的，所以当他下台和\(k\)作比较时，记得\(k\)要\(+1\)

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int Maxn=2e5+10;
int n,q,maxn;
struct node
{
    int st,en;
    int data;
}a[Maxn];

void run()
{
    cin>>n>>q;maxn=0;
    for(int i=0;i<=n;i++) a[i].st=a[i].en=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].data;
        if(a[i].data>a[maxn].data) a[maxn].en=i-1,a[i].st=i,maxn=i;
    }
    a[maxn].en=n;
//    for(int i=1;i<=n;i++) cout<<a[i].st<<" "<<a[i].en<<endl;
    while(q--)
    {
        int i,k;
        cin>>i>>k;
        if(k<i-1) cout<<0;
        else if(i==maxn) cout<<k-i+2-(i==1);
        else if(a[i].st==0) cout<<0;
        else cout<<min(k+1,a[i].en)-a[i].st+1-(i==1);
        cout<<endl;
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--) run();
}