Tag-STL

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-09-19 14:42:30 |  0 Comments  |  splay STL

Nowcoder Muti-School Training 2 H Happy Triangle multiset + splay平衡树

题目大意

维护一个多重集合,支持三种操作:

  • 1 : 加入一个x
  • 2 : 删除一个x
  • 3 : 询问当前在多重集中,是否存在两个数a,b,使得x能与a,b组成一个合法的三角形

题解

这题有线段树动态建点和离线离散化建线段树的做法,但是平衡树的做法一定是最好想的。

考虑查询操作我们可以假设下面两种情况:

  1. x为唯一最大边,则要a,b都小于x,于是只需要找比x更小的两个前驱作为a,b,判断a+b>x是否成立即可。
  2. x不是唯一最大边,假设b≥a,于是我们需要b≥x && b - a < x,而b-a最小的条件一定是b确定的情况下,a是b的一个非严格前驱,这样我们只需要找x的后缀最小值就行了。

第一种情况非常简单,直接用multiset维护、查询就行了,只需要注意一下边界问题。

第二种情况比较麻烦,没法用STL做,所以就用平衡树维护。平衡树维护的信息为子树内相邻两数差的最小值,排序的键值为当前数的大小,查询答案的时候,找到x的后缀节点,然后判断此节点与前一个节点的差mnval和其右子树中的相邻两数差的最小值mn中的最小值是否<x即可。

需要注意考虑边界问题。

最后提示的一点,s.lower_bound(x)和s.upper_bound(x)是比lower_bound(s.begin(),s.end(),x)和upper_bound(s.beign(),s.end(),x)要快不少的。我就被坑了……。

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
multiset<int>s;
const int maxn = 2e5+5;
typedef pair<int,int> PI;
struct splay_node{
    int siz;
    PI val;
    int mn;
    splay_node *fa,*ch[2];
    void update(){
        mn = min(val.second,min(ch[0]->mn,ch[1]->mn));
    }
    void set_ch(int type,splay_node *child);
    int get_wh(){
        return (this == this->fa->ch[0]) ? 0 : 1;
 2019-01-18 23:26:17 |  0 Comments  |  STL

[转载]6 个技巧,提升 C++11 的 vector 性能

6 个技巧,提升 C++11 的 vector 性能

Vector 就像是 C++ STL 容器的瑞士军刀。Bjarne Stoutsoup 有一句话 – “一般情况下,如果你需要容器,就用 vector”。像我们这样的普通人把这句话当作真理,只需要照样去做。然而,就像其它工具一样,vector 也只是个工具,它能提高效率,也能降低效率。

这篇文章中我们可以看到 6 种优化使用 vector 的方法。我们会在最常见的使用 vector 的开发任务中看到有效的方法和无效的方法,并以此衡量有效使用 vector 会带来怎样的性能提升,并试图理解为什么能得到这样的性能提升。

性能测试的搭建和方法:

  • 所有测试都在我的 Surface Book 中运行,这台笔记本拥有主频 2.6Ghz 的酷睿 i7 处理器,8 GB 内存,安装了 Windows 10 操作系统并使用 VS2015 C++ 编译器编译运行。

  • 我们会使用 Stopwatch。这个工具由 Kjell 创建,在 https://github.com/KjellKod/Stopwatch 可以找到。

  • 我们会运行每个测试 100 次,然后计算平均运行时间来作为依据。运行测试的代码在这里。你可以自由下载,用于在你自己的系统中评估 vector 的性能。那里提供的代码段只反映了一次循环,这让事件变得简单。

  • 我们在 vector 中存入 TestStruct 结构的数据,并使用 FillVector() 来填充 vector。它们的定义如下。

// Test struct to be inserted/removed from vector
struct BigTestStruct
{
  int iValue = 1;
  float fValue;
  long lValue;
  double dValue;
  char cNameArr[10];
  int iValArr[100];
};
// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
  for (int i = 0; i < 10000; i++)
  {
    BigTestStruct bt;
    testVect
Title - Artist
0:00