CF1883D In Love 题解

蒟蒻没用过 $multiset$，只好用优先队列。

问题简述

正方向数轴上，每次可能给出一条线段或删除一条线段，每次操作后判断是否存在两条不相交线段。

题目分析

只要贪心，找到当前存在的线段里最大的 $l$ 和最小的 $r$，满足 $l_{max} \gt r_{min}$，就好啦。( 读题时读成了判断是否存在相交的线段，以为是什么奇怪的数据结构题。 )(第一次写题解。)

实现思路

我们要删除一条线段时，先记录一下，但不删除。等到要使用这条它的时候，再删掉它。换句话说，只有当删除的线段的 $l$ 是当前所有线段最大或者 $r$ 是当前所有线段最小的时候，也就是马上影响咱们结果的时候，把它删掉。

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define foo(i,a,b) for(int i=a;i<=b;i++)
#define fro(i,a,b) for(int i=a;i>=b;i--)
//#define int long long
const int N=5e5+10;
typedef pair<int,int> PII;
typedef long long LL;

int q;
int a,b;
char m;
priority_queue<int,vector<int>,greater<int>>r,dr;
priority_queue<int,vector<int>>l,dl;
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>q;
	while(q--)
	{
		cin>>m>>a>>b;
		if(m=='+')
		{
			l.push(a);
			r.push(b);
		}
		else
		{
			dl.push(a);
			dr.push(b);
		}
		while(dr.size()&&r.top()==dr.top())r.pop(),dr.pop();
		while(dl.size()&&l.top()==dl.top())l.pop(),dl.pop();
		if(l.size()>1&&l.top()>r.top())cout<<"YES";
		else cout<<"NO";
		cout<<"\n";
	}
}