P9061 sol
H_W_Y
2023-11-27 23:20:14
# 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 线段树（可能会快一点），写之前做好心理准备啊！
```cpp
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$ 发才过。~~