北京建网站软件,深圳企业网站,会员制营销,中英文网站后台[Code#3]寻找车位 挺厉害的线段树题 mn#xff0c;所以n2000,并且只有1000次修改询问#xff0c;mqlogn的复杂度可以接受#xff01; 求全局#xff1f; 对行(n)建一个线段树。 线段树中维护的东西#xff0c;一定可以包含所有“完全包含在”这个横条中的最大正方…[Code#3]寻找车位 挺厉害的线段树题 mn所以n2000,并且只有1000次修改询问mqlogn的复杂度可以接受 求全局 对行(n)建一个线段树。 线段树中维护的东西一定可以包含所有“完全包含在”这个横条中的最大正方形。 只在mid左、右的可以递归下去再取max跨越中间的 大小为1000的两个数组维护区间两端的1000个位置的从左从右开始最长1的个数 线段树pushup的时候 考虑跨过mid的正方形 不妨考虑长方形 宽长 纵向下来的是宽双指针l,r 横向的是长 不断往后走r 如果r-l1lsmin(l,r)rsmin(l,r) 那么l 保证宽小于等于长 宽大于长的会在宽小的时候统计到 相当于枚举对于r的时候最靠上的宽小于等于长的位置l 因为ans取决于短边也就是宽 一定有单调性所以l直接即可 lsmin(l,r)rsmin(l,r)额外用单调队列维护 子矩形 先通过线段树把子矩形劈成logn段就暂时消除了行宽的限制 直接做的话对于完整的一个线段树区域还要暴力枚举每个行中线的就O(q*n^2logn)了 然鹅 对于每一个中线mid设之前单调队列找到的边长是r[x][i]那么就是min(r[x][i],i-U1)来贡献答案。UD是列的限制 都是对i-U1取min那么r[x][i]一定就是选择最大的那一个。 所以 每个区间再维护一个R[i]所有r[i]的max 这样保证了子矩形分到完整的区间的时候可以直接做完return了。复杂度就能正确 对于query时往两侧都分治的区间要再统计跨区间的最大正方形 这时最大1的长度就要和行的限制取min了。 queue用个pair存 代码 动态分内存 #includebits/stdc.h
#define reg register int
#define il inline
#define numb (ch^0)
#define mid ((lr)1)
#define ls (x1)
#define rs (x1|1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
il void rd(int x){char ch;x0;bool flfalse;while(!isdigit(chgetchar()))(ch-)(fltrue);for(xnumb;isdigit(chgetchar());xx*10numb);(fltrue)(x-x);
}
namespace Miracle{
const int N4e610;
int n,m,q;
int *lmx[4*N],*rmx[4*N],*ans[4*N];
int Pool[14*N],*curPool,*mp[N];
struct que{int l,r;pairint,intq[N];
// void p_f(int L){
// while(lrq[l]L) l;
// }void push(int id,int v){while(lrq[r].sev) --r;q[r]make_pair(id,v);}int get(int L){while(lrq[l].fiL) l;if(lr) return q[l].se;else return -1;}void clear(){l1,r0;}
}Q1,Q2;
void pushup(int x,int l,int r){Q1.clear();Q2.clear();int j1;for(reg i1;im;i){Q1.push(i,rmx[ls][i]);Q2.push(i,lmx[rs][i]);while(ijQ1.get(j)Q2.get(j)i-j1){j;}ans[x][i]i-j1;}for(reg i1;im;i){ans[x][i]max(ans[x][i],max(ans[ls][i],ans[rs][i]));lmx[x][i](lmx[ls][i]mid-l1)?lmx[ls][i]lmx[rs][i]:lmx[ls][i];rmx[x][i](rmx[rs][i]r-mid)?rmx[rs][i]rmx[ls][i]:rmx[rs][i];}
}
void build(int x,int l,int r){lmx[x]cur;curm1;rmx[x]cur;curm1;ans[x]cur;curm1;if(lr){for(reg i1;im;i){ans[x][i]rmx[x][i]lmx[x][i]mp[l][i];}return;}build(x1,l,mid);build(x1|1,mid1,r);pushup(x,l,r);
}
void upda(int x,int l,int r,int p,int t,int c){if(lr){ans[x][t]rmx[x][t]lmx[x][t]c;return;}if(pmid) upda(x1,l,mid,p,t,c);else upda(x1|1,mid1,r,p,t,c);pushup(x,l,r);
}
int mx;
void merge(int x,int l,int r,int L,int R,int U,int D){Q1.clear();Q2.clear();int jU;for(reg iU;iD;i){Q1.push(i,min(mid-L1,rmx[ls][i]));Q2.push(i,min(R-mid,lmx[rs][i]));while(ijQ1.get(j)Q2.get(j)i-j1){j;}mxmax(mx,i-j1);}
}
void query(int x,int l,int r,int L,int R,int U,int D){if(LlrR){for(reg iU;iD;i){mxmax(mx,min(ans[x][i],i-U1));}return;}if(LmidmidR) {query(x1,l,mid,L,R,U,D);query(x1|1,mid1,r,L,R,U,D);merge(x,l,r,L,R,U,D);}else if(Lmid){query(x1,l,mid,L,R,U,D);}else{query(x1|1,mid1,r,L,R,U,D);}
}int main(){rd(n);rd(m);rd(q);Q1.clear();Q2.clear();for(reg i1;in;i){mp[i]cur;curm1;for(reg j1;jm;j){rd(mp[i][j]);}}build(1,1,n);int x,y,l,s,r,t;int op;while(q--){rd(op);if(op0){rd(x);rd(y);mp[x][y]^1;upda(1,1,n,x,y,mp[x][y]);}else{mx0;rd(l);rd(s);rd(r);rd(t);query(1,1,n,l,r,s,t);printf(%d\n,mx);}}return 0;
}}
signed main(){Miracle::main();return 0;
}/*Author: *Miracle*Date: 2019/2/13 21:22:39
*/ 总结抓住mn性质对长的n建线段树区间维护信息时候处理跨域mid的最大正方形。 灵活运用单调队列。转载于:https://www.cnblogs.com/Miracevin/p/10372696.html
