[Code+#3] 寻找车位

_H17_ · 2026-11-13 14:10:29 · 题解

我今天才发现单调栈和单调队列的区别是“栈底”或“队首”是否可以弹出东西。

题目分析

注意到 m\le 2\times 10^3，而且 q 的范围也比较小不难想到这部分可能处理的相对暴力。

先考虑静态求一次这个怎么做：由于四个方向都可以扩展很不好做，不如枚举一个底边，我们考虑第 i 个位置向上扩展最多能扩展到 a_i。接下来我们做扫描线，双指针维护一个 j 表示此时可行的最小右边界。扩展的时候考虑单调队列维护这个 a 数组即可，假设队首是 k，然后判断 a_k\ge i-j+1 是否合法。当 j>k 的时候，把 k 弹出去；加入的话是类似单调栈的，每次把比当前值大的全部弹出去（因为不能在做贡献了）。

接下来考虑对 n 这个维度进行一些优化，区间问题先尝试线段树每个节点维护 m 个数，表示当前区间以 i 为底边的答案（设这个值是 val_i）。如果可以合并两个节点，那么建树、修改、询问就都解决了。

考虑这个 val_i 需要首先从两个子节点取较大值，然后考虑跨过中间的情况。跨过中间的话考虑多给两边维护 pre_i,suf_i 表示第 i 行（m 这个维度的），前缀后缀 1 的数量，这个合并时容易的。考虑现在类似于刚才那个静态求一次的暴力，枚举底边 i 之后对两边单调队列并且求出 j，然后把 val_i 和这个 i-j+1 比较。这样就可以 O(m) 合并节点了，不过不用担心，一开始我们已经发现 m 不大了。

最终时间复杂度 O(nm+qm\log n)，感觉有点卡空间。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=4e6+1;
int n,m,q,rt,tot,pool[N*12],*globalpos=pool;
vector<int>a[N];
struct SgtNode{
    int l,r,ls,rs,*pre,*suf,*val;
}f[N<<1];
int*getint(){
    int*ret=globalpos;
    globalpos+=m+1;
    return ret;
}
void init(int x,int l,int r){
    f[x].l=l,f[x].r=r;
    f[x].ls=f[x].rs=0;
    f[x].pre=getint(),f[x].suf=getint(),f[x].val=getint();
    return;
}
void copynode(int x,int y){
    f[x].l=f[y].l,f[x].r=f[y].r;
    copy(f[y].pre+1,f[y].pre+m+1,f[x].pre+1),
    copy(f[y].suf+1,f[y].suf+m+1,f[x].suf+1),
    copy(f[y].val+1,f[y].val+m+1,f[x].val+1);
    return;
}
void merge(int x,int a,int b){
    static deque<int>q1,q2;
    f[x].l=f[a].l,f[x].r=f[b].r;
    for(int i=1;i<=m;i++){
        f[x].pre[i]=f[a].pre[i],f[x].suf[i]=f[b].suf[i];
        if(f[x].pre[i]==f[a].r-f[a].l+1)
            f[x].pre[i]+=f[b].pre[i];
        if(f[x].suf[i]==f[b].r-f[b].l+1)
            f[x].suf[i]+=f[a].suf[i];
    }
    q1.clear(),q2.clear();
    for(int i=1,j=1;i<=m;i++){
        while(!q1.empty()&&f[a].suf[i]<=f[a].suf[q1.back()])
            q1.pop_back();
        while(!q2.empty()&&f[b].pre[i]<=f[b].pre[q2.back()])
            q2.pop_back();
        q1.push_back(i),q2.push_back(i);
        while(j<=i&&f[a].suf[q1.front()]+f[b].pre[q2.front()]<i-j+1){
            j++;
            if(q1.front()<j)
                q1.pop_front();
            if(q2.front()<j)
                q2.pop_front();
        }
        f[x].val[i]=max({f[a].val[i],f[b].val[i],i-j+1});
    }
    return;
}
void pushup(int cur){
    return merge(cur,f[cur].ls,f[cur].rs);
}
void build(int l,int r,int&cur){
    init(cur=(++tot),l,r);
    if(l==r){
        for(int i=1;i<=m;i++)
            f[cur].pre[i]=f[cur].suf[i]=f[cur].val[i]=a[l][i];
        return;
    }
    int mid=midpoint(l,r);
    build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);
    return pushup(cur);
}
void modify(int x,int y,int cur){
    if(f[cur].l==f[cur].r){
        f[cur].pre[y]=f[cur].suf[y]=f[cur].val[y]=(a[x][y]^=1);
        return;
    }
    int mid=midpoint(f[cur].l,f[cur].r);
    if(x<=mid)
        modify(x,y,f[cur].ls);
    else
        modify(x,y,f[cur].rs);
    return pushup(cur);
}
void query(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        if(l==f[cur].l)
            copynode(0,cur);
        else
            copynode(tot+1,0),merge(0,tot+1,cur);
        return;
    }
    int mid=midpoint(f[cur].l,f[cur].r);
    if(l<=mid)
        query(l,r,f[cur].ls);
    if(mid<r)
        query(l,r,f[cur].rs);
    return;
}
string program(){
    cin.tie(nullptr)->ios::sync_with_stdio(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        a[i].resize(m+1);
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    }
    build(1,n,rt);
    init(0,0,0),init(tot+1,0,0);
    for(int o,l,r,s,t,x,y,ans;q;q--){
        cin>>o;
        if(!o){
            cin>>x>>y;
            modify(x,y,rt);
        }
        else{
            cin>>l>>s>>r>>t;
            query(l,r,rt);
            ans=0;
            for(int i=s;i<=t;i++)
                ans=max(ans,min(f[0].val[i],i-s+1));
            println("{}",ans);
        }
    }
    return"H17";
}
string H17=program();
signed main(){
    return 0;
}