小沙の赌气

前言：你干嘛，哈哈，哎呦，赌，赌什么嘛

题目来源

今天这道题来自于2023牛客寒假算法集训营，链接如下：

D-小沙の赌气_2023牛客寒假算法基础集训营5 (nowcoder.com)

下面给出该题的题面

原题题面

小沙和小雅在一起打游戏，因为赌气，他们想要比比看谁打通的关卡数更多，在游戏过程中，他们两个人都可以获得一些奇怪的道具来帮助他们通关，假设小沙和小雅都从第一关开始，他们必须一关一关通，只有通过了第 x 关，第 x+1 关才会解锁。每次同时卡关他们各自会获得了一个道具，第 i个道具可以使他们通过 [li ri]之间的每一关，在获得每个道具之后，小沙想询问你目前已有的道具游玩下去，谁会领先，领先多少。

输入格式

第一行输入一个数 n ，代表 n 个发放道具，1 ≤ n≤ 10^5。

接下来 n 行，每行输入两个整数 1≤ l ≤ r ≤ 10^9 ，代表小沙获得的游戏道具能帮助他通过哪些关卡。

接下来 n 行，每行输入两个整数 1≤ l ≤r ≤ 10^9，代表小雅获得的游戏道具能帮助她通过哪些关卡。

输出格式

对于每一次获得道具后，目前的领先状况。

每次询问共输出两行

第一行输出一行字符串代表答案。

如果小沙通过的更多输出”sa_win!“(不包含引号);

如果小雅通过的更多输出”ya_win!“(不包含引号);

如果通过的一样多输出”win_win!“(不包含引号)。

第二行输出一个整数代表多通过的关卡数。

输入样例：

输出样例：

ya_win!
2
ya_win!
1
ya_win!
2

题目解释

这道题实际上好像是八仙过海？(出题人说，很多人的理解和解法都不同)，通过一系列的思考，这里主要给出的是我个人所理解的一种解题办法

朴素思路

首先，我们要清楚当小沙或是小雅得到了道具之后，这个道具是可以一直使用的，这也就意味着对于一开始不可以使用的道具我们是要保存下来的，这也就加大了这道题的难度，如此一来我就想到了第一种解法，把所有的道具先开数组存起来，然后依次遍历，对于可以使用的道具，我们就更新小沙或是小雅的最大通光量，这种思路固然正确，但是在时间上的复杂度就很高了，过不了的

优化

为此，我们要对这种朴素思路进行优化，最后我想到了用队列来写，只要这个道具没有用了或者说我用过了，那么我就把这个道具给从队列移出来，这种方法是可行的

更新最大通关数

现在有了一个问题，我们该如何知道小沙或是小雅在目前所有道具的使用下可以到第几关呢？我们可以开两个变量来保存他们的通关数，只要满足他们目前的通关数 >= 该道具的最小值 - 1，那么我们就可以使用这个道具，为什么是减一？很简单，假如现在小沙过到了第0关，第一个道具可以让小沙过1到3关，那么小沙的最大通关量就刷新成3了，但是如果第二个道具可以让小沙通过5到114514关，但是小沙没有通过第4关，那么第二个道具对于小沙来说就没有用了，hh

`ac`代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
//开的保存数组
int l1[N], l2[N], r1[N], r2[N];
//结构体内部排序(从小到大排)
struct edge{
    int l, r;
    bool operator < (const edge &b) const {
        return l == b.l ? b.r < r : b.l < l;
    }
};

int main()
{
    cin >> n;
    //存储
    for(int i = 0;i < n;i++) {
        cin >> l1[i] >> r1[i];
    }
    for(int i = 0;i < n;i++) {
        cin >> l2[i] >> r2[i];
    }
    //开两个优先队列
    priority_queue<edge> a, b;
    //记录目前两个人所到达的最大通关数
    int idx1 = 0, idx2 = 0;
    for(int i = 0;i < n;i++) {
        //加入队列
        a.push({l1[i], r1[i]});
        b.push({l2[i], r2[i]});
        //队列不为空
        while(a.size()) {
            auto t = a.top();
            //满足更新条件
            if(t.l - idx1 <= 1) {
                //取最大值
                idx1 = max(idx1, t.r);
                a.pop();
            }
            else break;
        }
        //同上
        while(b.size()) {
            auto t = b.top();
            if(t.l - idx2 <= 1) {
                idx2 = max(idx2, t.r);
                b.pop();
            }
            else break;
        }
        //输出答案
        if(idx1 > idx2) cout << "sa_win!" << endl;
        else if(idx1 == idx2) cout << "win_win!" << endl;
        else cout << "ya_win!" << endl;
        cout << abs(idx1 - idx2) << endl;
    }
    return 0;
}