题解 P1531 【I Hate It】

teafrogsf

2017-11-02 22:16:29

Solution

联赛期间复习一下分块。 [日常宣传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; } ```