欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

skkyk:题解 洛谷P3865 【【模板】ST表】

程序员文章站 2022-04-08 12:55:00
~~我不会ST表~~ 智推推到这个题 发现标签中居然有线段树。。? 于是贸然来了一发线段树 众所周知,线段树的查询是log(n)的 题目中" 请注意最大数据时限只有0.8s,数据强度不低,请务必保证你的每次查询复杂度为 O(1) " 然后草草打完代码竟然AC了。。exm?? 最慢也不过400ms ~ ......

我不会st表

智推推到这个题
发现标签中居然有线段树。。?
于是贸然来了一发线段树
众所周知,线段树的查询是log(n)的
题目中"请注意最大数据时限只有0.8s,数据强度不低,请务必保证你的每次查询复杂度为 o(1)"
然后草草打完代码竟然ac了。。exm??
最慢也不过400ms

数据好水

好吧,不多说上代码
首先是数据存贮,分别是左子节点,右子节点,maxx存贮当前节点的最大值

struct node{
    int left,right,maxx;
}tree[100000*4+10];

建树,和常规一样

void build(int index,int l,int r)
{
    tree[index].left=l,tree[index].right=r;
    if(l==r)
    {
        int x=read();
        tree[index].maxx=x;
        return ;
    }
    int mid=(l+r)>>1;
    build(index<<1,l,mid),build(index<<1|1,mid+1,r);
    tree[index].maxx=max(tree[index<<1].maxx,tree[index<<1|1].maxx);
}

区间查询,记录每个和目标区间有交集的区间的最大值

int intervalask(int index,int l,int r)
{
    if(tree[index].left>=l&&tree[index].right<=r)   
        return tree[index].maxx;
    int tempmax=-0x7fffffff;
    if(tree[index<<1].right>=l)
        tempmax=max(intervalask(index<<1,l,r),tempmax);
    if(tree[index<<1|1].left<=r)
        tempmax=max(intervalask(index<<1|1,l,r),tempmax);
    return tempmax;
}

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
struct node{
    int left,right,maxx;
}tree[100000*4+10];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-f;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

void build(int index,int l,int r)
{
    tree[index].left=l,tree[index].right=r;
    if(l==r)
    {
        int x=read();
        tree[index].maxx=x;
        return ;
    }
    int mid=(l+r)>>1;
    build(index<<1,l,mid),build(index<<1|1,mid+1,r);
    tree[index].maxx=max(tree[index<<1].maxx,tree[index<<1|1].maxx);
}

int intervalask(int index,int l,int r)
{
    if(tree[index].left>=l&&tree[index].right<=r)   
        return tree[index].maxx;
    int tempmax=-0x7fffffff;
    if(tree[index<<1].right>=l)
        tempmax=max(intervalask(index<<1,l,r),tempmax);
    if(tree[index<<1|1].left<=r)
        tempmax=max(intervalask(index<<1|1,l,r),tempmax);
    return tempmax;
}

int main()
{
    n=read(),m=read();
    build(1,1,n);
    for(register int i=1,l,r;i<=m;i++)
    {
        l=read(),r=read();
        printf("%d\n",intervalask(1,l,r));
    }
}

就这么多,学学半,如果有不理解的地方可以私信