题解 P1531 【I Hate It】
teafrogsf
2017-11-02 22:16:29
联赛期间复习一下分块。
[日常宣传lofter。](http://teafrog26.lofter.com/)
**分块算法是一种~~用于暴力骗分的~~比较高效的算法,经常用于解决各种区间问题。**~~当然nsqrt(n)毕竟还是没有nlogn的线段树快,但是好打不是么~~
其实现方式是把数组分成sqrt(n)(经均值不等式证明一般题型这样分时间效率最高)块,每块储存块内的数值。
于是遍历就只需要sqrt(n)了。
注意查询区间的边角不一定是个完整的块,这部分使用暴力解决。
此外,本题请使用cin,毕竟玄学输入。
```cpp
#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;
}
```