[luogu4259]寻找车位

考虑一个分治的做法：按行分治，将所有区间分为两类——经过分割线的、在左/右区间内部，后者显然可以递归下取，考虑前者

先求出出该行上每一列向上和向下的最大长度，记作$up_{i}$和$down_{i}$，然后枚举左端点$l$，找到最小的右端点$r$满足$r-l+1\le min_{i=l}^{r}up_{i}+\min_{i=l}^{r}down_{i}$（否则减小$r$一定不劣）

此时$r$具有单调性，再用一个单调队列维护即可，但时间复杂度为$o(qnm\log_{2}n)$，甚至劣于$o(qnm)$的暴力，因此需要优化

事实上，分治的很多过程都是重复的，即用线段树来维护区间，对于一个完全包含的区间，我们不需要搜下去，可以直接从该点得到答案

具体的，对于每一个区间：1.预处理出$up_{i}$和$down_{i}$；2.预处理出每一个$l$对应的$r$；3.维护第2项的子树最大值，合并的维护$o(m)$暴力即可，总复杂度为$o(nm+qm\log_{2}n)$

细节：关于$up_{i}$和$down_{i}$的处理另一种方法是求出每一个区间前后缀最长的1，根据子区间答案即可得到（而不保存$up_{i}$和$down_{i}$）

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 4000005

  4 #define L (k<<1)

  5 #define R (L+1)

  6 #define mid (l+r>>1)

  7 #define y1 y11

  8 struct ji{

  9     int l,r;

 10 };

 11 deque<int>q1,q2;

 12 vector<ji>zero,v[N<<2];

 13 vector<int>vv,f[N<<2],mx[N<<2];

 14 int n,m,q,p,x,y,x1,y1,x2,y2,ans;

 15 vector<ji> merge(vector<ji>x,vector<ji>y,int l1,int l2){

 16     vector<ji>v;

 17     for(int i=0;i<m;i++){

 18         v.push_back(ji{0,0});

 19         if (x[i].l<l1)v[i].l=x[i].l;

 20         else v[i].l=l1+y[i].l;

 21         if (y[i].r<l2)v[i].r=y[i].r;

 22         else v[i].r=l2+x[i].r;

 23     }

 24     q1.clear(),q2.clear(),vv.clear();

 25     for(int i=0,j=-1;i<m;i++){

 26         while ((j<m)&&((j<i)||(j-i+1<=x[q1.front()].r+y[q2.front()].l))){

 27             if (++j==m)break;

 28             while ((!q1.empty())&&(x[q1.back()].r>=x[j].r))q1.pop_back();

 29             q1.push_back(j);

 30             while ((!q2.empty())&&(y[q2.back()].l>=y[j].l))q2.pop_back();

 31             q2.push_back(j);

 32         }

 33         vv.push_back(j-1);

 34         while ((!q1.empty())&&(q1.front()<=i))q1.pop_front();

 35         while ((!q2.empty())&&(q2.front()<=i))q2.pop_front();

 36     }

 37     return v;

 38 }

 39 void up(int k,int l,int r){

 40     v[k]=merge(v[L],v[R],mid-l+1,r-mid);

 41     f[k]=vv;

 42     for(int i=0;i<m;i++)mx[k][i]=max(max(mx[L][i],mx[R][i]),f[k][i]);

 43 }

 44 void build(int k,int l,int r){

 45     for(int i=0;i<m;i++){

 46         f[k].push_back(0);

 47         mx[k].push_back(0);

 48     }

 49     if (l==r){

 50         for(int i=1;i<=m;i++){

 51             scanf("%d",&p);

 52             v[k].push_back(ji{p,p});

 53             f[k][i]=mx[k][i]=i-1-(p^1);

 54         }

 55         return;

 56     }

 57     build(L,l,mid);

 58     build(R,mid+1,r);

 59     up(k,l,r);

 60 }

 61 void update(int k,int l,int r,int x,int y){

 62     if (l==r){

 63         v[k][y].l^=1;

 64         v[k][y].r^=1;

 65         f[k][y]=mx[k][y]=y-(v[k][l].l^1);

 66         return;

 67     }

 68     if (x<=mid)update(L,l,mid,x,y);

 69     else update(R,mid+1,r,x,y);

 70     up(k,l,r);

 71 }

 72 vector<ji> query(int k,int l,int r,int x,int y,int xx,int yy){

 73     if ((l>y)||(x>r))return zero;

 74     if ((x<=l)&&(r<=y)){

 75         for(int i=xx;i<=yy;i++)ans=max(ans,min(mx[k][i],yy)-i+1);

 76         return v[k];

 77     }

 78     int ll=min(mid,y)-max(l,x),lr=min(r,y)-max(mid+1,x);

 79     vector<ji>vl,vr;

 80     vl=query(L,l,mid,x,y,xx,yy);

 81     vr=query(R,mid+1,r,x,y,xx,yy);

 82     vl=merge(vl,vr,max(ll+1,0),max(lr+1,0));

 83     for(int i=xx;i<=yy;i++)ans=max(ans,min(vv[i],yy)-i+1);

 84     return vl;

 85 }

 86 int main(){

 87     scanf("%d%d%d",&n,&m,&q);

 88     build(1,1,n);

 89     for(int i=0;i<m;i++)zero.push_back(ji{0,0});

 90     for(int i=1;i<=q;i++){

 91         scanf("%d",&p);

 92         if (!p){

 93             scanf("%d%d",&x,&y);

 94             update(1,1,n,x,y-1);

 95         }

 96         else{

 97             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

 98             ans=0;

 99             query(1,1,n,x1,x2,y1-1,y2-1);

100             printf("%d\n",ans);

101         }

102     }

103     return 0;

104 }

巴特西

[luogu4259]寻找车位

最新文章

热门文章