自动搬运

查看原文

来自洛谷，原作者为

	Notshgiook **

搬运于2025-08-24 21:30:39，当前版本为作者最后更新于2019-05-01 10:53:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

非常水的关于P1816【忠诚】的题解

前言：嘿嘿嘿嘿嘿嘿！！！！

这个题貌似非常有简单（滑稽）！可以很明显的看出这个题就是个板子题。众所周知，这是个问题，有无数种做法。such as 树状数组，线段树，ST表，暴力and so on！

本人非常的菜鸡只会ST表和线段树，对于树状数组那种高深的解法（包括lowbit那种玄学问题）鄙人并不明白！！

---

ST表解法

ST表示一种简单有效求静态RMQ（Range MIinimum/Maximum Query 离线查询区间最大最小值）问题的方法，他比较类似于动态规划（毒品！！！）

在进行ST表的操作中，我们用O( nlog(n) )的时间复杂度来进行预处理，用大概O(1) 的时间复杂度来进行查询

我们可以用一个数组 f[i][j] 来表示 “从i作为左端点，长度为 (1<<j) 长度的区间内的最大或最小值”

对于预处理而言 O（n log（n））

如果一个区间i的长度为1，那么f[i][0]就为位置i对应的值 对于一个长度为2的区间a—>b，我们可以用f[a][1]来表示这个区间的极值，那么对于这个区间而言，f[a][1]的最小值就可以看做min(a,b),即可以看做min(f[a][0],f[a+(1<<0)][0])。

如果我们把 左端点记做i，区间长度改为j呢 那么f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1];

所有我们在预处理的时候，我们不妨先枚举区间长度j，再枚举区间左端点i，只要能保证i+(1<<j)-1≤n，那么我们便可以将各种区间给预处理出来；

	for(register int i=1;i<=n;i++) scanf("%d",&f[i][0]);
	for(register int j=1;j<=20;j++)
	{
		for(register int i=1;i<=n;i++)
		{
			if(i+(1<<j)-1<=n) f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
    

关于查询操作

我们首先读入了 某个区间的左端点L，和右端点R； 我们并不能保证 区间长度 （R-L+1） 是2的n次方。所以怎么才能用我们预处理的信息呢？（如果用不上预处理他干什么）

对于一个区间的最大值的数值，一个区间肯定只要一个，如果我们用他的两个有重叠的子区间来更新这个区间肯定没有任何问题。

那么我们可以找距离区间长度（R-L+1）最近的一个2的n次方数k，那么我们就可以用 L为左端点，长度为k的区间和以R为右端点，区间长度为k的两个区间长度来更新所求的区间。不懂得可以画画图！

综上所述，对于左端点为L，右端点为R的区间，他的最小值MIN=min(f[L][log2(R-L+1)],f[R-(1<<(log2(R-L+1))+1][log(R-L+1]

int ask(int l,int r)
{
	int k=log2(r-l+1);
	return min(f[l][k],f[r-(1<<k)+1][k]);
}

下面是鄙人的弱弱的代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define maxn 100005
#define re register
int n,m,l,r,f[maxn][22];

int ask(int l,int r)
{
	int k=log2(r-l+1);
	return min(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(re int i=1;i<=n;i++) scanf("%d",&f[i][0]);
	for(re int j=1;j<=20;j++)
	{
		for(int i=1;i<=n;i++)
		{
			if(i+(1<<j)-1<=n)
			{
				f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
			}
		}
	}
	for(re int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		printf("%d ",ask(l,r));
	}
	return 0;
}

于是你就可以看见你的屏幕中间绿了一片

---

现在我们开始转入线段树

众所周知，我们刚刚结束了紧张有趣的ST表，开始用可爱的线段树！！！

这个题没修改，没有lazytag！只需要把线段树建好，然后区间查询，那么无论相比于P3372【模板】线段树1和P3373【模板】线段树2实在是没有可比性，其实和P1047校门外的树用线段树做差不多，用线段树更像是大材小用！

但是，线段树那么厉害！据某老师而言：st表，树状数组能做的事，线段树都能做（膜拜膜拜）；那么不妨开始线段树！！！

在没有区间修改的情况下，一个线段树就显得简单多了。

对于建树来看没有什么特别的地方，直接贴代码

void build(int p,int l,int r)
{
	s[p].l=l;
	s[p].r=r;
	if(l==r)
	{
		s[p].Min=data[l];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	s[p].Min=min(s[p<<1].Min,s[p<<1|1].Min);
}

对于查询来看，不说什么了，还是直接贴代码吧

inline int ask(int p,int l,int r)
{
	if(l==s[p].l&&s[p].r==r) return s[p].Min;//如果恰好完全覆盖，则直接返回 
	int mid=s[p].l+s[p].r>>1;
	if(r<=mid) return ask(p<<1,l,r);//如果查询的区间完全在这个节点所代表的区间的左端，直接去查询左边 
	if(l>mid) return ask(p<<1|1,l,r);//如果查询的区间完全在这个节点所代表的区间的右端，直接去查询右边
	return min(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));//如果正好跨过中间 
} 

然后鄙人弱弱的代码~~~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define maxn 100005
#define re register
#define INF 0x7fffffff

struct tree
{
	int l,r,Min=INF;
}s[(maxn<<2)+5];

int n,m,L,R,data[maxn];

void update(int p)
{
	s[p].Min=min(s[p<<1].Min,s[p<<1|1].Min);
}

void build(int p,int l,int r)
{
	s[p].l=l;
	s[p].r=r;
	if(l==r)
	{
		s[p].Min=data[l];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	update(p); 
}

inline int ask(int p,int l,int r)
{
	if(l==s[p].l&&s[p].r==r) return s[p].Min; 
	int mid=s[p].l+s[p].r>>1;
	if(r<=mid) return ask(p<<1,l,r);
	if(l>mid) return ask(p<<1|1,l,r);
	return min(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));
} 

int main()
{
	scanf("%d%d",&n,&m);
	for(re int i=1;i<=n;i++) scanf("%d",&data[i]);
	build(1,1,n);
	for(re int i=1;i<=m;i++)
	{
		scanf("%d%d",&L,&R);
		printf("%d ",ask(1,L,R)); 
	}
	return ~~(0-0);
}

于是您的屏幕之前会出现一片绿色

（若不是你突然闯进我生活）~~

---

本蒟蒻太弱，若有不正确的地方请各位大神及时指出