skkyk:题解 洛谷P3865 【【模板】ST表】
2024-08-29 00:59:18
我不会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));
}
}
就这么多,学学半,如果有不理解的地方可以私信
最新文章
- salesforce 零基础学习(二十一)workflow Q&;A
- vs.net 2005 C# WinForm GroupBOX 的BUG?尝试读取或写入受保护的内存。这通常指示其他内存已损坏
- tomcat和mysql安装配置总结
- iOS 基础 第三天(0807)
- 29、activity横竖屏切换细节问题
- logstash multiline
- GB2312引进和使用的字体
- 动手学习TCP:数据传输(转)
- 聊聊RocksDB Compact
- 采用SmartQQ 协议可制作聊天机器人
- textarea高度自适应,随着内容增加高度增加
- JAVA 数组作为方法参数—传递地址
- redis-list操作
- Quartz基础知识了解(一)
- c++为什么要面向对象?
- Spark记录-SparkSQL一些操作
- CCF CSP认证考试试题
- Python:SQLMap的工作流程
- LeetCode--203--删除链表中的节点
- ASP.NET在请求中检测到包含潜在危险的数据,因为它可能包括 HTML标记或脚本