multiset(cf-1862-round894-g)

void solve()
{
  int n;cin>>n;
  vector<int>a(n,0);
  for(int i=0;i<n;i++)cin>>a[i];
  multiset<int>b,c{0};
  auto add=[&](int x)
  {
    auto it=b.insert(x);
    if(it!=b.begin())
      c.insert(x-*prev(it));
    if(next(it)!=b.end())
      c.insert(*next(it)-x);
    if(it!=b.begin()&&next(it)!=b.end())
      c.extract(*next(it)-*prev(it));
  };
  auto del=[&](int x)
  {
    auto it=b.find(x);
    if(it!=b.begin())
      c.extract(x-*prev(it));
    if(next(it)!=b.end())
      c.extract(*next(it)-x);
    if(it!=b.begin()&&next(it)!=b.end())
      c.insert(*next(it)-*prev(it));
    b.erase(it);
  };
  for(int i=0;i<n;i++)add(a[i]);
  int ord;cin>>ord;
  for(int i=0;i<ord;i++)
  {
    int x,y;cin>>x>>y;
    del(a[--x]);
    a[x]=y;
    add(a[x]);
    int ans=*b.rbegin()+*c.rbegin();
    cout<<ans<<" \n"[i==ord-1];
  }
}

数据结构

• std::multiset s, d{0}: s 存储输入的整数，d 存储这些整数之间的差值。

算法描述

add 函数

add 函数接收一个整数 x，将其加入到 s 中，并据此更新 d。

1. 插入: auto it = s.insert(x);
2. 找到相邻元素: auto r = std::next(it);
3. 更新差值集合 d: 基于 x 和它的前后元素（如果存在）更新 d。

特点

• 使用了 std::multiset::insert 来插入元素。
• 使用了 std::next 和 std::prev 来找到相邻的元素。

del 函数

del 函数接收一个整数 x，将其从 s 中删除，并据此更新 d。

特点

• 使用了 std::multiset::find 和 std::multiset::erase 来删除元素。
• 使用了 std::multiset::extract 来精确地删除 d 中的元素。

STL 特性和函数

std::multiset

std::multiset 是一个排序的集合，允许存储重复元素。它通常用于需要快速查找、删除和插入操作的场合。

特定用法

• s.insert(x): 插入元素。时间复杂度为 $(O(log n))$。
• s.find(x): 查找元素，返回一个指向元素的迭代器。如果元素不存在，则返回 s.end()。时间复杂度为 (O(\log n))。
• s.erase(it): 删除元素，接受一个迭代器作为参数。时间复杂度为 (O(1))。
• s.extract(x): 精确删除元素，与 erase 不同的是，extract 不会使其他迭代器失效。时间复杂度为 (O(1))。

std::multiset 与 std::priority_queue 的比较

• 查找能力: multiset 允许快速查找任何元素，而 priority_queue 只能快速访问队列中的最大或最小元素。
• 删除操作: multiset 可以删除任何特定元素，priority_queue 只能删除队列顶部的元素。
• 排序: multiset 总是排序的，priority_queue 内部排序但对外表现为部分排序。
• 复杂度: 在 multiset 中插入、删除和查找操作通常具有 (O(\log n)) 的时间复杂度。priority_queue 的插入和删除操作也是 (O(\log n))，但查找（除了顶部元素）则可能需要 (O(n))。
• 迭代器失效: 使用 multiset 的 extract 方法可以避免迭代器失效，这在某些算法中是一个非常有用的特性。priority_queue 没有这样的操作。

与 std::priority_queue 相比，std::multiset 提供了更多的灵活性和查找能力，特别是 std::multiset::extract 函数在算法中的应用具有重要意义。