题解 P1816 【忠诚】

decoqwq · 2018-07-04 22:48:29 · 题解

qwq我特别喜欢暴力分块，给大家介绍一下此题的分块做法

首先是分块这种算法，时间复杂度是O(\sqrt n)级别的，不是很快也不是很慢 代码短最适合我这种懒人了

首先是如何分块

block=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    belong[i]=(i-1)/block+1;//每个数属于哪一块
    minn[belong[i]]=min(minn[belong[i]],a[i]);//每一块维护最小值
}

这一题只需要维护每一块最小值即可

而查询操作主要是这样的：

序列：1 2 3 4 5 
查询：[2,5]间最小值
可知1 2是一块，3 4是一块，5是一块
minn[1]=1,minn[2]=3,minn[3]=5//每块最小值
先查询第一个不完整的块[2,2]，暴力查询最小值为2
再查询一个整块[3,4]，最小值为minn[2]=3
最后查询不完整的快[5,5]，暴力查询最小值为5
所以[2,5]最小值为2

查询代码：

int query(int x,int y)
{
    int minx=0x3f3f3f3f;
    for(int i=x;i<=min(belong[x]*block,y);i++)//处理左边不完整块
    {
        minx=min(minx,a[i]);
    }
    if(belong[x]!=belong[y])//如果不在同一块
    {
        for(int i=(belong[y]-1)*block+1;i<=y;i++)//处理右边不完整块
        {
            minx=min(minx,a[i]);
        }
    }
    for(int i=belong[x]+1;i<belong[y];i++)//处理完整块
    {
        minx=min(minx,minn[i]);
    }
    return minx;
}

因为暴力查询的点肯定小于2 \sqrt n，查询的块个数也小于等于\sqrt n，故每次查询时间复杂度为O(\sqrt n)，总时间复杂度O(n \sqrt n) 最后上代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int block;
int n,m;
int belong[100010],a[100010],minn[400];
int query(int x,int y)
{
    int minx=0x3f3f3f3f;
    for(int i=x;i<=min(belong[x]*block,y);i++)
    {
        minx=min(minx,a[i]);
    }
    if(belong[x]!=belong[y])
    {
        for(int i=(belong[y]-1)*block+1;i<=y;i++)
        {
            minx=min(minx,a[i]);
        }
    }
    for(int i=belong[x]+1;i<belong[y];i++)
    {
        minx=min(minx,minn[i]);
    }
    return minx;
}
main()
{
    memset(minn,0x3f3f3f3f,sizeof(minn));
    cin>>n>>m;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
        //cout<<"count "<<i<<":"<<minn[belong[i]]<<" "<<a[i]<<endl;
        minn[belong[i]]=min(minn[belong[i]],a[i]);
        //cout<<"count "<<i<<":"<<minn[belong[i]]<<" "<<a[i]<<endl;
    }
    /*for(int i=1;i<=5;i++)
    {
        cout<<minn[i];
    }*/
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld ",query(x,y));
    }
}