[DS记录]P6109 [Ynoi2009]rprmq

command_block · 2020-03-07 12:46:06 · 个人记录

题意 n\times n的矩阵,先m次矩形+,然后q次矩形求\max

矩形求\max就变成了一段时间内存在的区间\max。

从某个时间点切开,向前向后延伸建立线段树,对于询问,就可以将左右端点历史最值分别查询一次。

不过注意,每个时刻可能出现多个操作,这时我们要先把减法做完,否则会导致历史最值大于真实值。

但是每个修改矩形会被分到很多的节点上去。

对于那些没有覆盖整个区间的修改,和线段树类似,只会挂在O(logn)个节点上。

在整个区间内都存在的修改,可以直接丢在初始状态里面。

类似线段树分治,初始状态是可以向下传递的,每次向左右做完之后还原即可。

历史最值问题 : 支持区间加和历史最值

维护x,m,t,mt分别表示区间最值,区间历史最值,加法标记,加法标记的历史最值。

每次u\rightarrow v下推的时候,令:

v.m=max(v.m,v.x+u.mt);
v.mt=max(v.mt,u.mt+v.t);
v.x+=u.t;
v.t+=u.t;
u.t=u.mt=0;

第一行 : 最值更新为原值+这一堆变化量中的最值。

第二行 : 变化量中的最值,既可以是自己历史留存的,也可以是目前持有的标记经受的所有更新的最值。

三四行是经典的。

第五行 : 标记完成了历史使命,被清空。

问题在于,我们需要一个操作能够清空历史最值,也就是说把全部的m=x;mt=t

我们可以在线段树上打访问标记,然后对被访问到的点进行dfs来做这件事。

然而,我们还有向下传递初始状态以及撤回操作。

这些操作之间还跨越了数次撤回操作,所以可能导致出问题。

一个naive的想法是 : 重置这两次操作之间的所有访问过的节点。这样就保证不可能错。

复杂度是O(nlog^2n+qlogn)的。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 50500
#define MaxM 500500
using namespace std;
inline int read()
{
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int n,ef;
struct Node
{
  ll x,t,m,mt;int vis;
  void add(ll ct,ll cmt){
    m=max(m,x+cmt);
    mt=max(mt,cmt+t);
    x+=ct;t+=ct;
  }
}a[MaxN<<2];
inline void ladd(int u)
{
  a[u].vis=ef;
  if (a[u].t||a[u].mt){
    a[u<<1].add(a[u].t,a[u].mt);
    a[u<<1|1].add(a[u].t,a[u].mt);
    a[u].t=a[u].mt=0;
  }
}
inline void up(int u)
{
  a[u].x=max(a[u<<1].x,a[u<<1|1].x);
  a[u].m=max(a[u<<1].m,a[u<<1|1].m);
}
int wfl,wfr,wfc;
void upd(int l=1,int r=n,int u=1)
{
  if (wfl<=l&&r<=wfr){
    a[u].add(wfc,max(wfc,0));
    return ;
  }ladd(u);
  int mid=(l+r)>>1;
  if (wfl<=mid)upd(l,mid,u<<1);
  if (mid<wfr)upd(mid+1,r,u<<1|1);
  up(u);
}
ll qry(int l=1,int r=n,int u=1)
{
  if (wfl<=l&&r<=wfr)return a[u].m;
  ladd(u);
  int mid=(l+r)>>1;ll ans=0;
  if (wfl<=mid)ans=qry(l,mid,u<<1);
  if (mid<wfr)ans=max(ans,qry(mid+1,r,u<<1|1));
  return ans;
}
int lim;
void clr(int l=1,int r=n,int u=1)
{
  if (a[u].vis<lim){
    a[u].m=a[u].x;
    a[u].mt=max(a[u].t,0ll);
    return ;
  }ladd(u);
  int mid=(l+r)>>1;
  clr(l,mid,u<<1);
  clr(mid+1,r,u<<1|1);
  up(u);
}
struct Data
{int tl,tr,l,r,x;};
vector<Data> t[MaxN<<2];
Data wfop;
void addop(int l=1,int r=n,int u=1)
{
  t[u].pb(wfop);
  if (wfl<=l&&r<=wfr)return ;
  int mid=(l+r)>>1;
  if (wfl<=mid)addop(l,mid,u<<1);
  if (mid<wfr)addop(mid+1,r,u<<1|1);
}
ll ans[MaxM];
struct OP
{
  int l,r,x;bool op;
  void ord(){
    wfl=l;wfr=r;
    if (op==1){wfc=x;upd();}
    else ans[x]=max(ans[x],qry());
  }
}stk[MaxN];
int tot;
vector<OP> g[MaxN];
Data b[MaxM],s1[MaxM],s2[MaxM];
void solve(int l,int r,int tl,int tr,int u)
{
  if (tl>tr)return ;
  int mid=(l+r)>>1,tim=tot,se=ef+1,t1=0,t2=0;
  for (int i=l-1;i<=r+1;i++)g[i].clear();
  for (int i=0;i<t[u].size();i++){
    Data st=t[u][i];
    st.l=max(st.l,l);st.r=min(st.r,r);
    OP t0=(OP){st.tl,st.tr,-st.x,1},
       t1=(OP){st.tl,st.tr,st.x,1};
    if (st.l==l&&st.r==r){
      t1.ord();
      stk[++tot]=t0;
      continue;
    }
    if (st.l<=mid&&mid<st.r){
      g[st.l-1].pb(t0);g[mid].pb(t1);
      g[mid+1].pb(t1);g[st.r+1].pb(t0);
    }else if (st.r<=mid){
      g[st.l-1].pb(t0);g[st.r].pb(t1);
    }else {
      g[st.l].pb(t1);g[st.r+1].pb(t0);
    }
  }
  for (int i=tl;i<=tr;i++){
    OP t=(OP){b[i].tl,b[i].tr,b[i].x,0};
    if (b[i].l<=mid&&mid<=b[i].r){
      g[b[i].l].pb(t);
      if (mid<b[i].r)g[b[i].r].pb(t);
    }else if (b[i].r<=mid)s1[++t1]=b[i];
    else s2[++t2]=b[i];
  }
  ef++;
  for (int i=mid;i>=l-1;i--){
    for (int j=0;j<g[i].size();j++)
      if (g[i][j].x<0)g[i][j].ord();
    for (int j=0;j<g[i].size();j++)
      if (g[i][j].x>0)g[i][j].ord();
  }lim=ef;clr();
  ef++;
  for (int i=mid+1;i<=r+1;i++){
    for (int j=0;j<g[i].size();j++)
      if (g[i][j].x<0)g[i][j].ord();
    for (int j=0;j<g[i].size();j++)
      if (g[i][j].x>0)g[i][j].ord();
  }lim=ef;clr();
  memcpy(b+tl,s1+1,t1*sizeof(Data));
  memcpy(b+tl+t1,s2+1,t2*sizeof(Data));
  solve(l,mid,tl,tl+t1-1,u<<1);
  solve(mid+1,r,tl+t1,tl+t1+t2-1,u<<1|1);
  ef++;
  while(tot>tim)stk[tot--].ord();
  lim=se;clr();
}
int m,q;
int main()
{
  n=read();m=read();q=read();
  for (int i=1;i<=m;i++){
    wfop.tl=read();wfl=wfop.l=read();
    wfop.tr=read();wfr=wfop.r=read();
    wfop.x=read();addop();
  }for (int i=1;i<=q;i++){
    b[i].tl=read();b[i].l=read();
    b[i].tr=read();b[i].r=read();
    b[i].x=i;
  }solve(1,n,1,q,1);
  for (int i=1;i<=q;i++)
    printf("%lld\n",ans[i]);
  return 0;
}