P6801 [CEOI2020]花式围栏

· · 题解

又没有我的做法，感觉要好想一点，还是记录一下吧。

考虑通过每个矩形右边界的位置来计数，依次加入每个围栏时就累加右边界在此围栏内的矩形数。

然后可以发现随着上边界的递减，左边界可以取的位置递增，如图，每个红色的位置表示上边界与左边界的交点：

就是单调栈的形式，而下边界怎么取都可以，如果每次计算长为 1 的围栏部分就可以简单的计数了。

但由于有宽度，要整块的计数，直接算可能不好看。

考虑用右边界在此围栏内的所有矩形减去有部分在围栏外的矩形数来得到所求的。

所有矩形的计算只与当前围栏大小有关，可以简单算到。

有部分在围栏外的矩形随着上边界的递减，左边界可以取的位置递减，下图蓝色部分：

还是单调栈，下边界仍然随便取。

然后写个单调栈维护蓝色部分的数量和即可，具体计算可以看代码。

要注意的是：上边界对应的下边界之和是个公差为 1 的等差数列，计算所有矩形时右边界对应的左边界也是这样。

核心代码：

for(i=1;i<=n;i++)
{
    for(;top&&ht[stk[top]]>=ht[i];top--)
    {//单调栈
        s1=Md((LL)(ht[stk[top-1]]+1+ht[stk[top]])*(ht[stk[top]]-ht[stk[top-1]])>>1);
        Add(sm,Mod-Ml(s1,wt[stk[top-1]]));
    }wt[stk[++top]=i]=Ad(wt[i-1],w=read());//宽度前缀和
    s1=Md((LL)(ht[stk[top-1]]+1+ht[stk[top]])*(ht[stk[top]]-ht[stk[top-1]])>>1);//等差数列
    Add(sm,Ml(s1,wt[stk[top-1]]));//围栏外的矩形数
    s1=Md((LL)(ht[i]+1)*ht[i]>>1);s2=Ml(Ml(wt[i-1]+1+wt[i],w),Inv2);//所有矩形：等差数列
    Add(ans,Ad(Ml(s1,s2),Mod-Ml(sm,w)));//整块计数
}writenum(ans,10);