P9061 sol

· · 题解

P9061 [Ynoi2002] Optimal Ordered Problem Solver -sol

发现这是一道很复杂的题目，直接优化了一天才过。

首先发现每一次推平操作一定是从 1 \sim x,1 \sim y 的，所以我们画出图像来一定是一个阶梯。

就像这样：

图中的黑色边框就是我们所得到的轮廓线。

现在考虑每一次加入一个操作的时候（图中绿色线表示），我们的改变主要分为两种：

  1. 对轮廓线上面点的改变。
  2. 对其他散点的改变（图中绿色的点）。

现在来考虑如何维护这些变化（下面以往上推平，也就是操作一为例），对于轮廓线上面的点，我们用两棵线段树维护，分别从横纵坐标两个维度分别维护，也就是维护横坐标为 x 的点的个数和纵坐标为 y 的点的个数。

而在修改的时候，我们发现对于横坐标的线段树是没有改变的， 对于纵坐标的线段树，我们需要把一个区间清空和单点修改，这都是很好维护的。

再来想想其他的散点，我们同样用线段树维护，维护每一个横坐标所对应的纵坐标最小值。这样我们只需要查询一个区间内的纵坐标最小值，不断取出这个最小值使得到某一时刻 1 \sim x 区间的纵坐标最小值都比 y 大的时候就停止。还是非常好理解的。

而对于轮廓线的维护，我们直接用类似于颜色段均摊的方法维护就可以了，只用用一个 set 维护每一个凸出来的点 (x,y) 即可（两个 set 更容易理解但是跑不过）。

那么对于查询我们如何完成呢？

发现这是一个二维数点问题，直接做是双 \log 的，一定是过不了的。

那怎么办呢？

首先我们可以分成轮廓线上面和散点两个部分，轮廓线上面是好处理的，而对于散点，如上图画出的，我们可以先预处理出红色区域的点数，用简单的容斥算出绿色区域内的点，个人就得挺好理解的。

于是这道题思维上面就做完了，感觉比较抽象，常数巨大。。。

在这里总结一下实现部分：

  1. 用两棵线段树分别维护轮廓线上面横纵坐标点的数量。
  2. 用一个 set 维护颜色段均摊，也就是轮廓线。
  3. 用一棵线段树维护散点中区间纵坐标最小的点，对于每一个横坐标相同的点，我们用 vecter 维护（因为其他的似乎要超时）。

注意需要预处理出二维数点，set 维护轮廓线和轮廓线数点的细节很多，大家可以在写的时候画图分析和对拍（这个细节真的很烦）。

代码中写的是 zkw 线段树（可能会快一点），写之前做好心理准备啊！

const int N=1e6+5,inf=2e9;
int n,m,ct=0,bit,dep=0,num=0;
struct Point{int x,y;}a[N];
struct node{int op,x,y,X,Y,c;}q[N];
vector<int> G[N];
vector<pii> f[N],g[N];
bool vis[N];

struct BIT{//维护二维数点
  int tr[N];
  inline int lowbit(int i){return i&(-i);}
  inline void upd(int x,int val){for(reg int i=x;i<=n;i+=lowbit(i)) tr[i]+=val;}
  inline int qry(int x){int res=0;for(reg int i=x;i>=1;i-=lowbit(i)) res+=tr[i];return res;}
}sd,ty;

#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

inline auto max(auto x,auto y){return (x>y)?x:y;}
inline auto min(auto x,auto y){return (x>y)?y:x;}

struct SGT2{//维护轮廓线上点的线段树
  int tr[N<<2],d[N<<2];
  inline void pu(int p){tr[p]=tr[lc]+tr[rc];}
  inline void pd(int p){if(d[p]) tr[lc]=tr[rc]=tr[p],d[p]=0,d[lc]=d[rc]=1;}
  inline void upd(int p,int val){
    p+=bit;for(reg int i=dep;i>0;--i) pd(p>>i);
    tr[p]+=val;for(p>>=1;p;p>>=1) pu(p);
  }
  inline void covx(int p,int val){
    if(p==0) return;
    p+=bit;for(reg int i=dep;i>0;--i) pd(p>>i);
    tr[p]=val;for(p>>=1;p;p>>=1) pu(p);
  }    
  inline void cov(int x,int y,int delta,int cnt){
    if(x>y||(x==0&&y==0)){upd(y+1,cnt);covx(x-1,delta);return ;}
    x=x+bit-1;y=y+bit+1;
    for(reg int i=dep;i>0;--i) pd(x>>i),pd(y>>i);
    tr[x]=delta;tr[y]+=cnt;
    while(x^y^1){
      if(~x&1) tr[x^1]=0,d[x^1]=1;
      if(y&1) tr[y^1]=0,d[y^1]=1;
      x>>=1;y>>=1;pu(x),pu(y); 
    }
    for(x>>=1;x;x>>=1) pu(x);
  }
  inline int qry(int x,int y){
    if(x>y||(x==0&&y==0)) return 0;
    x=x+bit-1,y=y+bit+1;int res=0;
    for(reg int i=dep;i>0;--i) pd(x>>i),pd(y>>i);
    for(;x^y^1;x>>=1,y>>=1){
      if(~x&1) res+=tr[x^1];
      if(y&1) res+=tr[y^1];
    }return res;
  }
}sx,sy;

struct SGT1{//维护散点的线段树
  int id[N<<2],c[N<<2];
  pii tr[N<<2];
  inline void pu(int p){tr[p]=min(tr[lc],tr[rc]);c[p]=c[lc]+c[rc];}
  inline void build(){
    for(reg int p=bit+1;p<=bit+n;++p) id[p]=0,tr[p]=f[p-bit][0],c[p]=(int)f[p-bit].size()-1;
    for(reg int p=bit-1;p;--p) pu(p);
  } 
  inline void del(int p){
    p+=bit;id[p]++;tr[p]=f[p-bit][id[p]];--c[p];
    for(p>>=1;p;p>>=1) pu(p);
  }
  inline pii qry(int x,int y){
    pii res={n+1,n+1};
    for(x=x+bit-1,y=y+bit+1;x^y^1;x>>=1,y>>=1){
      if(~x&1) res=min(res,tr[x^1]);
      if(y&1) res=min(res,tr[y^1]);
    }return res;
  }
  inline int qryc(int x){
    int res=0,l=1,r=x;
    for(l=l+bit-1,r=r+bit+1;l^r^1;l>>=1,r>>=1){
      if(~l&1) res+=c[l^1];
      if(r&1) res+=c[r^1];  
    }return res;
  }
}t;

set<pii> c;

inline void init(){
  n=read();m=read();
  for(int i=1;i<=n;++i) a[i].x=read(),a[i].y=read(),G[a[i].x].pb(a[i].y),f[a[i].x].pb({a[i].y,i}),ty.upd(a[i].y,1);
  for(bit=1;bit<=n+1;bit<<=1) dep++;
  a[0]=(Point){inf,inf};
  for(int i=1;i<=m;++i){
    q[i].op=read(),q[i].x=read(),q[i].y=read(),q[i].X=read(),q[i].Y=read();
    g[q[i].X].pb({q[i].Y,i});
  }
  num=0;
  for(reg int i=n;i>=1;--i){
    sort(f[i].begin(),f[i].end());
    f[i].pb({n+1,0});
    for(auto j:g[i]) q[j.se].c=num-sd.qry(j.fi);
    for(auto j:G[i]) num++,sd.upd(j,1);
  } //二维数点的预处理
  t.build();c.insert({0,0});c.insert({n+1,0});
}

inline int qry(node nw){
  auto it=c.lb({nw.X,n+1});
  if((*it).se>nw.Y) return 0;//在轮廓线内的要先判掉
  return sx.qry(1,nw.X)-sy.qry(nw.Y+1,n)+t.qryc(nw.X)+ty.qry(nw.Y)+nw.c-n+ct;
}

inline void upd1(node nw){//操作1
  int x=nw.x,y=nw.y,id,l;
  auto it=c.lb({x,n+1});
  l=(*it).se;bool vis=false;
  if(l>=y) return;
  if(it!=c.begin()){
    --it;
    while((*it).se<=y){
      if(it==c.begin()){c.erase(it);vis=true;break;}
      else c.erase(it--);
    }  
    if(vis||(!vis&&(*it).fi!=x)) c.insert({x,y});   
  }
  else c.insert({x,y}); 
  int delta=sx.qry(x+1,n)-sy.qry(1,l-1),cnt=sy.qry(l,y-1)-delta;
  if(cnt>0) sy.cov(l+1,y-1,delta,cnt);//建议自己画图分析一下
  num=0;
  while(a[id=t.qry(1,x).se].y<=y){
    t.del(a[id].x);ty.upd(a[id].y,-1);
    sx.upd(a[id].x,1);++ct;++num;
  }
  if(num) sy.upd(y,num);
}

inline void upd2(node nw){操作2
  int x=nw.x,y=nw.y,id,l=0;
  auto it=c.lb({x,n+1});
  if((*it).se>y) return;
  bool vis=false;
  if(it!=c.begin()){
    --it;
    while((*it).se<=y){
      if(it==c.begin()){c.erase(it);vis=true;break;}
      else c.erase(it--);
    }
    if(vis||(!vis&&(*it).fi!=x)) c.insert({x,y}); 
    l=vis?0:(*it).fi;
  }
  else if((*it).se!=y) c.insert({x,y});
  int delta=sy.qry(y+1,n)-sx.qry(1,l-1),cnt=sx.qry(l,x-1)-delta;
  if(cnt>0) sx.cov(l+1,x-1,delta,cnt);
  num=0;
  while(a[id=t.qry(1,x).se].y<=y){
    t.del(a[id].x);ty.upd(a[id].y,-1);
    sy.upd(a[id].y,1);++ct;++num;
  }
  if(num) sx.upd(x,num);
} 

inline void sol(int i){
  (q[i].op==1)?upd1(q[i]):upd2(q[i]);
  print(qry(q[i]));
}

inline void wrk(){
  init();
  for(reg int i=1;i<=m;++i) sol(i);
}

/*2023.11.24-27 H_W_Y P9061 [Ynoi2002] Optimal Ordered Problem Solver SGT*/
int main(){wrk();return 0;}

容易发现我交了整整 65 发才过。