Loading...

洛谷P1531 I hate it

check评论:0 条 remove_red_eye浏览量:421 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-08-07

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));
        }
    }
} 

chevron_left 洛谷P1168 中位数
浅析FFT与NTT chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名