单调栈单调队列.pptx

单调栈单调队列By苏赞文

看一个简单问题求一串数的最长不降子序列的个数。如：13627589ans：6维护一个单调不减栈~

例题：LargestRectangleinaHistogram〔POJ2559〕给定一串长度为n(n=100000)的序列hi(hi=10^9)，可以画出其直方图，问其中面积最大的矩形是多大？如n=7,序列为2145133

思想朴素的做法，复杂度最坏为O〔n^2〕对于一个数a[i]来说，如何找到向左和向右能扩展到的位置？两种实现方法，模拟下~

核心代码一：栈扫描〔单调栈〕，复杂度接近O〔n〕longlongans=0;inttop=0;list[n]=0;stack[top]=list[0];idx[top++]=0;for(inti=1;i=n;i++){if(stack[top-1]list[i]){while(top0stack[top-1]list[i]){longlongtmp=(longlong)(i-idx[top-1])*stack[top-1];if(tmpans){ans=tmp;}top--;}stack[top++]=list[i];}else{stack[top]=list[i];idx[top++]=i;}}printf(%lld\n,ans);

核心代码二：将高度从高到低排序，用并查集维护当前集合的宽度〔节点个数〕，取max(当前高度*宽度)为答案。复杂度为O(nlogn+na(n))h[n+1]=h[0]=-1;for(i=1;i=n;i++)l[i]=r[i]=i;for(i=1;i=n;i++) while(h[l[i]-1]=h[i])l[i]=l[l[i]-1];for(i=n;i=1;i--) while(h[r[i]+1]=h[i])r[i]=r[r[i]+1];

作业：POJ2559349427962082〔差不多一样的〕POJ2452〔思想难〕

例题：SecondMyProblemFirst〔hdu3706〕Giveyouthreeintegersn(1=n=107)，AandB(1=A,B=231-1)DefineSi=AimodBandTi=Min{Sk|i-A=k=Ik=1}.CalculatetheproductofTi(1=i=n)modB.

核心代码：longlongtmp=1,res=1;inthead=0,rear=-1;for(inti=1;i=n;i++){tmp*=a;tmp%=b;while(rear=headQ[rear]=tmp){rear--;}Q[++rear]=tmp;idx[rear]=i;while(idx[head]i-a){head++;}res=(res*Q[head])%b;}printf(%lld\n,res);POJ2823

Thanks~