挺厉害的线段树题

---

m<=n，所以n<=2000,并且只有1000次修改询问，mqlogn的复杂度可以接受！

 求全局？

对行(n)建一个线段树。

线段树中维护的东西，一定可以包含所有“完全包含在”这个横条中的最大正方形。

只在mid左、右的可以递归下去再取max，跨越中间的？

大小为1000的两个数组，维护区间两端的1000个位置的从左从右开始最长1的个数

线段树pushup的时候 考虑跨过mid的正方形

不妨考虑长方形 宽<=长 纵向下来的是宽，双指针l,r 横向的是长 不断往后走r 如果r-l+1>lsmin(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-U+1)来贡献答案。（U，D是列的限制）

都是对i-U+1取min，那么r[x][i]一定就是选择最大的那一个。

所以，

每个区间再维护一个R[i]，所有r[i]的max

这样保证了子矩形分到完整的区间的时候，可以直接做完return了。复杂度就能正确

对于query时往两侧都分治的区间，要再统计跨区间的最大正方形

这时最大1的长度就要和行的限制取min了。

queue用个pair存

 

代码：

（动态分内存）

#include
     
      #define reg register int#define il inline#define numb (ch^'0')#define mid ((l+r)>>1)#define ls (x<<1)#define rs (x<<1|1)#define fi first#define se secondusing namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=4e6+10;int n,m,q;int *lmx[4*N],*rmx[4*N],*ans[4*N];int Pool[14*N],*cur=Pool,*mp[N];struct que{    int l,r;    pair
      
       q[N];//    void p_f(int L){//        while(l<=r&&q[l]
       
        v) --r;        q[++r]=make_pair(id,v);    }    int get(int L){        while(l<=r&&q[l].fi
        
         =j&&Q1.get(j)+Q2.get(j)
         
          =j&&Q1.get(j)+Q2.get(j)
         
        
       
      
     

总结：

抓住m<=n性质，对长的n建线段树，区间维护信息时候，处理跨域mid的最大正方形。

灵活运用单调队列。