P6109 [Ynoi2009] rprmq1 题解
猫树分治 + 区间历史最值。
没找到猫树分治的模板只能过来写这个了。
猫树分治，是线段树分治的一种，类似于整体二分和线段树分治的结合，但每次把越过中点的询问处理并删除，而不是到底在处理，这里需要注意与 mid 或者 (mid+1) 相等也是中点。
注意到每次询问的矩形是 4-Side 的，也就是有 4 条边的。
参考小学奥数，老爷爷喜欢把篱笆围在靠墙的地方，这提醒我们把矩形拆分成两个由中点延伸的部分，这样可以用两次扫面线扫描线段树历史最值取最大值得到答案。
就像这样。
如果你不会线段树历史最值，参考： P4314 CPU 监控。
所以考虑一种及其暴力的情况：我们每次在线段树上插入矩形，然后每次把矩形处理成扫描线线段加入。
注意几个细节。
$2.$ 注意开 `long long`。
只要在递归子节点的时候把区间都有的矩形加上，每次扫描线后撤销操作，递归推出撤销操作即可。
看一眼，**本题不卡常**！高兴地交上去，发现 **MLE** 了。
我们发现每次撤销操作的空间复杂度是 $\mathcal{O}(mlog^{2}n)$ 的，严重超出限制。
考虑用更好的撤销方法，发现区间历史最值线段树不易撤销，所以对全局加上一个极大值，后面再减去加上的和。
当然还有另一种做法，每次递归子区间的时候把另一半先算上，递归完撤销递归另一半，但细节过多，并未采用。
更多细节详见代码。
**为了防抄把历史最值线段树删掉了，且函数中有几处错误。**
码风**不**优美，见谅。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll1;
template<typename T>
void in(T &n){n=0;char c=getchar();bool flag=0;for(;c<'0'||c>'9';c=getchar()) if (c=='-') flag=1;for(;c>='0'&&c<='9';c=getchar())(n*=10)+=(c^48);if(flag)n=-n;}
int wlsk[45];int wltp;
template<typename T>
void out(T n,char c=0){if(n==0){putchar('0');if(c)putchar(c);return;}if(n<0)putchar('-'),n=-n;while(n) wlsk[++wltp]=(n%10),n/=10;while(wltp)putchar(wlsk[wltp--]^48);if(c)putchar(c);}
const int N=5e4+5;
const int M=5e5+5;
const ll1 inf=5e4*(long long)INT_MAX;
namespace Sgt{//历史最值线段树，封namespace里。
}
int n,m,q;
//按照一维坐标分治
struct Query{int xl,xr,yl,yr,id;}qs[M];
int totq,tota;
struct Square{int lx,rx,ly,ry,val;};
struct Node{
int l,r;
vector<Square>sqr;//每个的矩形加
vector<Square>tag;//打标记的矩形加（不与矩形重叠）
}t[N*4];
#define ls (o<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
void build(int o,int l,int r){
t[o]=(Node){l,r};if(l==r)return;
build(ls,l,mid),build(rs,mid+1,r);
}
void insert(int o,int lt,int rt,Square x){//孩子们，其实这和树套树真没区别
int l=t[o].l,r=t[o].r;
if(l>=lt&&r<=rt){t[o].tag.push_back(x);return;}
t[o].sqr.push_back(x);
if(lt<=mid)insert(ls,lt,rt,x);
if(rt>mid)insert(rs,lt,rt,x);
}
void init(){
in(n),in(m),in(q);
int xl,yl,xr,yr,val;
build(1,1,n);
Sgt::build(1,1,n);
for(int i=1;i<=m;i++){
in(xl),in(yl),in(xr),in(yr),in(val);
insert(1,xl,xr,(Square){xl,xr,yl,yr,val});
}
for(int i=1;i<=q;i++){
in(xl),in(yl),in(xr),in(yr);
qs[++totq]=(Query){xl,xr,yl,yr,i};
}
}
struct Seg{
int x,l,r,val;
bool op;//0修1问
//注意同值情况的加入顺序，先减再加，防止历史最值溢出
}sgl[M*4],sgr[M*4];//存储当前猫树分治
int lts=0,rts=0;
bool CMPL(Seg x,Seg y){//倒序
if(x.x!=y.x)return x.x>y.x;
if(x.op!=y.op)return x.op<y.op;
return x.val<y.val;
}
bool CMPR(Seg x,Seg y){
if(x.x!=y.x)return x.x<y.x;
if(x.op!=y.op)return x.op<y.op;
return x.val<y.val;
}
void Devide(int l,int r,Square sq){//拆分矩形加
if(sq.rx<=mid){//在左边的询问
sgl[++lts]=(Seg){sq.rx,sq.ly,sq.ry,sq.val,0};
sgl[++lts]=(Seg){sq.lx-1,sq.ly,sq.ry,-sq.val,0};
}else if(sq.lx>mid){//右边
sgr[++rts]=(Seg){sq.lx,sq.ly,sq.ry,sq.val,0};
sgr[++rts]=(Seg){sq.rx+1,sq.ly,sq.ry,-sq.val,0};
}else{//两边都有
sgl[++lts]=(Seg){mid,sq.ly,sq.ry,sq.val,0};
sgl[++lts]=(Seg){sq.lx-1,sq.ly,sq.ry,-sq.val,0};
sgr[++rts]=(Seg){mid+1,sq.ly,sq.ry,sq.val,0};
sgr[++rts]=(Seg){sq.rx+1,sq.ly,sq.ry,-sq.val,0};
}
}
//其中1%数据，为样例1
ll1 allinf=0;//遗忘操作加
void DateBack(){//遗忘操作，加一个极大值再减去即可。
//这里取值域上限，用long long即可
Sgt::add(1,1,n,inf);
allinf+=inf;
}
ll1 Ans[M];
void Left(){
if(!lts)return;
sort(sgl+1,sgl+1+lts,CMPL);
int l,r,w;
for(int i=1;i<=lts;i++){
l=sgl[i].l,r=sgl[i].r;
w=sgl[i].val;
if(sgl[i].op==0){
Sgt::add(1,l,r,w);
}else{
Ans[w]=max(Ans[w],Sgt::query(1,l,r)-allinf);
}
}
}
void Right(){
if(!rts)return;
sort(sgr+1,sgr+1+rts,CMPR);
int l,r,w;
for(int i=1;i<=rts;i++){
l=sgr[i].l,r=sgr[i].r;
w=sgr[i].val;
if(sgr[i].op==0){
Sgt::add(1,l,r,w);
}else{
Ans[w]=max(Ans[w],Sgt::query(1,l,r)-allinf);
}
}
}
Query ql[M],qr[M];
void solve(int o,int lt,int rt){
if(lt>rt)return;
int l=t[o].l,r=t[o].r;
for(auto sq:t[o].tag)Sgt::add(1,sq.ly,sq.ry,sq.val);
lts=rts=0;int cl=0,cr=0;//左边的，右边的询问
for(auto sq:t[o].sqr)Devide(l,l,sq);//放入当前这轮的询问矩形
//当前线段树分治存储的矩形加，构成猫树分治，考虑矩形。
for(int L,R,i=lt;i<=rt;i++){//处理询问
L=qs[i].xl,R=qs[i].xr;
if((R<mid)||(L>mid+1)){
if(R<mid)ql[++cl]=qs[i];
else qr[++cr]=qs[i];//下一层解决！
continue;
}
if(R==mid){//左边的询问
sgl[++lts]=(Seg){L,qs[i].yl,qs[i].yr,qs[i].id,1};
}else if(L==mid+1){//右边的询问
sgr[++rts]=(Seg){R,qs[i].yl,qs[i].yr,qs[i].id,1};
}else{//都有
sgl[++lts]=(Seg){L,qs[i].yl,qs[i].yr,qs[i].id,1};
sgr[++rts]=(Seg){R,qs[i].yl,qs[i].yr,qs[i].id,1};
}
}
for(int i=lt;i<lt+cl;i++)qs[i]=ql[i-lt+1];
for(int i=rt-cr+1;i<=rt;i++)qs[i]=qr[i-rt+cr];
Right();//做右边3side矩形
DateBack();//遗忘历史最值操作。
Left();//做左边的3side矩形
DateBack();//遗忘历史最值操作。
if(l!=r)solve(ls,lt,lt+cl-1),solve(rs,rt-cr+1,rt);//递归子结点
for(auto sq:t[o].tag)Sgt::add(1,sq.ly,sq.ry,-sq.val);//减去标记
DateBack();//遗忘历史最值操作。
}
void work(){
solve(1,1,q);
for(int i=1;i<=q;i++){
out(Ans[i],'\n');
}
}
signed main(){
init();
work();
return 0;
}
```