codeforces （C++ In Love ）

codeforces （C++ In Love ）"/>

codeforces （C++ In Love ）

 题目：

 翻译：

思路：

1、在一个集合中有多组线段，如果有不相交的两组线段，则输出YES，否则输出NO。

2、每次操纵可以选择增加一组线段或者删除一组线段后，输出YES或者NO。

3、用flag标记该线段是否还在集合中，flag=1表示在，flag=0表示不在。

4、找到最大起始点和最小的结束点，当最大的起始点减去最小的结束点大于0，则说明存在两组不相交的线段，输出YES；小于等于，则说明不存在，输出NO。

代码： 

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct node
{long long begin = 0, end = 0;int flag = 1;
}node;
bool cmp1(node a, node b)
{return a.begin > b.begin;
}
bool cmp2(node a, node b)
{return a.end < b.end;
}
int main()
{int n,k=0;char a;node b[12];long long minend = 1e9, maxbegin = 0;cin >> n;for (int i = 0; i < n; i++){cin >> a;long long c, d;cin >> c >> d;if (a == '+')b[k].begin = c, b[k++].end = d;if (a == '-'){for (int j = 0; j < i; j++){if (b[j].begin == c && b[j].end == d && b[j].flag==1){b[j].flag = 0;break;}}}long long minend = 1e9, maxbegin = 0;int v=0;sort(b, b + k, cmp1);//求maxbegin从大到小排序for (int j = 0; j < k; j++){if (b[j].begin >= maxbegin && b[j].flag == 1){maxbegin = b[j].begin;break;}}sort(b, b + k, cmp2);//求minend从小到大排序for (int j = 0; j < k; j++){if (b[j].end <= minend && b[j].flag == 1){minend = b[j].end;break;}}if (i == 0){cout << "NO" << endl;continue;}if (maxbegin - minend > 0)cout << "YES" << endl;elsecout << "NO" << endl;}
}

结果：