二叉堆（基础）

知识：

1.堆分为大根堆和小根堆，是一种相对有序的树形结构。

大根堆性质：堆中所有元素的值都小于等于堆顶元素，即堆顶是最大元素，所以我们可以用大根堆去维护前m大的值

小根堆反之。

形成堆分为几个操作：插入，删除，上浮、下沉

插入时，我们将将所操作元素插入在堆底最后一位，然后进行上浮。

上浮：判断该元素是否满足大/小根堆的性质，即比较它和父节点的大小，小根堆：小于父节点时交换，反之。

删除：将堆顶元素与堆底元素最后一位交换，然后进行下沉。

下沉：先比对子节点元素大小，将该元素与较小的子节点交换，直到该元素小于等于最小的（小根堆），大根堆反之。

例题：

1黑匣子 - 洛谷

就是使用对顶堆，可以动态维护第i个最值

#include 
#include 
#include 
#include 
using namespace std;
 
const int N = 2e5 + 10;
int n, m;
int a[N];
priority_queue<int, vector<int>, greater<int>> small;
priority_queue<int> big;
int main()
{
    cin >> n >> m;
 
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
 
    // 对顶堆的维护操作 (我们是用小顶堆存小数， 大顶堆存大数), 让对顶堆保持能找到第i小的数
    int p = 1;
    for (int i = 1; i <= m; i ++ )
    {
        int x;
        cin >> x;
 
        for (int j = p; j <= x; j ++ )
        {
            big.push(a[j]);
            if(big.size() == i)
                small.push(big.top()), big.pop();
        }
        p = x + 1;
        cout << small.top() << endl;
        big.push(small.top());
        small.pop();
    }
    return 0;
}

2[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷

这道题就是每次找前两个小的合并，然后再插入堆中，贪心的思想

#include 
#include 
using namespace std;
 
const int N = 1e5 + 10;
int n, a[N];
priority_queue<int, vector<int>, greater<int>> s; 
 
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> x;
        s.push(x);
    }
    
    int ans = 0;
    while(s.size() >= 2)
    {
        //这道题就是动态将堆中最小的两个值合并
        int a = s.top();
        s.pop();
        int b = s.top();
        s.pop();
        s.push(a + b);
        ans += a + b;
    }
    
    cout << ans << endl;
    return 0;
}

3中位数 - 洛谷

也是使用对顶堆，经典例题，找到每次对半的中间数

#include 
#include 
using namespace std;
 
priority_queue<int> big;
priority_queue<int, vector<int>, greater<int>> small;
int n;
int mid;
 
int main()
{
    cin >> n >> mid;
 
    cout << mid << endl;
    
    for(int i = 2; i <= n; i ++ )
    {
        int x;
        cin >> x;
        
        if(x > mid)
            small.push(x);
        else
            big.push(x);
            
        if(i % 2)
        {
            while(small.size() != big.size())
            {
                if(small.size() < big.size())
                {
                    small.push(mid);
                    mid = big.top();
                    big.pop();
                }
                else
                {
                    big.push(mid);
                    mid = small.top();
                    small.pop();
                }
            }
            cout << mid << endl;
        }
    }
    
    return 0;
}

4最小函数值 - 洛谷

这道题比较水，因为函数式递增的就是开一个大根堆（对内元素<=堆顶元素），然后将第一组系数下的函数值作为对照，小于堆顶元素的就放到堆中，实现动态维护前m个小的数

#include 
#include 
using namespace std;
 
const int N = 10010;
int n, m;
int a[N], b[N], c[N];
int ans[N];
priority_queue<int> big; // 求前m小的数
 
int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i] >> b[i] >> c[i];
        for(int j = 1; j <= m; j ++ )
        {
            int k = a[i] * j * j + b[i] * j + c[i];
            
            if(i == 1) // 先把函数1的值当作对照组
            {
                big.push(k);
            }
            else 
            {
                if(k < big.top()) // 如果其他函数有小于的，就替换下来
                {
                    big.push(k);
                    big.pop();
                }
                else // 这里可以直接break掉，因为这个函数是递增的
                 break;
            }
        }
    }
    
    for(int i = 1; i <= m; i ++ )
    {
        ans[i] = big.top();
        big.pop();
    }
    
    for(int i = m; i >= 1; i -- )
    {
        cout << ans[i] << ' ';
    }
    
    return 0;
}

5【模板】ST 表 - 洛谷

st表的作用是求区间最值（RMQ(A,i,j))。

使用倍增实现的，类似区间dp，f[i][j]存放[i, i + 2^j]之中的最值。

预处理操作：

先将f[i][0]填入，然后遍历区间（注意边界值），

状态转移方程：f[i][j] = max(f[i][j - 1] + f[i - (1 << j - 1)][j - 1]),即[i, i + 2^j - 1 - 1]+[i + 2^j - 1, i + 2^j]

查询操作：

类似于预处理操作，len = log2[r - l  + 1],f[l][r] = max(f[l][len], f[r - (1 << len) + 1][len],

即[l, l + 2^len - 1][r - 2^len + 1, r]

#include 
using namespace std;
 
const int N = 1e5 + 10;
int n, m;
int lg[N];
int f[N][21];
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
 
int main()
{
    cin >> n >> m;
    
    //预处理
    lg[0] = -1;
    for(int i = 1; i <= n; i ++ ) 
    {
        f[i][0] = read();
        lg[i] = lg[i >> 1] + 1;
    }
    for(int j = 1; j <= lg[n]; j ++ )
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i ++ )
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
    
    //查询操作
    for(int i = 1; i <= m; i ++ )
    {
        int l, r, ans;
        l = read();
        r = read();
        
        int len = lg[r - l + 1];
        ans = max(f[l][len], f[r - (1 << len) + 1][len]);
        printf("%d\n",ans);
    }
    
    return 0;
}

6质量检测 - 洛谷

st表板子题

#include 
using namespace std;
 
const int N = 1000010;
int n, m;
int f[N][100];
int lg[N];
 
int main()
{
    cin >> n >> m;
    
    //预处理
    lg[0] = -1;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> f[i][0];
        lg[i] = lg[i >> 1] + 1;
    }
    for(int j = 1; j <= lg[n]; j ++ )
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i ++ )
        {
            f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
    
    int len = lg[m];
    for(int i = 1; i <= n - m + 1; i ++ )
    {
        int l = i, r = i + m - 1;
        
        int ans = min(f[l][len], f[r - (1 << len) + 1][len]);
        
        cout << ans << endl;
    }
    
    return 0;
}