题解 P1816 【忠诚】

离子键Ionic_Bond · 2019-05-18 17:09:32 · 题解

不就是个ST表板子啊

ST表详解：

引入：

- ST表用于解决R.M.Q问题（区间最值问题）

1.预处理原理

• 首先是这张图

• 倍增的目的是快速预处理每个区间的最大值而不遗漏，查询时只需取出该区间最大值即可;

• 每次处理，都用maxn[i][j]数组存下[i...i+2^j-1]区间的最大值，总的时间复杂度为O(nlogn)

这一部分的代码有点暴力意味，相当于打了个表

const int MAXN=21;//maxn的值根据实际情况而定
for(int j=1;j<=MAXN;j++）//注意j在外层循环
    for(int i=1;i+(1<<j)-1<=n;i++)
        maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1];

2.查询原理

• 又是一张图

• 设k=log_2R

• 查询L~R这一区间的最大值，就是求max(maxn[L][k],maxn[R-2^k+1][k])

• 为啥呢？

• 很明显有时候对R取底会得到一个小数甚至是无理数如：

  log_25≈2.32192809

• 这时，就会出现向下取整，引用不全的情况

• 所以我们从头到尾再从尾到头地查两遍，把区间全部覆盖就会避免这样的问题 这一部分代码极简如下，思路清晰优美显然

  int lookit(int le,int ri)
  {
  int lg;
  lg=log2(ri-le+1);
  return min(minn[le][lg],minn[ri-(1<<lg)+1][lg]);
  }

  看AC代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int lef,rig;
int n,m;
int minn[2333333][30];
int ans[100001];
/*查询*/
int lookit(int le,int ri)
{
    int lg;
    lg=log2(ri-le+1);
    return min(minn[le][lg],minn[ri-(1<<lg)+1][lg]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&minn[i][0]);
    }
    /*预处理*/
    for(int j=1;j<=21;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&lef,&rig);
        ans[i]=lookit(lef,rig);
    }
    for(int i=1;i<=m;i++)printf("%d",ans[i]);
    return ~~(0-0)
}

话说洛谷MARKDOWN变了好多啊，代码高亮用法求解

• 我太弱了连markdown都不会用了

最后请管理员帮我过一下这个题解，虽然有用ST表做的，但不如我这个讲得详细嘛