luoguP3865人类智慧做法TLE49分求条

虽然窝知道这题要用ST表,但我还是的用线段树…那咋了

#include<bits/stdc++.h>
using namespace std;
int tree[400005],n,a[100001],x,y,m;
void jianshu(int id,int l,int r){
	if(l==r){
		tree[id]=a[l];
		return ;
	}
	int mid=(l+r)/2;
	jianshu(id*2,l,mid);
	jianshu(id*2+1,mid+1,r);
	tree[id]=max(tree[id*2],tree[id*2+1]);
}
int find(int id,int l,int r){
	if(x<=l&&y>=r) return tree[id];
	int mid=(l+r)/2,ma=-1e9;
	if(x<=mid) ma=max(ma,find(id*2,l,mid));
	if(y>mid) ma=max(ma,find(id*2+1,mid+1,r));
	return ma;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	jianshu(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		cout<<find(1,1,n)<<endl;
	}
}

题面
ST表是TLE56。

#include<bits/stdc++.h>
using namespace std;
int n,l,r,a[100005],m,st[100005][105];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i][0]=a[i];
    }
    for(int j=1;j<=log2(n);j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        int s=log2(r-l+1);
        cout<<max(st[l][s],st[r-(1<<s)+1][s])<<endl;
    }
}

666
反人类啊!!
你用线段树??
(⊙﹏⊙)

@卡皮巴拉 你要调哪个??
ST表,还是线段树?

都要

endl换成’\n’,还有: 请注意最大数据时限只有 0.8s,数据强度不低,请务必保证你的每次查询复杂度为 O(1)。若使用更高时间复杂度算法不保证能通过。

算了,只要线段树

行,我来康康

我懂了,who有快读和快写模板

image

(帖子已被作者删除)

题面有快读快写模板

thank,窝一改就A

那让论管管贴吧

@LeuR 关帖