[ZJOI2009]对称的正方形 manacher+单调队列

快看，这里有个蒟蒻不会写单调队列！

弱者就是弱。啥思路没有，码力还不行。

显然的思路是考虑每一个中心点，求最大边长。发现每个点的限制挺难维护的。其实可以把限制拆开，拆成上下左右四个方向，最后求个min。

以向上的方向为例。我们想求向上能扩展的最大边长。从上往下扫，维护半径单调递增的单调队列，每次从队头弹掉半径过小的点，记录最后一个弹掉的队头。然后边长就很好求了。

然后我就写不出来了

#include
using namespace std;
typedef pair pii;
#define forg(i,x) for(int i=fir[x];i;i=nxt[i])
#define uu unsigned
#define scanf a1234=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define rint register int
int a1234;
char buf[1<<18],*bufs=buf,*buft=buf;
inline int gc(){
    return bufs==buft&&(buft=(bufs=buf)+fread(buf,1,1<<18,stdin)),bufs==buft?-1:*bufs++;
}
inline void xxx(){for(;;);}
inline int rd(int l,int r){return rand()%(r-l+1)+l;}

const int mxn=2005;
int a[mxn][mxn],ra[mxn],r1[mxn][mxn],r2[mxn][mxn];
int n,m;
inline void man1(rint x){
//横向
    rint md=-1,rp=-1;
    for(rint i=1;i<=m;++i){
        if(irp)rp=i+ra[i],md=i;
    }
}
inline void man2(rint y){
//纵向
    rint md=-1,rp=-1;
    for(rint i=1;i<=n;++i){
        if(irp)rp=i+ra[i],md=i;
    }
}
int lm[mxn][mxn];
int q[mxn];
inline void work1(){
    rint qh,qt,lim;
    for(rint j=2;j>1;
    for(int i=1;i<=n;i+=2)for(int j=1;j<=m;j+=2)ans+=lm[i][j]>>1;
    printf("%d\n",ans);
    return 0;
}

说几个比较重要的细节吧。

还是以向上的方向为例(work1)，如果中心行是\(i\)行，上界是第\(x\)行 （上界一定是关键行，但是第i行可以是辅助行），边长就是\(i-x+1\) 分类讨论一下挺好推的

还有每次更新lim的时候其实应该特判关键行，但是不判也没事。