题解 P1531 【I Hate It】

decoqwq · 2018-07-05 10:14:38 · 题解

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

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

首先是如何分块

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

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

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

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

查询代码：

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

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

然后是修改操作，我们每一次如果进行了修改（当前数字小于被修改成的数字），判断修改后的数是否大于之前它所在块最大值，不大于就退出，大于就修改最大值即可

修改代码：

void update(int x,int y)
{
    if(a[x]<y)//需要修改
    {
        a[x]=y;
    }
    else//不需要
    {
        return ;
    }
    if(y>maxn[belong[x]])//需要更新最大值
    {
        maxn[belong[x]]=y;
    }
    return ;
}

最后上代码：

#include <bits/stdc++.h>
using namespace std;
int block,n,m;
int a[200010],belong[200010],maxn[500];
void update(int x,int y)
{
    if(a[x]<y)
    {
        a[x]=y;
    }
    else
    {
        return ;
    }
    if(y>maxn[belong[x]])
    {
        maxn[belong[x]]=y;
    }
    return ;
}
int query(int x,int y)
{
    int ans=-0x3f3f3f3f;
    for(int i=x;i<=min(belong[x]*block,y);i++)
    {
        ans=max(ans,a[i]);
    }
    if(belong[x]!=belong[y])
    {
        for(int i=(belong[y]-1)*block+1;i<=y;i++)
        {
            ans=max(ans,a[i]);
        }
    }
    for(int i=belong[x]+1;i<belong[y];i++)
    {
        ans=max(ans,maxn[i]);
    }
    return ans;
}
int main()
{
    memset(maxn,-0x3f3f3f3f,sizeof(maxn));
    cin>>n>>m;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
        maxn[belong[i]]=max(maxn[belong[i]],a[i]);
    }
    char opt[3];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='U')
        {
            update(x,y);
        }
        else
        {
            printf("%d\n",query(x,y));
        }
    }
}