个百zz分点个 发表于 2023-4-21 23:33

C++ ST表

RMQ 问题
      RMQ（Range Minimum/Maximum Query）问题是指：对于长度为 n 的数列 A，回答若干询问 RMQ(区间 [ l，r ] ) ，返回数列A中下标在 l , r 里的最小/大值，也就是说，RMQ 问题是指求区间最值的问题。

ST 表
      st 表和线段树常被用来解决 RMQ 问题，两个各有优缺点：st 表运行效率高，但不能修改；线段树运行效率相对较慢，但支持修改操作。

      st 表的合并复杂度为 O(1)，构建复杂度为 O(n log n)，查询复杂度是 O(1)。

      st 表的核心要领在于倍增和 DP ，设区间左端点为 l ，长度为，求其区间最值。st 表的做法就是 DP 预处理出所有的区间最值，询问时直接输出。



其中 merge 为最值函数，最大值用 max ，最小值用 min 。      易看出，只有当区间中重叠的部分对最终答案无影响时，才能使用 st 表。      一点小优化，可以预处理一个 log[] 数组，以减小 cmath 库中 https://latex.codecogs.com/gif.latex?log_%7B2%7D 函数的运算时间。

个百zz分点个 发表于 2023-4-21 23:34

log 函数预处理
      没什么可讲的，只是注意初始时，log = -1 。因为 log 和 某个函数重了，所以用 Log 来表示。

for(register int i=1;i<=n;i++)
    Log=Log+1;

个百zz分点个 发表于 2023-4-21 23:34

例题讲解
P3865 【模板】ST 表https://www.luogu.com.cn/problem/P3865

https://www.luogu.com.cn/problem/P3865

个百zz分点个 发表于 2023-4-21 23:35

st 表的板子题目，也可以用线段树，不过需要卡常。

st 表做法：

      套用 st 表的板子，轻松 AC ，时间复杂度为 O(n log n + m) 。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
inline int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {num=(num<<1)+(num<<3)+ch-'0';ch=getchar();}
    return num*w;
}
int n,m,l,r,k;
int a;
int f;
int Log;
inline void st()
{
        Log=-1;
        for(register int i=1;i<=n;i++) Log=Log+1;
        for(register int i=1;i<=n;i++) f=a;
        for(register int j=1;j<=Log;j++)
                for(register int i=1;i+(1<<j)-1<=n;i++)
                        f=max(f,f);
        return;
}
int main()
{
        //freopen(".in","r",stdin);
        //freopen(".out","w",stdout);
        n=read(),m=read();
        for(register int i=1;i<=n;i++) a=read();
        st();
        while(m--)
        {
                l=read(),r=read();
                k=Log;
                printf("%d\n",max(f,f));}
        //fclose(stdin);
        //fclose(stdout);               
        return 0;
}

个百zz分点个 发表于 2023-4-21 23:35

线段树做法：

      需要使用卡常**！！！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
using namespace std;
inline int read()
{
        int num=0,w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
        while(ch>='0'&&ch<='9') {num=(num<<1)+(num<<3)+ch-'0';ch=getchar();}
        return num*w;
}
struct node
{
        int l;
        int r;
        int maxx;
}tree;
int n,m,x,y;
int a;
inline void add(int k)
{
        tree.maxx=max(tree.maxx,tree.maxx);
}
inline void build(int k,int l,int r)
{
        tree.l=l,tree.r=r;
        if(l==r) {tree.maxx=a;return;}
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        add(k);
        return;
}
inline int find(int k,int l,int r,int x,int y)
{
        if(x<=l&&r<=y) return tree.maxx;
        int mid=(l+r)>>1;
        int res=-0x3f3f3f;
        if(x<=mid) res=max(res,find(k<<1,l,mid,x,y));
        if(y>mid) res=max(res,find(k<<1|1,mid+1,r,x,y));
        return res;
}
int main()
{
        n=read(),m=read();
        for(register int i=1;i<=n;i++) a=read();
        build(1,1,n);
        while(m--)
        {
                x=read(),y=read();
                printf("%d\n",find(1,1,n,x,y));
        }
        return 0;
}

Clyde011 发表于 2024-6-6 07:08


电源电压处于1.6V到5.5V之间

公羊子丹 发表于 2024-6-6 08:01


电压范围称为工作电源电压

公羊子丹 发表于 2024-6-6 08:01


电压范围称为工作电源电压

万图 发表于 2024-6-6 09:04


内部电路工作电圧是通过内部电压调节器调节电源电压得到的

Uriah 发表于 2024-6-6 10:07


单片机的外部都连接有象电池等电源部分

帛灿灿 发表于 2024-6-6 12:03


通常选择0.01μF～0.1μF的陶瓷电容作为旁路电容。

Bblythe 发表于 2024-6-6 13:06


主时钟振荡器主要用作CPU的工作时钟

周半梅 发表于 2024-6-6 15:02


防止因瞬间大电流引起的电源电压下降

Pulitzer 发表于 2024-6-6 16:05


要在外部连接一个振荡电路提供时钟信号

童雨竹 发表于 2024-6-6 18:01


与15号引脚连接的C1称为旁路电容

Wordsworth 发表于 2024-6-6 19:04


时序电路是按时钟信号（CK）的上升沿（信号从L→H的变化）或下降沿（信号从H→L的变化）同步工作的
页: [1]
查看完整版本: C++ ST表