星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P1531 【I Hate It】

posted on 2017-11-02 22:16:29 | under 题解 |

联赛期间复习一下分块。

日常宣传lofter。

分块算法是一种用于暴力骗分的比较高效的算法,经常用于解决各种区间问题。当然nsqrt(n)毕竟还是没有nlogn的线段树快,但是好打不是么

其实现方式是把数组分成sqrt(n)(经均值不等式证明一般题型这样分时间效率最高)块,每块储存块内的数值。

于是遍历就只需要sqrt(n)了。

注意查询区间的边角不一定是个完整的块,这部分使用暴力解决。

此外,本题请使用cin,毕竟玄学输入。

#include<cstdio>
#include<iostream>
#include<cmath>
#define neko 200010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
int n,m,blk,a[neko],bl[neko],Max[neko];
using std::cin;
void split()
{
    f(i,1,n)
    {
        bl[i]=(i-1)/blk+1;
        Max[bl[i]]=chkmax(Max[bl[i]],a[i]);
    }
}
void update(int tag,int x)
{
    if(a[tag]<x)a[tag]=x,Max[bl[tag]]=chkmax(Max[bl[tag]],a[tag]);//仅一行的update
}
int query(int l,int r)
{
    int tmp=0;
    f(i,l,chkmin(bl[l]*blk,r))tmp=chkmax(tmp,a[i]);
    if(bl[l]!=bl[r])f(i,bl[l]+1,bl[r]-1)tmp=chkmax(tmp,Max[i]);
    f(i,chkmax((bl[r]-1)*blk+1,l),r)tmp=chkmax(tmp,a[i]);
    return tmp;
}
int main()
{
    std::ios::sync_with_stdio(false);
    char c;int x,y;
    cin>>n>>m,blk=sqrt(n);
    f(i,1,n)cin>>a[i];
    split();
    f(i,1,m)
    {
        cin>>c>>x>>y;
        if(c=='Q')printf("%d\n",query(x,y));
        else update(x,y);
    }return 0; 
}