20231025

P6109 [Ynoi2009] rprmq1 题解-猫树+Segment Tree Beats

不愧是学长出的题。。。让我更深刻地理解了猫树。

Statement

传送门

有一个 \(n \times n\) 的矩阵 \(a\)，初始全是 \(0\)，有 \(m\) 次修改操作和 \(q\) 次查询操作，先进行所有修改操作，然后进行所有查询操作。

一次修改操作会给出 \(l_1,l_2,r_1,r_2,x\)，代表把所有满足 \(l_1 \le i \le r_1\) 且 \(l_2 \le j \le r_2\) 的 \(a_{i,j}\) 元素加上一个值 \(x\)。

一次查询操作会给出 \(l_1,l_2,r_1,r_2\)，代表查询所有满足 \(l_1 \le i \le r_1\) 且 \(l_2 \le j \le r_2\) 的 \(a_{i,j}\) 元素的最大值。

对于 \(100\%\) 的数据，\(1\leq n,m\leq 5\times 10^4\)，\(1\leq q \leq 5\times 10^5\)，\(1\leq x\leq 2147483647\)，\(1\leq l_1\leq r_1\leq n\)，\(1\leq l_2\leq r_2\leq n\)。

Solution

首先我们第一步需要想到的：

二维问题可将一维看作时间轴，转化为历史版本问题。

于是我们把一维看作时间轴，那么答案就是问一段时间的历史最大值。

而且历史最大值，我们可以直接用吉司机线段树维护。

考虑如何处理一段时间——用猫树分治！

我们把这些区间挂在猫树上面进行合并即可。

具体来说，我们需要用吉司机线段树维护一个回退操作，

也就是代码里面的 reset，即放弃之前记录的历史最大。

在猫树上面我们先算 \(mid\sim r\) 的区间的答案，

即直接枚举一次，每次询问即可。

这一步完成后回退回去既可以枚举右子树。

而左子树我们用相同的方法处理即可。

这种思路真的好妙！！！

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=1e6+5;
const ll inf=2e9;
int n,m,Q;
struct node{
  int l,r;
  ll val;
  bool operator <(const node &rhs) const{
    return val<rhs.val;
  }
};
vector<node> a[N];

#define mid ((l+r)>>1)
#define lc p<<1
#define rc p<<1|1
#define lson l,mid,lc
#define rson mid+1,r,rc
#define pb push_back

namespace SGT{
  struct sgt{
  	ll mx,hmx,tag1,tag2;
  	int res;
  }tr[N<<2];

  void pu(int p){
  	tr[p].mx=max(tr[lc].mx,tr[rc].mx);
  	tr[p].hmx=max(tr[lc].hmx,tr[rc].hmx);
  }
  
  void change(int p,ll tag1,ll tag2){
  	tr[p].hmx=max(tr[p].hmx,tr[p].mx+tag1);
  	tr[p].mx+=tag2;
  	tr[p].tag1=max(tr[p].tag1,tr[p].tag2+tag1);
  	tr[p].tag2+=tag2;
  }
  
  void reset(int p){
  	change(lc,tr[p].tag1,tr[p].tag2);change(rc,tr[p].tag1,tr[p].tag2);
  	tr[p].tag1=tr[p].tag2=0;
  	tr[p].hmx=tr[p].mx;tr[p].res=1;
  }
  
  void pd(int p){
  	if(!p) return;
  	if(tr[p].res){reset(lc),reset(rc);tr[p].res=0;}
  	change(lc,tr[p].tag1,tr[p].tag2);change(rc,tr[p].tag1,tr[p].tag2);
  	tr[p].tag1=tr[p].tag2=0;
  }
  
  void update(int l,int r,int p,int x,int y,ll val){
  	if(x<=l&&y>=r){change(p,val,val);return;}
	pd(p);
	if(x<=mid) update(lson,x,y,val);
	if(y>mid) update(rson,x,y,val);
	pu(p);
  }
  
  ll query(int l,int r,int p,int x,int y){
  	if(x<=l&&y>=r) return tr[p].hmx;
  	pd(p);
	ll res=-inf;
	if(x<=mid) res=max(res,query(lson,x,y));
	if(y>mid) res=max(res,query(rson,x,y));
	return res;
  }
}

struct ask{
  int l,r,x,y,id;
}b[N];
ll ans[N];
vector<ask> q[N<<2];

bool cmp1(ask a,ask b){return a.r<b.r;}
bool cmp2(ask a,ask b){return a.l>b.l;}

void add(int l,int r,int p,ask val){
  if(val.l<=mid+1&&val.r>=mid){q[p].pb(val);return;}
  if(val.r<=mid) add(lson,val);
  else add(rson,val);
}

void ins(int x,int op){
  if(op==1) for(auto p:a[x]) SGT::update(1,n,1,p.l,p.r,p.val);
  else for(int i=(int)a[x].size()-1;i>=0;i--) SGT::update(1,n,1,a[x][i].l,a[x][i].r,-a[x][i].val);
}

void sol(int l,int r,int p){
  for(int i=l;i<=mid;i++) ins(i,1);
  int cnt=0,nw=1;
  for(auto i:q[p]) b[++cnt]=i;
  sort(b+1,b+cnt+1,cmp1);
  while(nw<=cnt&&b[nw].r==mid) nw++;
  for(int i=mid+1;i<=r;i++){
  	ins(i,1);
  	if(i==mid+1) SGT::reset(1);
  	while(b[nw].r==i&&nw<=cnt) ans[b[nw].id]=max(ans[b[nw].id],SGT::query(1,n,1,b[nw].x,b[nw].y)),nw++;
  }
  for(int i=r;i>=mid+1;i--) ins(i,-1);
  if(l!=r) sol(rson);
  cnt=0;nw=1;
  for(auto i:q[p]) b[++cnt]=i;
  sort(b+1,b+cnt+1,cmp2);
  while(nw<=cnt&&b[nw].l==mid+1) nw++;
  for(int i=mid;i>=l;i--){
  	if(i==mid) SGT::reset(1);
  	while(b[nw].l==i&&nw<=cnt) ans[b[nw].id]=max(ans[b[nw].id],SGT::query(1,n,1,b[nw].x,b[nw].y)),nw++;
    ins(i,-1);
  }
  if(l!=r) sol(lson);
}

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(ll x){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

int main(){
  /*2023.10.25 H_W_Y P6109 [Ynoi2009] rprmq1 猫树+Segment Tree Beats*/ 
  n=read();m=read();Q=read();
  for(int i=1;i<=m;i++){
  	int l=read(),x=read(),r=read(),y=read();ll val=1ll*read();
  	a[l].pb((node){x,y,val});
  	a[r+1].pb((node){x,y,-val});
  }
  for(int i=1;i<=Q;i++){
  	int l=read(),x=read(),r=read(),y=read();
  	add(1,n,1,(ask){l,r,x,y,i});
  }
  for(int i=1;i<=n;i++) sort(a[i].begin(),a[i].end());
  sol(1,n,1);
  for(int i=1;i<=Q;i++) print(ans[i]);
  return 0; 
}

Conclusion

二维问题可将一维看作时间轴，转化为历史版本问题。

区间离线问题可以考虑用猫树。