ST表WA10

问题讨论区 普及段
1

题目： 智灵班提高衔接-倍增/ST 表 - 信友队

screenshotnoscale55692e83-2cab-40b7-b7cf-360d48661010
screenshotnoscale55692e83-2cab-40b7-b7cf-360d486610101619×1341 171 KB

我的代码：

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
#define i_will signed
#define ak main
#define IMO ()
#define int long long
I AK IOI;
int n,m,a[200005],last[2000005],len[1000005],bg[200005],st[200005][23];
void get(){
	memset(last,-1,sizeof last);
	last[a[0]]=0;
	len[0]=1;
	bg[0]=0;
	for(int i=1;i<n;i++){
		bg[i]=max(bg[i-1],last[a[i]]+1);
		len[i]=i-bg[i]+1;
		last[a[i]]=i;
	}
}
void init(){
	for(int i=0;i<n;i++)st[i][0]=len[i];
	int k=log2(n);
	for(int j=1;j<=k;j++){
		for(int i=0;i+(1<<j-1)<n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
}
int query(int l,int r){
	int k=log(r-l+1);
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
i_will ak IMO{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	get();
	init();
	while(m--){
		int l,r,L,R,mid,ans=0;
		cin>>L>>R;
		l=L,r=R;
		while(l<r){
			mid=(l+r)>>1;
			if(L<=bg[mid])r=mid;
			else l=mid+1;
		}
		if(L<=bg[r])ans=max(r-L,query(r,R));
		else ans=r-L+1;
		cout<<ans<<endl;
	}
	i_ak ioi;
}
2

@王建力 @360病毒 @2345安全卫士 @stringdp100005

3

怎么办我不会ST表呜呜呜T_T

4

@俞天行 你都提高组了不可能不会

5

题目中的a[i]可能为负数，应该要把它变为正数吧（但是我和你写的差不多，WA70分，换种思路就AC了）

6

真的不会

好吧会一点，但是不咋会用

7

@王晨欢 就是要求 abs 对吧

8

加上200001应该就行了吧（反正我是这样干的）

9

@王晨欢 按照你的做了现在 WA20

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
#define i_will signed
#define ak main
#define IMO ()
#define int long long
I AK IOI;
const int M=1e6;
int n,m,a[200005],last[2000005],len[1000005],bg[200005],st[200005][23];
void get(){
	memset(last,-1,sizeof last);
	last[a[0]+M]=0;
	len[0]=1;
	bg[0]=0;
	for(int i=1;i<n;i++){
		bg[i]=max(bg[i-1],last[a[i]+M]+1);
		len[i]=i-bg[i]+1;
		last[a[i]+M]=i;
	}
}
void init(){
	for(int i=0;i<n;i++)st[i][0]=len[i];
	int k=log2(n);
	for(int j=1;j<=k;j++){
		for(int i=0;i+(1<<j-1)<n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
}
int query(int l,int r){
	int k=log(r-l+1);
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
i_will ak IMO{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	get();
	init();
	while(m--){
		int l,r,L,R,mid,ans=0;
		cin>>L>>R;
		l=L,r=R;
		while(l<r){
			mid=(l+r)>>1;
			if(L<=bg[mid])r=mid;
			else l=mid+1;
		}
		if(L<=bg[r])ans=max(r-L,query(r,R));
		else ans=r-L+1;
		cout<<ans<<endl;
	}
	i_ak ioi;
}
10

稍等，我再看看

11

@王晨欢 还在吗？

12

在，快看出来了

13

破案了，query函数中的log改为log2。

14

log2是计算以2为底的对数,而log是计算以e为底的对数。

15

@王晨欢 感谢 AC 了，脑抽了忘记打 2 了

18

已经 AC