此题正解为线段树，想看正解的请按下Ctrl+W
写这篇题解的缘由
我前两天被超长的代码玩死了，一调就是一下午，尤其是沙雕少女LJJ，不想再码这么多行了。我看到题解里有说用STL的，我便也来了一发
解题过程和大致思想
题解里用到了set 我：?????
便滚去查资料，得出结论：set的作用是按照某种顺序（eg:从大到小）维护一个序列，它有一个兄弟叫multiset，它不像set一样不能有重复的元素，它可以维护重复的元素，但代价是时间复杂度很高:(
这时有人会问，这个set和priority_queue有嘛区别啊。答案就是priority_queue只能访问在顶上的元素，不能像set一样访问中间的元素，但它在插入元素时复杂度是线性的，而set是O(nlogn)的，并且priority_queue可以有重复的元素（和multiset更像）。
我从这里学到的
做题时的注意点:
multiset的大小要开够
后果：
注意比较时是直接用<还是比较它们的成员函数size()的返回值（很明显不一样，单用<会T）
template< class Key, class Compare, class Alloc >
bool operator==( const std::set<Key,Compare,Alloc>& lhs,
const std::set<Key,Compare,Alloc>& rhs ); |
(1) |
|
template< class Key, class Compare, class Alloc >
bool operator!=( const std::set<Key,Compare,Alloc>& lhs,
const std::set<Key,Compare,Alloc>& rhs ); |
(2) |
(until C++20) |
template< class Key, class Compare, class Alloc >
bool operator<( const std::set<Key,Compare,Alloc>& lhs,
const std::set<Key,Compare,Alloc>& rhs ); |
(3) |
(until C++20) |
template< class Key, class Compare, class Alloc >
bool operator<=( const std::set<Key,Compare,Alloc>& lhs,
const std::set<Key,Compare,Alloc>& rhs ); |
(4) |
(until C++20) |
template< class Key, class Compare, class Alloc >
bool operator>( const std::set<Key,Compare,Alloc>& lhs,
const std::set<Key,Compare,Alloc>& rhs ); |
(5) |
(until C++20) |
template< class Key, class Compare, class Alloc >
bool operator>=( const std::set<Key,Compare,Alloc>& lhs,
const std::set<Key,Compare,Alloc>& rhs ); |
(6) |
(until C++20) |
template< class Key, class Compare, class Alloc >
/* see below */ operator<=>( const std::set<Key,Compare,Alloc>& lhs,
const std::set<Key,Compare,Alloc>& rhs ); |
(7) |
(since C++20) |
| | |
Complexity
1-2) Constant if lhs and rhs are of different size, otherwise linear in the size of the set
3-7) Linear in the size of the set
