长了集训Day12

上午

打不了一点，改不了一点

下午

100 + 0 + 0 \rightarrow 100 + 100 + 0

T1 气象台

要不是比赛叫单调队列，真的想不到那去

b数组存备选位置的最低气温，作为判断条件

s数组存备选位置可以延伸到的位置，用来计算区间长度

ll solve(){
    ll l=1,r=0,ans=1;
    rep(i,1,n){
        while(l<=r&&Max[i]<b[l]) l++;
        if(l<=r) ans=max(ans,i-s[l]+1);
        ll pos=i;
        while(l<=r&&Min[i]>b[r]) pos=s[r],r--;
        s[++r]=pos,b[r]=Min[i]; 
    }
    return ans;
}

T2 停车场

尝试了一下线段树的写法，结果不出所料，非TLE即WA，调了半天终于AC

注意v和up、down要分开初始化，否则复杂度会难以察觉地飙上O(n³logn)

class SegmenTree{
    public :
        ll up[Nx<<2][Nx],down[Nx<<2][Nx],mx[Nx<<2];
        ll s1[Nx],s2[Nx];
        inline ll update(now){
            ll l1=1,r1=0,l2=1,r2=0,j=1,v=0;
            rep(i,1,m){
                while(l1<=r1&&up[t][i]<up[t][s1[r1]]) r1--;
                while(l2<=r2&&down[t][i]<down[t][s2[r2]]) r2--;
                s1[++r1]=i,s2[++r2]=i;
                while(j<=i&&up[t][s1[l1]]+down[t][s2[l2]]<i-j+1){
                    if(++j>s1[l1]) l1++;
                    if(j>s2[l2]) l2++;
                }
                if(j<=i) v=max(v,i-j+1);
                if(v==r-l+1) break;
            }
            return v;
        }
        inline void build(now,ll opt){
            if(opt) rep(i,1,m) up[t][i]=mid-l+1,down[t][i]=r-mid;
            else mx[t]=update(_this);
            if(l==r) return ;
            build(lson,opt),build(rson,opt);
            mx[t]=max(mx[t],max(mx[ls],mx[rs]));
        }
        inline void modify(now,ll x,ll y,ll opt){
            if(r<x||l>x) return ;
            if(x<=mid) up[t][y]=min(up[t][y],mid-x);
            else down[t][y]=min(down[t][y],x-mid-1);
            if(opt) mx[t]=update(_this);
            if(l==r) return ;
            modify(lson,x,y,opt),modify(rson,x,y,opt);
            mx[t]=max(mx[t],max(mx[ls],mx[rs]));
        }
} tree;

最后 stO cqr&&wwh Orz