持续更新

精确位数的定义

cout << fixed << setprecision(r) <<res<< endl;

氧气/臭氧优化

#pragma GCC optimize(2)
#pragma GCC optimize(3)

lower/upper_bound

通俗理解：
在从小到大的数组中，
lower_bound : 找到大于等于x的数字
upper_bound : 找到大于x的数字

详细内容：
在从小到大的排序数组中，
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中，重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

无旋平衡树

FHQ Treap , 使用方法：复制粘贴
来自Konjac’s Blog

struct Treap
{
    const int INF;
    int Root,cnt;
    deque<int>del_list;
    struct Node
    {
        int ch[2],v,rnd,siz;
    }node[N];
    int newNode(int x)//申请新节点
    {
        int tmp;
        if(del_list.empty()) tmp=++cnt;
        else tmp=del_list.front(),del_list.pop_front();
        node[tmp].rnd=rand(),node[tmp].v=x,node[tmp].siz=1,node[tmp].ch[0]=node[tmp].ch[1]=0;
        return tmp;
    }
    void update(int x)//更新信息
    {
        node[x].siz=node[node[x].ch[0]].siz+node[node[x].ch[1]].siz+1;
    }
    void vsplit(int pos,int v,int &x,int &y)//按权值分裂
    {
        if(!pos)
        {
            x=y=0;
            return;
        }
        if(node[pos].v<=v) x=pos,vsplit(node[pos].ch[1],v,node[pos].ch[1],y);
        else y=pos,vsplit(node[pos].ch[0],v,x,node[pos].ch[0]);
        update(pos);
    }
    void ssplit(int pos,int k,int &x,int &y)//按size分裂
    {
        if(!pos)
        {
            x=y=0;
            return;
        }
        if(k>node[node[pos].ch[0]].siz)
            x=pos,ssplit(node[pos].ch[1],k-node[node[pos].ch[0]].siz-1,node[pos].ch[1],y);
        else y=pos,ssplit(node[pos].ch[0],k,x,node[pos].ch[0]);
        update(pos);
    }
    int merge(int x,int y)//合并
    {
        if(!x||!y) return x+y;
        if(node[x].rnd<node[y].rnd)
        {
            node[x].ch[1]=merge(node[x].ch[1],y);
            update(x);
            return x;
        }
        node[y].ch[0]=merge(x,node[y].ch[0]);
        update(y);
        return y;
    }
    void insert(int v)//插入
    {
        int x,y;
        vsplit(Root,v,x,y);
        Root=merge(merge(x,newNode(v)),y);
    }
    void erase(int v)//删除
    {
        int x,y,z;
        vsplit(Root,v,x,z);
        vsplit(x,v-1,x,y);
        del_list.push_back(y);
        y=merge(node[y].ch[0],node[y].ch[1]);
        Root=merge(merge(x,y),z);
    }
    int pre(int v)//前驱
    {
        int x,y,cur;
        vsplit(Root,v-1,x,y);
        cur=x;
        while(node[cur].ch[1]) cur=node[cur].ch[1];
        merge(x,y);
        return node[cur].v;
    }
    int nxt(int v)//后继
    {
        int x,y,cur;
        vsplit(Root,v,x,y);
        cur=y;
        while(node[cur].ch[0]) cur=node[cur].ch[0];
        merge(x,y);
        return node[cur].v;
    }
    int get_rank(int v)//查排名
    {
        int x,y,ans;
        vsplit(Root,v-1,x,y);
        ans=node[x].siz;
        merge(x,y);
        return ans;
    }
    int kth(int k)//查排名为k的数
    {
        ++k;
        int x,y,cur;
        ssplit(Root,k,x,y);
        cur=x;
        while(node[cur].ch[1]) cur=node[cur].ch[1];
        merge(x,y);
        return node[cur].v;
    }
    Treap():INF(2147483647)//构造函数初始化
    {
        Root=cnt=0;
        insert(-INF),insert(INF);
    }
};

//粘贴封装好的代码之后
Treap a;//定义一棵无旋Treap
Treap b[10];//定义一个长度为10的数组，每一个位置有一棵无旋Treap

使用样例代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include<deque>
using namespace std;

typedef long long LL;

const int N = 3e5+10 ;
struct Treap
{
    const int INF;
    int Root,cnt;
    deque<int>del_list;
    struct Node
    {
        int ch[2],v,rnd,siz;
    }node[N];
    int newNode(int x)//申请新节点
    {
        int tmp;
        if(del_list.empty()) tmp=++cnt;
        else tmp=del_list.front(),del_list.pop_front();
        node[tmp].rnd=rand(),node[tmp].v=x,node[tmp].siz=1,node[tmp].ch[0]=node[tmp].ch[1]=0;
        return tmp;
    }
    void update(int x)//更新信息
    {
        node[x].siz=node[node[x].ch[0]].siz+node[node[x].ch[1]].siz+1;
    }
    void vsplit(int pos,int v,int &x,int &y)//按权值分裂
    {
        if(!pos)
        {
            x=y=0;
            return;
        }
        if(node[pos].v<=v) x=pos,vsplit(node[pos].ch[1],v,node[pos].ch[1],y);
        else y=pos,vsplit(node[pos].ch[0],v,x,node[pos].ch[0]);
        update(pos);
    }
    void ssplit(int pos,int k,int &x,int &y)//按size分裂
    {
        if(!pos)
        {
            x=y=0;
            return;
        }
        if(k>node[node[pos].ch[0]].siz)
            x=pos,ssplit(node[pos].ch[1],k-node[node[pos].ch[0]].siz-1,node[pos].ch[1],y);
        else y=pos,ssplit(node[pos].ch[0],k,x,node[pos].ch[0]);
        update(pos);
    }
    int merge(int x,int y)//合并
    {
        if(!x||!y) return x+y;
        if(node[x].rnd<node[y].rnd)
        {
            node[x].ch[1]=merge(node[x].ch[1],y);
            update(x);
            return x;
        }
        node[y].ch[0]=merge(x,node[y].ch[0]);
        update(y);
        return y;
    }
    void insert(int v)//插入
    {
        int x,y;
        vsplit(Root,v,x,y);
        Root=merge(merge(x,newNode(v)),y);
    }
    void erase(int v)//删除
    {
        int x,y,z;
        vsplit(Root,v,x,z);
        vsplit(x,v-1,x,y);
        del_list.push_back(y);
        y=merge(node[y].ch[0],node[y].ch[1]);
        Root=merge(merge(x,y),z);
    }
    int pre(int v)//前驱 (严格前驱)
    {
        int x,y,cur;
        vsplit(Root,v-1,x,y);
        cur=x;
        while(node[cur].ch[1]) cur=node[cur].ch[1];
        merge(x,y);
        return node[cur].v;
    }

    int nxt(int v)//后继 (严格后继)
    {
        int x,y,cur;
        vsplit(Root,v,x,y);
        cur=y;
        while(node[cur].ch[0]) cur=node[cur].ch[0];
        merge(x,y);
        return node[cur].v;
    }
    int get_rank(int v)//查排名
    {
        int x,y,ans;
        vsplit(Root,v-1,x,y);
        ans=node[x].siz;
        merge(x,y);
        return ans;
    }
    int kth(int k)//查排名为k的数
    {
        ++k;
        int x,y,cur;
        ssplit(Root,k,x,y);
        cur=x;
        while(node[cur].ch[1]) cur=node[cur].ch[1];
        merge(x,y);
        return node[cur].v;
    }
    Treap():INF(1e8)//构造函数初始化,不使用int最大值是防止溢出问题
    {
        Root=cnt=0;
        insert(-INF),insert(INF);
    }
};
Treap s;//定义一棵至多有100005个节点的无旋Treap
int main()
{
    int n ;
    scanf("%d", &n);
    LL res = 0 ;
    for(int i = 0 ; i < n ; i++ ) 
    {
        int x ;
        scanf("%d", &x);
        if(!i) 
        {
            res +=x ;
        }
        else if(s.nxt(s.pre(x)) != x)
        {
            // cout << s.pre(x) << " " << s.nxt(x) << endl;
            res += min(abs(s.pre(x) - x ) ,abs(s.nxt(x) - x));
        }
        s.insert(x) ;
    }
    cout << res << endl;
    return 0 ;
}

优化火车头

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")